{"id":5015,"date":"2019-04-07T15:46:19","date_gmt":"2019-04-07T22:46:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5015"},"modified":"2019-04-23T16:14:15","modified_gmt":"2019-04-23T23:14:15","slug":"leetcode-weekly-contest-131-1021-1022-1023-1024","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-weekly-contest-131-1021-1022-1023-1024\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Weekly Contest 131 (1021, 1022, 1023, 1024)"},"content":{"rendered":"\n<p><strong>LeetCode 1021. Remove Outermost Parentheses<\/strong><\/p>\n\n\n\n<p>Solution: Track # of opened parentheses<\/p>\n\n\n\n<p>Let n denote the # of  opened parentheses after current char, keep &#8216;(&#8216; if n &gt; 1 and keep &#8216;)&#8217; if n &gt; 0<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\/\/ Author: Huahua\nclass Solution {\npublic:\n  string removeOuterParentheses(string S) {    \n    string ans;\n    int n = 0;    \n    for (char c : S) {      \n      if (c == '(' &amp;&amp; n++) ans += c;\n      if (c == ')' &amp;&amp; --n) ans += c;      \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>LeetCode 1022. Sum of Root To Leaf Binary Numbers<\/strong><\/p>\n\n\n\n<p>Solution: Recursion + Math<\/p>\n\n\n\n<p>Keep tracking the number from root to current node.<\/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++\">\nclass Solution {\npublic:\n    int sumRootToLeaf(TreeNode* root) {      \n      return sums(root, 0);\n    }\nprivate:\n    static constexpr int kMod = 1e9 + 7;\n    int sums(TreeNode* root, int c) {\n      if (!root) return 0;\n      c = ((c << 1) | root->val) % kMod;\n      if (!root->left && !root->right) {\n        return c;\n      }\n      return sums(root->left, c) + sums(root->right, c);\n    }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>LeetCode 1023. Camelcase Matching<\/strong><\/p>\n\n\n\n<p>Solution: String&#8230;<\/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\nclass Solution {\npublic:\n  vector<bool> camelMatch(vector<string>& queries, string p) {\n    vector<bool> ans;\n    for (const string& q : queries)\n      ans.push_back(match(q, p));\n    return ans;\n  }\nprivate:\n  bool match(const string& q, const string& p) {    \n    int m = p.length();\n    int n = q.length();\n    int i = 0;\n    int j = 0;\n    for (i = 0; i < n; ++i) {      \n      if (j == m &#038;&#038; isupper(q[i])) return false;      \n      if ((j == m || isupper(p[j])) &#038;&#038; islower(q[i])) continue;        \n      if ((isupper(p[j]) || isupper(q[i])) &#038;&#038; p[j] != q[i]) return false;\n      if (islower(p[j]) &#038;&#038; p[j] != q[i]) continue;\n      ++j;\n    }\n    return i == n &#038;&#038; j == m;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>LeetCode 1024. Video Stitching<\/strong><\/p>\n\n\n\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 1024. Video Stitching - \u5237\u9898\u627e\u5de5\u4f5c EP248\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/tdrPFN9d1y4?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>Solution 1: DP<\/p>\n\n\n\n<p>Time complexity: O(nT^2)<br>Space complexity: O(T^2)<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/1024-ep248.png\" alt=\"\" class=\"wp-image-5024\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/1024-ep248.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/1024-ep248-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/1024-ep248-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\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, 16 ms \/ 9.5 MB\nclass Solution {\npublic:\n  int videoStitching(vector<vector<int>>& clips, int T) {\n    constexpr int kInf = 101;\n    \/\/ dp[i][j] := min clips to cover range [i, j]\n    vector<vector<int>> dp(T + 1, vector<int>(T + 1, kInf));   \n    for (const auto& c : clips) {\n      int s = c[0];\n      int e = c[1];\n      for (int l = 1; l <= T; ++l) {\n        for (int i = 0; i <= T - l; ++i) {\n          int j = i + l;\n          if (s > j || e < i) continue;\n          if (s <= i &#038;&#038; e >= j) dp[i][j] = 1;\n          else if (e >= j) dp[i][j] = min(dp[i][j], dp[i][s] + 1);\n          else if (s <= i) dp[i][j] = min(dp[i][j], dp[e][j] + 1);\n          else dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]);          \n        }\n      }\n    }\n    return dp[0][T] == kInf ? -1 : dp[0][T];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/V2<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 20 ms \/ 9.4 MB\nclass Solution {\npublic:\n  int videoStitching(vector<vector<int>>& clips, int T) {\n    constexpr int kInf = 101;\n    \/\/ dp[i][j] := min clips to cover range [i, j]\n    vector<vector<int>> dp(T + 1, vector<int>(T + 1));\n    for (int i = 0; i <= T; ++i)\n      for (int j = 0; j <= T; ++j)\n        dp[i][j] = i < j ? kInf : 0;\n    for (const auto&#038; c : clips) {\n      const int s = min(c[0], T);\n      const int e = min(c[1], T);\n      for (int l = 1; l <= T; ++l)\n        for (int i = 0, j = l; j <= T; ++i, ++j)\n          dp[i][j] = min(dp[i][j], dp[i][s] + 1 + dp[e][j]);\n    }\n    return dp[0][T] == kInf ? -1 : dp[0][T];\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>LeetCode 1021. Remove Outermost Parentheses Solution: Track # of opened parentheses Let n denote the # of opened parentheses after current char, keep &#8216;(&#8216; if&#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":[6,456,439],"class_list":["post-5015","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-leetcode","tag-weekly","tag-weekly-contest","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5015","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=5015"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5015\/revisions"}],"predecessor-version":[{"id":5102,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5015\/revisions\/5102"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5015"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5015"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5015"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}