网站的基础建设项目,wordpress 后台演示,上海建设工程安全质量监督站网站,seo外链工具源码代码随想录图论 第三天 | 130. 被围绕的区域 417. 太平洋大西洋水流问题
一、130. 被围绕的区域
题目链接#xff1a;https://leetcode.cn/problems/surrounded-regions/ 思路#xff1a;题目要求沾边的不动#xff0c;只改没沾边的#xff0c;那么可以先dfs遍历4条边https://leetcode.cn/problems/surrounded-regions/ 思路题目要求沾边的不动只改没沾边的那么可以先dfs遍历4条边把沾边的O都改成A。然后直接两层for循环遍历整个数组把O该成X把A改成O。
class Solution {public void solve(char[][] board) {for (int i 0; i board.length; i) {if (board[i][0] O) dfs(board, i, 0);if (board[i][board[0].length-1] O) dfs(board, i, board[0].length-1);}for (int i 0; i board[0].length; i) {if (board[0][i] O) dfs(board, 0, i);if (board[board.length-1][i] O) dfs(board, board.length-1, i);}for (int i 0; i board.length; i) {for (int j 0; j board[0].length; j) {if (board[i][j] O) board[i][j] X;if (board[i][j] A) board[i][j] O;}}}void dfs(char[][] board, int x, int y) {if (x 0 || x board.length || y 0 || y board[0].length || board[x][y] ! O) {return;}board[x][y] A;dfs(board, x-1, y);dfs(board, x1, y);dfs(board, x, y-1);dfs(board, x, y1);}
}二、417. 太平洋大西洋水流问题
题目链接https://leetcode.cn/problems/pacific-atlantic-water-flow/ 思路分别从太平洋和大西洋的边界出发逆流而上进行分开的标记只要某个格子即被太平洋标记又被大西洋标记即可收取。
class Solution {boolean[][][] visited;int[][] nums {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public ListListInteger pacificAtlantic(int[][] heights) {ListListInteger arrayLists new ArrayList();visited new boolean[heights.length][heights[0].length][2];for (int i 0; i heights.length; i) {visited[i][0][0] true;dfs(heights, i, 0, 0);visited[i][heights[0].length-1][1] true;dfs(heights, i, heights[0].length-1, 1);}for (int i 0; i heights[0].length; i) {visited[0][i][0] true;dfs(heights, 0, i, 0);visited[heights.length-1][i][1] true;dfs(heights, heights.length-1, i,1);}for (int i 0; i heights.length; i) {for (int j 0; j heights[0].length; j) {if (visited[i][j][0] visited[i][j][1]) {ListInteger list new ArrayList();list.add(i);list.add(j);arrayLists.add(list);}}}return arrayLists;}void dfs(int[][] heights, int x, int y, int sign) {for (int[] num : nums) {int nX x num[0];int nY y num[1];if (nX 0 || nX heights.length || nY 0 || nY heights[0].length) {continue;}if (visited[nX][nY][sign] || heights[nX][nY] heights[x][y]) continue;visited[nX][nY][sign] true;dfs(heights, nX, nY, sign);}}
}
