{"id":4993,"date":"2019-03-30T21:58:31","date_gmt":"2019-03-31T04:58:31","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4993"},"modified":"2019-04-02T23:19:21","modified_gmt":"2019-04-03T06:19:21","slug":"leetcode-weekly-contest-130","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-weekly-contest-130\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Weekly Contest 130 (1017, 1018, 1019, 1020)"},"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 1017. Convert to Base -2 - \u5237\u9898\u627e\u5de5\u4f5c EP247\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/uo0jozNyNlg?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<h2 class=\"wp-block-heading\"><strong>1017. Convert to Base -2<\/strong><\/h2>\n\n\n\n<p><strong>Solution: Math \/ Simulation<\/strong><\/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\/1017-ep247.png\" alt=\"\" class=\"wp-image-5007\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/1017-ep247.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/1017-ep247-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/1017-ep247-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Time complexity: O(logn)<br>Space complexity: O(logn)<\/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  string baseNeg2(int N) {\n    if (N == 0) return \"0\"; \n    vector<char> ans;\n    while (N) {\n      ans.push_back((N & 1) + '0');\n      N = -(N >> 1);\n    }    \n    return {rbegin(ans), rend(ans)};\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">base K<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:  \n  string baseNeg2(int N) {   \n    if (N == 0) return \"0\"; \n    return baseNegK(N, -2);\n  }\nprivate:\n  string baseNegK(int N, int K) {\n    vector<char> ans;\n    while (N) {\n      int r = N % K;\n      N \/= K;\n      if (r < 0) {\n        r += -K;\n        N += 1;\n      }\n      ans.push_back(r + '0');\n    }    \n    return {rbegin(ans), rend(ans)};\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong> 1018.&nbsp;Binary Prefix Divisible By 5<\/strong><br><\/h2>\n\n\n\n<p><strong>Solution: Math<\/strong><\/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++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<bool> prefixesDivBy5(vector<int>& A) {\n    int num = 0;\n    vector<bool> ans(A.size());    \n    for (int i = 0; i < A.size(); ++i) {\n      num = ((num << 1) | A[i]) % 5;\n      ans[i] = num == 0;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong> 1019.&nbsp;Next Greater Node In Linked List<\/strong><br><\/h2>\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 1019. Next Greater Node In Linked List - \u5237\u9898\u627e\u5de5\u4f5c EP246\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/e4BtnOVy0Gs?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>Solution: Reverse + Monotonic Stack<\/strong><\/p>\n\n\n\n<p>Process in reverse order and keep a monotonically increasing stack, pop all the elements that are smaller than the current one, then the top of the stack (if exists) will be the next greater node.<\/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\/03\/1030-ep246.png\" alt=\"\" class=\"wp-image-5002\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1030-ep246.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1030-ep246-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/03\/1030-ep246-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\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<int> nextLargerNodes(ListNode* head) {    \n    vector<int> nums;\n    while (head) {\n      nums.push_back(head->val);\n      head = head->next;      \n    }\n    stack<int> s;\n    vector<int> ans(nums.size());\n    for (int i = nums.size() - 1; i >= 0; --i) {\n      while (!s.empty() && s.top() <= nums[i]) s.pop();\n      ans[i] = s.empty() ? 0 : s.top();\n      s.push(nums[i]);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>1020. Number of Enclaves<\/strong><\/h2>\n\n\n\n<p><strong>Solution: DFS \/ Connected Components<\/strong><\/p>\n\n\n\n<p>Time complexity: O(mn)<br>Space complexity: O(mn)<\/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  int numEnclaves(vector<vector<int>>& A) {\n    int ans = 0;\n    for (int i = 0; i < A.size(); ++i)\n      for (int j = 0; j < A[0].size(); ++j) {\n        int count = 0;\n        if (!dfs(A, j, i, count))\n          ans += count;\n      }\n    return ans;\n  }\nprivate:\n  static constexpr int dirs[5]{0, -1, 0, 1, 0};\n  bool dfs(vector<vector<int>>& A, int x, int y, int& count) {\n    if (x < 0 || x == A[0].size() || y < 0 || y == A.size()) return true;    \n    if (A[y][x] == 0) return false;    \n    ++count;\n    A[y][x] = 0;\n    bool valid = false;    \n    for (int i = 0; i < 4; ++i)\n      valid |= dfs(A, x + dirs[i], y + dirs[i + 1], count);\n    return valid;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>1017. Convert to Base -2 Solution: Math \/ Simulation Time complexity: O(logn)Space complexity: O(logn) \/\/ Author: Huahua class Solution { public: string baseNeg2(int N) {&#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,1],"tags":[456],"class_list":["post-4993","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-uncategorized","tag-weekly","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4993","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=4993"}],"version-history":[{"count":12,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4993\/revisions"}],"predecessor-version":[{"id":5008,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4993\/revisions\/5008"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4993"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4993"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4993"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}