1025. Divisor Game
Solution: Recursion with Memoization
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, running time: 12 ms class Solution { public: bool divisorGame(int N) { cache_ = vector<int>(N + 1, -1); return canWin(N); } private: vector<int> cache_; bool canWin(int N) { if (N == 1) return false; if (cache_[N] != -1) return cache_[N]; bool win = false; for (int i = 1; i < N; ++i) if (N % i == 0) win |= !canWin(N - i); return cache_[N] = win; } }; |
1026. Maximum Difference Between Node and Ancestor
Solution: Resolution, pass min / max of ancestor nodes
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 maxAncestorDiff(TreeNode* root) { if (!root) return 0; return maxDiff(root, root->val, root->val); } private: int maxDiff(TreeNode* root, int l, int r) { if (!root) return 0; int cur = max(abs(root->val - l), abs(root->val - r)); l = min(l, root->val); r = max(r, root->val); return max(cur, max(maxDiff(root->left, l, r), maxDiff(root->right, l, r))); } }; |
1027. Longest Arithmetic Sequence
Solution 1: Brute Force + Pruning
Time complexity: O(n^3) ~ O(n^2) in practice
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, running time: 352 ms class Solution { public: int longestArithSeqLength(vector<int>& A) { int n = A.size(); unordered_set<int> h; int ans = 2; for (int a: A) h.insert(a); for (int i = 0; i < n - 1; ++i) for (int j = i + 1; j < n; ++j) { int d = (A[j] - A[i]); int t = A[j] + d; int l = 2; if (!h.count(t)) continue; int k = j + 1; for (int k = j + 1; k < n; ++k) if (A[k] == t) { t += d; ++l; } ans = max(ans, l); } return ans; } }; |
1028. Recover a Tree From Preorder Traversal
Solution: Recursion
Check the current depth and expected depth, if don’t match, return nullptr.
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 26 27 28 29 30 |
// Author: Huahua, running time: 24 ms class Solution { public: TreeNode* recoverFromPreorder(string S) { int i = 0; return recover(S, i, 0); } private: TreeNode* recover(const string& s, int& i, int depth) { const int d = getD(s, i); if (d != depth) { i -= d; return nullptr; } auto root = new TreeNode(getVal(s, i)); root->left = recover(s, i, d + 1); root->right = recover(s, i, d + 1); return root; } int getD(const string& s, int& i) { int d = 0; while (i < s.length() && s[i] == '-') {++d; ++i;} return d; } int getVal(const string& s, int& i) { int val = 0; while (i < s.length() && isdigit(s[i])) val = val * 10 + (s[i++] - '0'); return val; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment