濮阳网站优化公司哪家好,江苏省建设局网站证件查询,seo加盟代理,国产做爰全免费的视频网站130. 被围绕的区域
**题目#xff1a;**给你一个 m x n 的矩阵 board #xff0c;由若干字符 ‘X’ 和 ‘O’ #xff0c;找到所有被 ‘X’ 围绕的区域#xff0c;并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。 题目链接#xff1a;130. 被围绕的区域 解题思路#xff1a…130. 被围绕的区域
**题目**给你一个 m x n 的矩阵 board 由若干字符 ‘X’ 和 ‘O’ 找到所有被 ‘X’ 围绕的区域并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。 题目链接130. 被围绕的区域 解题思路在飞地的基础上做改动使用一个栈存储需要改变的节点
class Solution {public int[][] move{{0,1},{0,-1},{1,0},{-1,0}};public boolean[][] visited;public boolean flag;public void solve(char[][] board) {//多一个栈记录要被改变的区域visitednew boolean[board.length][board[0].length];for(int i0;iboard.length;i){for(int j0;jboard[0].length;j){if(!visited[i][j]board[i][j]O){flagfalse;Queueint[] needToChange new LinkedList();bfs(board,i,j,needToChange);if(flagtrue){needToChange.clear();}else{while(!needToChange.isEmpty()){int[] nodeneedToChange.poll();board[node[0]][node[1]]X;}} }}}}public void bfs(char[][] board,int x,int y,Queueint[] needToChange){if(x0||xboard.length-1||y0||yboard[0].length-1){flagtrue;}Queueint[] queuenew LinkedList();queue.offer(new int[]{x,y});needToChange.offer(new int[]{x,y});visited[x][y]true;while(!queue.isEmpty()){int[] nodequeue.poll();for(int p0;p4;p){int nextxnode[0]move[p][0];int nextynode[1]move[p][1];if(nextx0||nextxboard.length||nexty0||nextyboard[0].length){continue;}if(!visited[nextx][nexty]board[nextx][nexty]O){if(nextx0||nextxboard.length-1||nexty0||nextyboard[0].length-1) {flagtrue;}queue.offer(new int[]{nextx,nexty});needToChange.offer(new int[]{nextx,nexty});visited[nextx][nexty]true;}}}}
}417. 太平洋大西洋水流问题
题目有一个 m × n 的矩形岛屿与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界而 “大西洋” 处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。岛上雨水较多如果相邻单元格的高度 小于或等于 当前单元格的高度雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。返回网格坐标 result 的 2D 列表 其中 result[i] [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。 输入: heights [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] 示例 2 输入: heights [[2,1],[1,2]] 输出: [[0,0],[0,1],[1,0],[1,1]] 题目链接417. 太平洋大西洋水流问题 **解题思路**找到哪些点 可以同时到达太平洋和大西洋。 流动的方式只能从高往低流。从太平洋边上的节点 逆流而上将遍历过的节点都标记上。 从大西洋的边上节点 逆流而长将遍历过的节点也标记上。 然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。 代码如下
class Solution {private static final int[][] position {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};/*** 循环遍历超时时可以将需要遍历搜索的点加入队列再进行遍历搜索*/public void bfs(int[][] heights, Queueint[] queue, boolean[][][] visited) {while (!queue.isEmpty()) {int[] curPos queue.poll();for (int[] current: position) {int row curPos[0] current[0], col curPos[1] current[1], sign curPos[2];// 越界if (row 0 || row heights.length || col 0 || col heights[0].length) continue;// 高度不合适或者已经被访问过了if (heights[row][col] heights[curPos[0]][curPos[1]] || visited[row][col][sign]) continue;visited[row][col][sign] true;queue.add(new int[]{row, col, sign});}}}public ListListInteger pacificAtlantic(int[][] heights) {int rowSize heights.length, colSize heights[0].length;ListListInteger ans new ArrayList();boolean[][][] visited new boolean[rowSize][colSize][2];// 队列保存的数据为 [行号, 列号, 标记]// 假设太平洋的标记为 1大西洋为 0Queueint[] queue new ArrayDeque();for (int row 0; row rowSize; row) {visited[row][colSize - 1][0] true;visited[row][0][1] true;queue.add(new int[]{row, colSize - 1, 0});queue.add(new int[]{row, 0, 1});}for (int col 0; col colSize; col) {visited[rowSize - 1][col][0] true;visited[0][col][1] true;queue.add(new int[]{rowSize - 1, col, 0});queue.add(new int[]{0, col, 1});}bfs(heights, queue, visited);for (int row 0; row rowSize; row) {for (int col 0; col colSize; col) {// 如果该位置即可以到太平洋又可以到大西洋就放入答案数组if (visited[row][col][0] visited[row][col][1])ans.add(List.of(row, col));}}return ans;}}
