AMGE’s Blogger

Leetcode 網址: https://leetcode.com/problems/n-queens/ 題目說明: 知名的 n 皇后問題，請找出 n 皇后的所有解。 解題說明: 使用 DFS 去窮舉出所有 n 皇后的解。 程式碼 class Solution { public: int flag[9] = {0}; vector<vector<string>> answers; bool isValid(vector<string>& board, int row, int col) { for (int i = 0; i < 9 && flag[i]; i++) { if (flag[i] == col) return false; if (flag[i] + i == row + col) return false; if (row - i == col - flag[i]) return false; } return true; } vector<vector<string>> solveNQueens(int n) { vector<string> board(n, string(n, '.')); dfs(board, 0, n); return answers; } void dfs(vector<string>& board, int row, int n) { if (row == n) { answers.push_back(board); return; } for (int i = 0; i < n; i++) { if (!isValid(board, row, i + 1)) continue; ...

Leetcode 網址: https://leetcode.com/problems/smallest-string-starting-from-leaf/ 題目說明: 給定一個 Binary Tree，從這個 Binary Tree 中找出從 Leaf 到 Root 最小的單字 (最小的單字意味者字典排序， a -> z，短到長) 解題說明: 這題很直觀，就是直接從 Binary Tree 的 Root 訪問到 Leaf， 最後到 Leaf 之後再去依照字典排序比較要保留哪個單字， 途中保存 Node 的方式可以使用 vector ，亦或者是使用 string， 由於只需要訪問所有的 Node，所以這題的時間複雜度是 O (n)， 而因為我們始終只保留最短的單字，所以空間複雜度是 O (n)。 程式碼 class Solution { public: string answer; string smallestFromLeaf(TreeNode* root) { answer = ""; vector<int> nodes; if (root) traverseTree(root, nodes); return answer; } void updateAnswer(vector<int>& nodes) { bool flag = true; int length = answer.length(); for (int i = nodes.size() - 1, j = 0; i >= 0 && j < length && flag; i--, j++) { if (nodes[i] < (answer[j] - 'a')) break; if (nodes[i] > (answer[j] - 'a')) flag = false; } if (flag) { a...

Leetcode 網址: https://leetcode.com/problems/regions-cut-by-slashes/ 題目說明: 這題跟 LeetCode 1254 非常像，給定 Grid 以及其邊線， 要找尋這些邊線切出來的 Region 總共有幾塊。 解題說明: 因為是找 Region 數量問題，所以方向很直覺就是藉由 DFS 去訪問， 不過這題比較不同的是，他給你的 Grid 是包含 "邊線" 而非 "'障礙物"， 意思也就是追要把這個 Grid 先轉換成 DFS 能 Traverse 的 Grid， 觀察題目給的幾個範例後，一開始想說把 Grid 放大成二倍， 結果遇到這個情況會過不了: ["//", "/ "]， 放大 2 倍的 Grid: 01 0 1 1010 0100 1000 也就是說，因為只有 2 倍大的 Grid 空間不夠，進而造成連續二個 // 形成一個不存在的 region， 所以發現問題之後，嘗試改成 3 倍大確認跟預期的 Grid 無誤後 Submit 即 AC 了。 放大 3 倍的 Grid: 001001 010010 100100 001000 010000 100000 程式碼 class Solution { public: int count; void traverseIsland(vector<vector<int>>& grid, int x, int y) { if (y < 0 || x < 0 || y >= grid.size() || x >= grid[0].size()) return; if (grid[y][x]) return; grid[y][x] = count; traverseIsland(grid, x - 1, y); traverseIsland(grid, x + 1, y); traverseIsland(grid, x, y - 1); return traverseIsland(gri...

Leetcode 網址: https://leetcode.com/problems/number-of-closed-islands/ 題目說明: 題目大意是要從一個二維地圖中，找出所有"完全被海包圍的陸地"， 如果陸地在地圖邊界，則不算 "完全被海包圍的陸地"。 解題說明: 這題很直覺，我們就是直接藉由 DFS 去訪問那些陸地， 如果訪問陸地途中碰到邊界，則代表該陸地沒有完全被海包圍， 如果訪問完連續的陸地也沒碰到邊界，則代表該陸地有完全被海包圍。 程式碼 class Solution { public: bool traverseIsland(vector<vector<int>>& grid, int x, int y) { if (y < 0 || x < 0 || y >= grid.size() || x >= grid[0].size()) return false; if (grid[y][x]) return true; grid[y][x] = 1; bool isClosedIsland = traverseIsland(grid, x - 1, y); isClosedIsland = isClosedIsland & traverseIsland(grid, x + 1, y); isClosedIsland = isClosedIsland & traverseIsland(grid, x, y - 1); return isClosedIsland & traverseIsland(grid, x, y + 1); } int closedIsland(vector<vector<int>>& grid) { int count = 0, width = grid[0].size(), height = grid.size(); for (int i = 0; i < height; i++) ...