{"id":5142,"date":"2019-05-04T21:58:09","date_gmt":"2019-05-05T04:58:09","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5142"},"modified":"2019-05-05T10:41:07","modified_gmt":"2019-05-05T17:41:07","slug":"leetcode-weekly-contest-135-1037-1038-1039-1040","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-weekly-contest-135-1037-1038-1039-1040\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Weekly Contest 135 (1037, 1038, 1039, 1040)"},"content":{"rendered":"\n

LeetCode 1037. Valid Boomerang<\/strong><\/h2>\n\n\n\n

Solution: Math
Time complexity: O(1)
Space complexity: O(1)<\/p>\n\n\n\n

\n

C++<\/h2>\n
\n\n
\nclass Solution {\npublic:\n  bool isBoomerang(vector>& points) {\n    if (points[0] == points[1] || \n        points[1] == points[2] ||\n        points[0] == points[2]) return false;\n    int dx0 = points[0][0] - points[1][0];\n    int dy0 = points[0][1] - points[1][1];\n    int dx1 = points[0][0] - points[2][0];\n    int dy1 = points[0][1] - points[2][1];    \n    return dy0 * dx1 != dy1 * dx0;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
LeetCode 1038. Binary Search Tree to Greater Sum Tree<\/strong>
<\/h2>\n\n\n\n
Solution: Recursion: right, root, left<\/p>\n\n\n\n
Time complexity: O(n)
Space complexity: O(n)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\nclass Solution {\npublic:\n  TreeNode* bstToGst(TreeNode* root) {     \n    int s = 0;    \n    function dfs = [&](TreeNode* n) {\n      if (!n) return;\n      dfs(n->right);\n      n->val = s += n->val;      \n      dfs(n->left);\n    };\n    dfs(root);\n    return root;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
1039. Minimum Score Triangulation of Polygon<\/strong>
<\/h2>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Solution: DP<\/p>\n\n\n\n
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]<\/p>\n\n\n\n
Time complexity: O(n^3)
Space complexity: O(n^2)<\/p>\n\n\n\n
\n
C++\/bottom-up<\/h2>\n
\n\n
\nclass Solution {\npublic:\n  int minScoreTriangulation(vector& A) {\n    const int n = A.size();\n    vector> dp(n, vector(n));\n    for (int l = 3; l <= n; ++l)\n      for (int i = 0; i + l <= n; ++i) {        \n        int j = i + l - 1;\n        dp[i][j] = INT_MAX;\n        for (int k = i + 1; k <= j - 1; ++k)\n          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);\n      }\n    return dp[0][n - 1];\n  }\n};\n<\/pre>\n\n<\/div>
C++\/top-down<\/h2>\n
\n\n
\nclass Solution {\npublic:\n  int minScoreTriangulation(vector& A) {\n    const int n = A.size();\n    vector> dp(n, vector(n, INT_MAX));\n    function solve = [&](int i, int j) {\n      if (j - i <= 1) return 0;\n      if (dp[i][j] != INT_MAX) return dp[i][j];\n      dp[i][j] = INT_MAX;\n      for (int k = i + 1; k <= j - 1; ++k)\n        dp[i][j] = min(dp[i][j], \n                       solve(i, k) + solve(k, j) + A[i] * A[k] * A[j]);\n      return dp[i][j];  \n    };\n    return solve(0, n - 1);\n  }\n};\n<\/pre>\n\n<\/div>
Python<\/h2>\n
\n\n
\n\"Author: Huahua\"\nfrom functools import lru_cache\n\nclass Solution:\n  def minScoreTriangulation(self, A: List[int]) -> int:     \n    @lru_cache(None)\n    def dp(i, j):      \n      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))\n    return dp(0, len(A) - 1)\n<\/pre>\n<\/div><\/div>\n\n\n\n
 1040. Moving Stones Until Consecutive II<\/strong>
<\/h2>\n\n\n\n
Solution: Sliding Window<\/p>\n\n\n\n
Time complexity: O(nlogn)
Space complexity: O(1)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\nclass Solution {\npublic:\n  vector numMovesStonesII(vector& stones) {\n    const int n = static_cast(stones.size());\n    sort(begin(stones), end(stones));\n    int max_steps = max(stones[n - 1] - stones[1] - n + 2,\n                        stones[n - 2] - stones[0] - n + 2);\n    int min_steps = INT_MAX;\n    int i = 0;\n    for (int j = 0; j < n; ++j) {\n      while (stones[j] - stones[i] >= n) ++i;\n      if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2)\n        min_steps = min(min_steps, 2);\n      else\n        min_steps = min(min_steps, n - (j - i + 1));\n    }\n    return {min_steps, max_steps};\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
LeetCode 1037. Valid Boomerang Solution: MathTime complexity: O(1)Space complexity: O(1) class Solution { public: bool isBoomerang(vector& points) { if (points[0] == points[1] || points[1] == points[2]…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[439],"class_list":["post-5142","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-weekly-contest","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5142","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5142"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5142\/revisions"}],"predecessor-version":[{"id":5151,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5142\/revisions\/5151"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5142"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5142"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5142"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}