{"id":5064,"date":"2019-04-13T21:12:05","date_gmt":"2019-04-14T04:12:05","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5064"},"modified":"2019-04-14T23:40:19","modified_gmt":"2019-04-15T06:40:19","slug":"leetcode-weekly-contest-132","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-weekly-contest-132\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Weekly Contest 132 (1025,1026,1027,1028)"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode Weekly Contest 132 (1025,1026,1027,1028) - \u5237\u9898\u627e\u5de5\u4f5c\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/QRSDXF8ZrmE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><strong>1025. Divisor Game<\/strong><\/p>\n\n\n\n<p>Solution: Recursion with Memoization<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 12 ms\nclass Solution {\npublic:\n  bool divisorGame(int N) {\n    cache_ = vector<int>(N + 1, -1);\n    return canWin(N);\n  }\nprivate:\n  vector<int> cache_;\n  bool canWin(int N) {\n    if (N == 1) return false;\n    if (cache_[N] != -1) return cache_[N];\n    bool win = false;\n    for (int i = 1; i < N; ++i)\n      if (N % i == 0)\n        win |= !canWin(N - i);\n    return cache_[N] = win;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>1026. Maximum Difference Between Node and Ancestor<\/strong><\/p>\n\n\n\n<p>Solution: Resolution, pass min \/ max of ancestor nodes<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">class Solution {\npublic:\n  int maxAncestorDiff(TreeNode* root) {\n    if (!root) return 0;\n    return maxDiff(root, root-&gt;val, root-&gt;val);\n  }\nprivate:\n  int maxDiff(TreeNode* root, int l, int r) {\n    if (!root) return 0;\n    int cur = max(abs(root-&gt;val - l), abs(root-&gt;val - r));\n    l = min(l, root-&gt;val);\n    r = max(r, root-&gt;val);\n    return max(cur, max(maxDiff(root-&gt;left, l, r),\n                        maxDiff(root-&gt;right, l, r)));\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>1027.  Longest Arithmetic Sequence <\/strong><\/p>\n\n\n\n<p>Solution 1: Brute Force + Pruning<\/p>\n\n\n\n<p>Time complexity: O(n^3) ~ O(n^2) in practice<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 352 ms\nclass Solution {\npublic:\n  int longestArithSeqLength(vector<int>& A) {\n    int n = A.size();\n    unordered_set<int> h;\n    int ans = 2;\n    for (int a: A) h.insert(a);\n    for (int i = 0; i < n - 1; ++i)\n      for (int j = i + 1; j < n; ++j) {\n        int d = (A[j] - A[i]);\n        int t = A[j] + d;\n        int l = 2;\n        if (!h.count(t)) continue;\n        int k = j + 1;\n        for (int k = j + 1; k < n; ++k)\n          if (A[k] == t) {\n            t += d;\n            ++l;\n          }        \n        ans = max(ans, l);\n      }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>1028. Recover a Tree From Preorder Traversal<\/strong><\/p>\n\n\n\n<p>Solution: Recursion<\/p>\n\n\n\n<p>Check the current depth and expected depth, if don't match, return nullptr.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++'>\n\/\/ Author: Huahua, running time: 24 ms\nclass Solution {\npublic:\n  TreeNode* recoverFromPreorder(string S) {\n    int i = 0;\n    return recover(S, i, 0);\n  }\nprivate:\n  TreeNode* recover(const string& s, int& i, int depth) {    \n    const int d = getD(s, i);\n    if (d != depth) { i -= d; return nullptr; }    \n    auto root = new TreeNode(getVal(s, i));\n    root->left = recover(s, i, d + 1);    \n    root->right = recover(s, i, d + 1);\n    return root;\n  }\n  \n  int getD(const string& s, int& i) {\n    int d = 0;\n    while (i < s.length() &#038;&#038; s[i] == '-') {++d; ++i;}\n    return d;\n  }\n  \n  int getVal(const string&#038; s, int&#038; i) {\n    int val = 0;\n    while (i < s.length() &#038;&#038; isdigit(s[i]))\n      val = val * 10 + (s[i++] - '0');       \n    return val;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>1025. Divisor Game Solution: Recursion with Memoization Time complexity: O(n^2)Space complexity: O(n) \/\/ Author: Huahua, running time: 12 ms class Solution { public: bool divisorGame(int&#8230;<\/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-5064","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\/5064","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=5064"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5064\/revisions"}],"predecessor-version":[{"id":5071,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5064\/revisions\/5071"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5064"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5064"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5064"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}