LeetCode 1037. Valid Boomerang
Solution: Math
Time complexity: O(1)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: bool isBoomerang(vector<vector<int>>& points) { if (points[0] == points[1] || points[1] == points[2] || points[0] == points[2]) return false; int dx0 = points[0][0] - points[1][0]; int dy0 = points[0][1] - points[1][1]; int dx1 = points[0][0] - points[2][0]; int dy1 = points[0][1] - points[2][1]; return dy0 * dx1 != dy1 * dx0; } }; |
LeetCode 1038. Binary Search Tree to Greater Sum Tree
Solution: Recursion: right, root, left
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public: TreeNode* bstToGst(TreeNode* root) { int s = 0; function<void(TreeNode*)> dfs = [&](TreeNode* n) { if (!n) return; dfs(n->right); n->val = s += n->val; dfs(n->left); }; dfs(root); return root; } }; |
1039. Minimum Score Triangulation of Polygon
Solution: DP
Init: dp[i][j] = 0 if 0 <= j – i <= 1
dp[i][j] := min score to triangulate A[i] ~ A[j]
dp[i][j] = min{dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]), i < k < j
answer: dp[0][n – 1]
Time complexity: O(n^3)
Space complexity: O(n^2)
C++/bottom-up
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: int minScoreTriangulation(vector<int>& A) { const int n = A.size(); vector<vector<int>> dp(n, vector<int>(n)); for (int l = 3; l <= n; ++l) for (int i = 0; i + l <= n; ++i) { int j = i + l - 1; dp[i][j] = INT_MAX; for (int k = i + 1; k <= j - 1; ++k) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]); } return dp[0][n - 1]; } }; |
C++/top-down
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int minScoreTriangulation(vector<int>& A) { const int n = A.size(); vector<vector<int>> dp(n, vector<int>(n, INT_MAX)); function<int(int, int)> solve = [&](int i, int j) { if (j - i <= 1) return 0; if (dp[i][j] != INT_MAX) return dp[i][j]; dp[i][j] = INT_MAX; for (int k = i + 1; k <= j - 1; ++k) dp[i][j] = min(dp[i][j], solve(i, k) + solve(k, j) + A[i] * A[k] * A[j]); return dp[i][j]; }; return solve(0, n - 1); } }; |
Python
|
1 2 3 4 5 6 7 8 9 |
"Author: Huahua" from functools import lru_cache class Solution: def minScoreTriangulation(self, A: List[int]) -> int: @lru_cache(None) def dp(i, j): return 0 if j - i <= 1 else min(dp(i, k) + dp(k, j) + A[i] * A[k] * A[j] for k in range(i + 1, j)) return dp(0, len(A) - 1) |
1040. Moving Stones Until Consecutive II
Solution: Sliding Window
Time complexity: O(nlogn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: vector<int> numMovesStonesII(vector<int>& stones) { const int n = static_cast<int>(stones.size()); sort(begin(stones), end(stones)); int max_steps = max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2); int min_steps = INT_MAX; int i = 0; for (int j = 0; j < n; ++j) { while (stones[j] - stones[i] >= n) ++i; if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2) min_steps = min(min_steps, 2); else min_steps = min(min_steps, n - (j - i + 1)); } return {min_steps, max_steps}; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment