Huahua’s Tech Road

花花酱 LeetCode 1051. Height Checker

By zxi on May 27, 2019

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students not standing in the right positions. (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)

Example 1:

Input: [1,1,4,2,1,3]
Output: 3
Explanation: 
Students with heights 4, 3 and the last 1 are not standing in the right positions.

Note:

1 <= heights.length <= 100
1 <= heights[i] <= 100

Solution: Sorting

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

int heightChecker(vector<int>& heights) {

vector<int> h(heights);

sort(begin(h), end(h));

int ans = 0;

for (int i = 0; i < h.size(); ++i)

ans += (heights[i] != h[i]);

return ans;

}

};

花花酱 LeetCode Weekly Contest 137

By zxi on May 18, 2019

1046. Last Stone Weight

Solution: Simulation (priority_queue)

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int lastStoneWeight(vector<int>& stones) {

priority_queue<int> q;

for (int s : stones)

q.push(s);

while (q.size() > 1) {

int x = q.top(); q.pop();

int y = q.top(); q.pop();

if (x == y) continue;

q.push(abs(x - y));

}

return q.empty() ? 0 : q.top();

}

};

1047. Remove All Adjacent Duplicates In String

Solution: Stack / Deque

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

string removeDuplicates(string S) {

deque<char> s;

for (char c : S) {

if (!s.empty() && s.back() == c) s.pop_back();

else s.push_back(c);

}

return {begin(s), end(s)};

}

};

1048. Longest String Chain

Solution: DP

dp[i] := max length of chain of (A[0] ~ A[i-1])

dp[i] = max{dp[j] + 1} if A[j] is prederrsor of A[i], 1 <= j <i

Time complexity: O(n^2*l)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestStrChain(vector<string>& words) {

int n = words.size();

sort(begin(words), end(words), [](const string& a, const string& b) {

return a.length() < b.length();

});

vector<int> dp(n, 1);

for (int i = 0; i < n; ++i)

for (int j = 0; j < i; ++j)

if (valid(words[j], words[i]))

dp[i] = dp[j] + 1;

return *max_element(begin(dp), end(dp));

}

private:

bool valid(const string& a, const string& b) {

if (a.length() + 1 != b.length()) return false;

int count = 0;

for (int i = 0, j = 0; i < a.length() && j < b.length();) {

if (a[i] == b[j]) {

++i; ++j;

} else {

++count; ++j;

}

return count <= 1;

}

};

1049. Last Stone Weight II

Solution: DP / target sum

Time complexity: O(n * S) = O(n * 100)

Space complexity: O(S) = O(100)

C++

// Author: Huahua

class Solution {

public:

int lastStoneWeightII(vector<int>& stones) {

const int n = stones.size();

const int max_sum = accumulate(begin(stones), end(stones), 0);

unordered_set<int> sums;

sums.insert(stones[0]);

sums.insert(-stones[0]);

for (int i = 1; i < n; ++i) {

unordered_set<int> tmp;

for (int s : sums) {

tmp.insert(s + stones[i]);

tmp.insert(s - stones[i]);

}

swap(tmp, sums);

}

int ans = INT_MAX;

for (int s : sums)

ans = min(ans, abs(s));

return ans;

}

};

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

By zxi on May 17, 2019

iven two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

Solution: DP

dp[i][j] := max length of (A[0:i], B[0:j])

dp[i][j] = dp[i – 1][j – 1] + 1 if A[i-1] == B[j-1] else 0

Time complexity: O(m*n)
Space complexity: O(m*n) -> O(n)

C++ S:O(mn)

// Author: Huahua, 176 ms / 106.4 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

int m = A.size();

int n = B.size();

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

int ans = 0;

for (int i = 1; i <= m; ++i)

for (int j = 1; j <= n; ++j)

if (A[i - 1] == B[j - 1]) {

dp[i][j] = dp[i - 1][j - 1] + 1;

ans = max(ans, dp[i][j]);

}

return ans;

}

};

C++ S:O(min(m,n))

// Author: Huahua, 152 ms / 9.1 MB

class Solution {

public:

int findLength(vector<int>& A, vector<int>& B) {

if (A.size() < B.size()) swap(A, B);

int m = A.size();

int n = B.size();

vector<int> dp(n + 1);

int ans = 0;

for (int i = 1; i <= m; ++i)

for (int j = n; j >= 1; --j) {

dp[j] = A[i - 1] == B[j - 1] ? dp[j - 1] + 1 : 0;

ans = max(ans, dp[j]);

}

return ans;

}

};

花花酱 LeetCode 90. Subsets II

By zxi on May 15, 2019

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

<strong>Input:</strong> [1,2,2]

<strong>Output:</strong>

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

Solution: DFS

The key to this problem is how to remove/avoid duplicates efficiently.

For the same depth, among the same numbers, only the first number can be used.

Time complexity: O(2^n * n)
Space complexity: O(n)

C++

class Solution {

public:

vector<vector<int>> subsetsWithDup(vector<int>& nums) {

const int n = nums.size();

sort(begin(nums), end(nums));

vector<vector<int>> ans;

vector<int> cur;

function<void(int)> dfs = [&](int s) {

ans.push_back(cur);

if (cur.size() == n)

return;

for (int i = s; i < n; ++i) {

if (i > s && nums[i] == nums[i - 1]) continue;

cur.push_back(nums[i]);

dfs(i + 1);

cur.pop_back();

}

};

dfs(0);

return ans;

}

};

花花酱 LeetCode 1043. Partition Array for Maximum Sum

By zxi on May 14, 2019

Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

1 <= K <= A.length <= 500
0 <= A[i] <= 10^6

Solution: DP

Time complexity: O(n*k)
Space complexity: O(n)

dp[i] := max sum of A[1] ~ A[i]
init: dp[0] = 0
transition: dp[i] = max{dp[i – k] + max(A[i-k:i]) * k}, 1 <= k <= min(i, K)
ans: dp[n]

A = | 2 | 1 | 4 | 3 |
K = 3
dp[0] = 0
dp[1] = max(dp[0] + 2 * 1) = 2
dp[2] = max(dp[0] + 2 * 2, dp[1] + 1 * 1) = max(4, 3) = 4
dp[3] = max(dp[0] + 4 * 3, dp[1] + 4 * 2, dp[2] + 4 * 1) = max(12, 10, 8) = 12
dp[4] = max(dp[1] + 4 * 3, dp[2] + 4 * 2, dp[3] + 3 * 1) = max(14, 12, 15) = 15
best = | 4 | 4 | 4 | 3 |

C++

class Solution {

public:

int maxSumAfterPartitioning(vector<int>& A, int K) {

int n = A.size();

vector<int> dp(n + 1, 0);

for (int i = 1; i <= n; ++i) {

int m = INT_MIN;

for (int k = 1; k <= K && i - k >= 0; ++k) {

m = max(m, A[i - k]);

dp[i] = max(dp[i], dp[i - k] + m * k);

}

return dp[n];

}

};

Huahua's Tech Road

花花酱 LeetCode 1051. Height Checker

Solution: Sorting

C++

花花酱 LeetCode Weekly Contest 137

1046. Last Stone Weight

C++

1047. Remove All Adjacent Duplicates In String

C++

1048. Longest String Chain

C++

1049. Last Stone Weight II

C++

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

Solution: DP

C++ S:O(mn)

C++ S:O(min(m,n))

花花酱 LeetCode 90. Subsets II

C++

花花酱 LeetCode 1043. Partition Array for Maximum Sum

Solution: DP

C++