1033. Moving Stones Until Consecutive
Solution: Math
Time complexity: O(1)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua, running time: 4 ms / 8.3 MB class Solution { public: vector<int> numMovesStones(int a, int b, int c) { if (a > c) swap(a, c); if (a > b) swap(a, b); if (b > c) swap(b, c); int u = c - b - 1 + (b - a -1); int l = 0; if (a + 1 == b && b + 1 == c) l = 0; else if (a + 2 >= b || b + 2 >= c) l = 1; else l = 2; return {l, u}; } }; |
1034. Coloring A Border
Solution: DFS
Time complexity: O(mn)
Space complexity: O(mn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua, 52 MB / 12.6 MB class Solution { public: vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) { vector<vector<int>> b(grid.size(), vector<int>(grid[0].size())); dfs(grid, r0, c0, grid[r0][c0], b); for (int i = 0; i < b.size(); ++i) for (int j = 0; j < b[0].size(); ++j) if (b[i][j] > 0) grid[i][j] = color; return grid; } private: bool dfs(const vector<vector<int>>& grid, int r, int c, int color, vector<vector<int>>& b) { if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size()) return true; if (grid[r][c] != color) return true; if (b[r][c]) return false; b[r][c] = -1; bool valid = dfs(grid, r + 1, c, color, b) | dfs(grid, r - 1, c, color, b) | dfs(grid, r, c + 1, color, b) | dfs(grid, r, c - 1, color, b); if (valid) b[r][c] = 1; return false; } }; |
1035. Uncrossed Lines
Solution: LCS
Time complexity: O(nm)
Space complexity: O(mn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua, 12 ms / 12.1 MB class Solution { public: int maxUncrossedLines(vector<int>& A, vector<int>& B) { const int m = A.size(); const int n = B.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); dp[0][0] = 0; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) { if (A[i - 1] == B[j - 1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } return dp[m][n]; } }; |
1036. Escape a Large Maze
Solution: limited search
Time complexity: O(b^2)
Space complexity: O(b^2)
C++
// Author: Huahua, running time: 168 ms, 49.7 MB class Solution { public: bool isEscapePossible(vector>& blocked, vector& source, vector& target) { for (const auto& p : blocked) b.insert(static_cast(p[0]) << 32 | p[1]); seen = 0; t = target; bool first = dfs(source[0], source[1]); t = source; bool second = dfs(target[0], target[1]); return first && second; } private: const static int kMaxN = 1000000; const static int kMaxSeen = 20000; unordered_set b; vector t; int seen; int tx; int ty; bool dfs(int x, int y) { if (x < 0 || y < 0 || x >= kMaxN || y >= kMaxN) return false; if (x == t[0] && y == t[1]) return true; long key = static_cast(x) << 32 | y; if (b.find(key) != b.end()) return false; b.insert(key); if (++seen > kMaxSeen) return true; return dfs(x + 1, y) || dfs(x – 1, y) || dfs(x, y + 1) || dfs(x, y – 1); } };
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment