1046. Last Stone Weight
Solution: Simulation (priority_queue)
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 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++
|
1 2 3 4 5 6 7 8 9 10 11 |
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++
|
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 26 27 28 29 |
// 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
Time complexity: O(n * S) = O(n * 100)
Space complexity: O(S) = O(100)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// 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; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment