{"id":5114,"date":"2019-04-27T22:42:58","date_gmt":"2019-04-28T05:42:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5114"},"modified":"2019-04-27T22:45:26","modified_gmt":"2019-04-28T05:45:26","slug":"leetcode-weekly-contest-134","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-weekly-contest-134\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode Weekly Contest 134 (1033,1034,1035,1036)"},"content":{"rendered":"\n

1033. Moving Stones Until Consecutive<\/strong><\/h2>\n\n\n\n

Solution: Math<\/p>\n\n\n\n

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

\n

C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua, running time: 4 ms \/ 8.3 MB\nclass Solution {\npublic:\n  vector numMovesStones(int a, int b, int c) {\n    if (a > c) swap(a, c);\n    if (a > b) swap(a, b);\n    if (b > c) swap(b, c);\n    int u = c - b - 1 + (b - a -1);\n    int l = 0;\n    if (a + 1 == b && b + 1 == c) l = 0;\n    else if (a + 2 >= b || b + 2 >= c) l = 1;\n    else l = 2;\n    return {l, u};\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
1034. Coloring A Border<\/strong>
<\/h2>\n\n\n\n
Solution: DFS<\/p>\n\n\n\n
Time complexity: O(mn)
Space complexity: O(mn)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua, 52 MB \/ 12.6 MB\nclass Solution {\npublic:\n  vector> colorBorder(vector>& grid, int r0, int c0, int color) {\n    vector> b(grid.size(), vector(grid[0].size()));\n    dfs(grid, r0, c0, grid[r0][c0], b);\n    for (int i = 0; i < b.size(); ++i)\n      for (int j = 0; j < b[0].size(); ++j)\n        if (b[i][j] > 0) grid[i][j] = color;\n    return grid;\n  }\nprivate:\n  bool dfs(const vector>& grid, int r, int c, int color, vector>& b) {\n    if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size()) return true;\n    if (grid[r][c] != color) return true;\n    if (b[r][c]) return false;\n    b[r][c] = -1;\n    bool valid = dfs(grid, r + 1, c, color, b) |\n                 dfs(grid, r - 1, c, color, b) | \n                 dfs(grid, r, c + 1, color, b) |\n                 dfs(grid, r, c - 1, color, b);\n    if (valid) b[r][c] = 1;\n    return false;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
1035. Uncrossed Lines<\/strong>
<\/h2>\n\n\n\n
Solution: LCS<\/p>\n\n\n\n
Time complexity: O(nm)
Space complexity: O(mn)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua, 12 ms \/ 12.1 MB\nclass Solution {\npublic:\n  int maxUncrossedLines(vector& A, vector& B) {\n    const int m = A.size();\n    const int n = B.size();\n    vector> dp(m + 1, vector(n + 1));\n    dp[0][0] = 0;\n    for (int i = 1; i <= m; ++i)\n      for (int j = 1; j <= n; ++j) {        \n        if (A[i - 1] == B[j - 1]) \n          dp[i][j] = dp[i-1][j-1] + 1;\n        else\n          dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);\n      }\n    return dp[m][n];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
1036. Escape a Large Maze<\/strong><\/h2>\n\n\n\n
Solution: limited search<\/p>\n\n\n\n
Time complexity: O(b^2)
Space complexity: O(b^2)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n\/\/ Author: Huahua, running time: 168 ms, 49.7 MB\nclass Solution {\npublic:\n  bool isEscapePossible(vector>& blocked, vector& source, vector& target) {        \n    for (const auto& p : blocked)\n      b.insert(static_cast(p[0]) << 32 | p[1]);\n    seen = 0;\n    t = target;\n    bool first = dfs(source[0], source[1]);\n    t = source;\n    bool second = dfs(target[0], target[1]);\n    return first && second;\n  }\nprivate:\n  const static int kMaxN = 1000000;\n  const static int kMaxSeen = 20000;\n  unordered_set b;\n  vector t;\n  int seen;\n  int tx;\n  int ty;\n  \n  bool dfs(int x, int y) {\n    if (x < 0 || y < 0 || x >= kMaxN || y >= kMaxN) return false;\n    if (x == t[0] && y == t[1]) return true;\n    long key = static_cast(x) << 32 | y;\n    if (b.find(key) != b.end()) return false;    \n    b.insert(key);\n    if (++seen > kMaxSeen) return true;    \n    return dfs(x + 1, y) ||\n           dfs(x - 1, y) ||\n           dfs(x, y + 1) ||\n           dfs(x, y - 1);\n  }\n};\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
1033. Moving Stones Until Consecutive Solution: Math Time complexity: O(1)Space complexity: O(1) \/\/ Author: Huahua, running time: 4 ms \/ 8.3 MB class Solution {…<\/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,439],"class_list":["post-5114","post","type-post","status-publish","format-standard","hentry","category-leetcode","tag-leetcode","tag-weekly-contest","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5114","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=5114"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5114\/revisions"}],"predecessor-version":[{"id":5117,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5114\/revisions\/5117"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5114"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5114"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5114"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}