{"id":5092,"date":"2019-04-20T21:39:26","date_gmt":"2019-04-21T04:39:26","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5092"},"modified":"2019-04-22T00:41:46","modified_gmt":"2019-04-22T07:41:46","slug":"leetcode-weekly-contest-133","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-weekly-contest-133\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Weekly Contest 133"},"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 133 (1029,1030,1031,1032)\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/3A98vh5zsqw?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<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\/weekly-133.png\" alt=\"\" class=\"wp-image-5098\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/weekly-133.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/weekly-133-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2019\/04\/weekly-133-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>LeetCode 1029  Two City Scheduling<\/strong><\/h2>\n\n\n\n<p>Solution1: DP<\/p>\n\n\n\n<p>dp[i][j] := min cost to put j people into city A for the first i people<br>dp[0][0] = 0<br>dp[i][0] = dp[i -1][0] + cost_b<br>dp[i][j] = min(dp[i &#8211; 1][j] + cost_b, dp[i &#8211; 1][j &#8211; 1] + cost_a)<br>ans := dp[n][n\/2]<\/p>\n\n\n\n<p>Time complexity: O(n^2)<br>Space complexity: O(n^2)<\/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: 8 ms\nclass Solution {\npublic:\n  int twoCitySchedCost(vector<vector<int>>& costs) {\n    int n = costs.size();\n    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX \/ 2));\n    dp[0][0] = 0;\n    for (int i = 1; i <= n; ++i) {      \n      dp[i][0] = dp[i - 1][0] + costs[i - 1][1];\n      for (int j = 1; j <= i; ++j)\n        dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0], \n                       dp[i - 1][j] + costs[i - 1][1]);\n    }\n    return dp[n][n \/ 2];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>Solution 2: Greedy<\/p>\n\n\n\n<p>Sort by cost_a - cost_b<\/p>\n\n\n\n<p>Choose the first n\/2 people for A, rest for B<\/p>\n\n\n\n<p>Time complexity: O(nlogn)<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, running time: 8 ms\nclass Solution {\npublic:\n  int twoCitySchedCost(vector<vector<int>>& costs) {\n    int n = costs.size();\n    sort(begin(costs), end(costs), [](const auto& c1, const auto& c2){\n      return c1[0] - c1[1] < c2[0] - c2[1];\n    });\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      ans += i < n\/2 ? costs[i][0] : costs[i][1];    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong> 1030.&nbsp;Matrix Cells in Distance Order<\/strong><\/h2>\n\n\n\n<p>Solution: Sorting<\/p>\n\n\n\n<p>Time complexity: O(RC*log(RC))<br>Space complexity: O(RC)<\/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<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {\n    vector<vector<int>> ans;\n    for (int i = 0; i < R; ++i)\n      for (int j = 0; j < C; ++j)\n        ans.push_back({i, j});\n    std::sort(begin(ans), end(ans), [r0, c0](const vector<int>& a, const vector<int>& b){\n      return (abs(a[0] - r0) + abs(a[1] - c0)) < (abs(b[0] - r0) + abs(b[1] - c0));\n    });\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>1031. Maximum Sum of Two Non-Overlapping Subarrays<\/strong><\/h2>\n\n\n\n<p>Solution: Prefix sum<\/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\nclass Solution {\npublic:\n  int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {\n    const int n = A.size();\n    vector<int> s(n + 1, 0);\n    for (int i = 0; i < n; ++i)\n      s[i + 1] = s[i] + A[i];\n    int ans = 0;\n    for (int i = 0; i <= n - L; ++i) {\n      int ls = s[i + L] - s[i];\n      int ms = max(maxSum(s, 0, i - M - 1, M), \n                   maxSum(s, i + L, n - M, M));\n      ans = max(ans, ls + ms);      \n    }\n    return ans;\n  }\nprivate:\n  int maxSum(const vector<int>& s, int start, int end, int l) {\n    int ans = INT_MIN;    \n    for (int i = start; i <= end; ++i)\n      ans = max(ans, s[i + l] - s[i]);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong> 1032. Stream of Characters<\/strong><\/h2>\n\n\n\n<p>Solution: Trie<\/p>\n\n\n\n<p>Time complexity: <br><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>build O(sum(len(w))<\/li><li>query O(max(len(w)) <\/li><\/ul>\n\n\n\n<p>Space complexity: O(sum(len(w))<\/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, 320 ms, 95 MB\nclass TrieNode {\npublic:        \n  ~TrieNode() {\n    for (auto node : next_)\n      delete node;\n  }\n\n  void reverse_build(const string& s, int i) {\n    if (i == -1) {\n      is_word_ = true;\n      return;\n    }\n    const int idx = s[i] - 'a';\n    if (!next_[idx]) next_[idx] = new TrieNode();\n    next_[idx]->reverse_build(s, i - 1);\n  }\n  \n  bool reverse_search(const string& s, int i) {\n    if (i == -1 || is_word_) return is_word_;\n    const int idx = s[i] - 'a';\n    if (!next_[idx]) return false;\n    return next_[idx]->reverse_search(s, i - 1);\n  }\n\nprivate:\n  bool is_word_ = false;\n  TrieNode* next_[26] = {0};\n};\n\nclass StreamChecker {\npublic:\n  StreamChecker(vector<string>& words) {\n    root_ = std::make_unique<TrieNode>();\n    for (const string& w : words)\n      root_->reverse_build(w, w.length() - 1);\n  }\n\n  bool query(char letter) {\n    s_ += letter;\n    return root_->reverse_search(s_, s_.length() - 1);    \n  }\n  \nprivate:\n  string s_;\n  unique_ptr<TrieNode> root_;\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"java\">\n\/\/ Author: Huahua, running time: 133 ms\nclass StreamChecker {\n  class TrieNode {\n    public TrieNode() {\n      isWord = false;\n      next = new TrieNode[26];\n    }\n    public boolean isWord;\n    public TrieNode next[];    \n  }\n  \n  private TrieNode root;\n  private StringBuilder sb;\n\n  public StreamChecker(String[] words) {\n    root = new TrieNode();\n    sb = new StringBuilder();\n    for (String word : words) {\n      TrieNode node = root;\n      char[] w = word.toCharArray();\n      for (int i = w.length - 1; i >= 0; --i) {        \n        int idx = w[i] - 'a';\n        if (node.next[idx] == null) node.next[idx] = new TrieNode();\n        node = node.next[idx];\n      }\n      node.isWord = true;\n    }\n  }\n\n  public boolean query(char letter) {\n    sb.append(letter);\n    TrieNode node = root;\n    for (int i = sb.length() - 1; i >= 0; --i) {      \n      int idx = sb.charAt(i) - 'a';\n      if (node.next[idx] == null) return false;\n      if (node.next[idx].isWord) return true;\n      node = node.next[idx];\n    }\n    return false;\n  }  \n}\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>LeetCode 1029 Two City Scheduling Solution1: DP dp[i][j] := min cost to put j people into city A for the first i peopledp[0][0] = 0dp[i][0]&#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":[470,18,96,456],"class_list":["post-5092","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-contest","tag-dp","tag-trie","tag-weekly","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5092","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=5092"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5092\/revisions"}],"predecessor-version":[{"id":5101,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5092\/revisions\/5101"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5092"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5092"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5092"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}