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)