LeetCode 1021. Remove Outermost Parentheses
Solution: Track # of opened parentheses
Let n denote the # of opened parentheses after current char, keep ‘(‘ if n > 1 and keep ‘)’ if n > 0
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: string removeOuterParentheses(string S) { string ans; int n = 0; for (char c : S) { if (c == '(' && n++) ans += c; if (c == ')' && --n) ans += c; } return ans; } }; |
LeetCode 1022. Sum of Root To Leaf Binary Numbers
Solution: Recursion + Math
Keep tracking the number from root to current node.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: int sumRootToLeaf(TreeNode* root) { return sums(root, 0); } private: static constexpr int kMod = 1e9 + 7; int sums(TreeNode* root, int c) { if (!root) return 0; c = ((c << 1) | root->val) % kMod; if (!root->left && !root->right) { return c; } return sums(root->left, c) + sums(root->right, c); } }; |
LeetCode 1023. Camelcase Matching
Solution: String…
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: vector<bool> camelMatch(vector<string>& queries, string p) { vector<bool> ans; for (const string& q : queries) ans.push_back(match(q, p)); return ans; } private: bool match(const string& q, const string& p) { int m = p.length(); int n = q.length(); int i = 0; int j = 0; for (i = 0; i < n; ++i) { if (j == m && isupper(q[i])) return false; if ((j == m || isupper(p[j])) && islower(q[i])) continue; if ((isupper(p[j]) || isupper(q[i])) && p[j] != q[i]) return false; if (islower(p[j]) && p[j] != q[i]) continue; ++j; } return i == n && j == m; } }; |
LeetCode 1024. Video Stitching
Solution 1: DP
Time complexity: O(nT^2)
Space complexity: O(T^2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua, 16 ms / 9.5 MB class Solution { public: int videoStitching(vector<vector<int>>& clips, int T) { constexpr int kInf = 101; // dp[i][j] := min clips to cover range [i, j] vector<vector<int>> dp(T + 1, vector<int>(T + 1, kInf)); for (const auto& c : clips) { int s = c[0]; int e = c[1]; for (int l = 1; l <= T; ++l) { for (int i = 0; i <= T - l; ++i) { int j = i + l; if (s > j || e < i) continue; if (s <= i && e >= j) dp[i][j] = 1; else if (e >= j) dp[i][j] = min(dp[i][j], dp[i][s] + 1); else if (s <= i) dp[i][j] = min(dp[i][j], dp[e][j] + 1); else dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]); } } } return dp[0][T] == kInf ? -1 : dp[0][T]; } }; |
C++/V2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua, running time: 20 ms / 9.4 MB class Solution { public: int videoStitching(vector<vector<int>>& clips, int T) { constexpr int kInf = 101; // dp[i][j] := min clips to cover range [i, j] vector<vector<int>> dp(T + 1, vector<int>(T + 1)); for (int i = 0; i <= T; ++i) for (int j = 0; j <= T; ++j) dp[i][j] = i < j ? kInf : 0; for (const auto& c : clips) { const int s = min(c[0], T); const int e = min(c[1], T); for (int l = 1; l <= T; ++l) for (int i = 0, j = l; j <= T; ++i, ++j) dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]); } return dp[0][T] == kInf ? -1 : dp[0][T]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment