上传文件的网站,网站设计制作报价图片,免费医院网站源码,家装设计师价格提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣417. 太平洋大西洋水流问题二、力扣827. 最大人工岛三、力扣127. 单词接龙四、力扣841. 钥匙和房间 前言 岛屿问题最容易让人想到BFS或者DFS#xff0… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣417. 太平洋大西洋水流问题二、力扣827. 最大人工岛三、力扣127. 单词接龙四、力扣841. 钥匙和房间 前言 岛屿问题最容易让人想到BFS或者DFS但是这道题还真的没有必要别把简单问题搞复杂了
一、力扣417. 太平洋大西洋水流问题
class Solution {int[][] arr new int[][]{{0,1},{0,-1},{-1,0},{1,0}};boolean[][][] flag;public ListListInteger pacificAtlantic(int[][] heights) {int m heights.length, n heights[0].length;flag new boolean[m][n][2];ListListInteger res new ArrayList();for(int i 0; i m; i ){if(!flag[i][0][0]){dfs(heights,i,0,0);}if(!flag[i][n-1][1]){dfs(heights,i,n-1,1);}}for(int i 0; i n; i ){if(!flag[0][i][0]){dfs(heights,0,i,0);}if(!flag[m-1][i][1]){dfs(heights,m-1,i,1);}}for(int i 0; i m; i ){for(int j 0; j n; j ){if(flag[i][j][0] flag[i][j][1]){res.add(new ArrayList(Arrays.asList(i,j)));}}}return res;}public void dfs(int[][] heights, int x, int y, int sign){flag[x][y][sign] true;for(int i 0; i 4; i ){int curX x arr[i][0];int curY y arr[i][1];if(curX 0 || curX heights.length || curY 0 || curY heights[0].length){continue;}if(!flag[curX][curY][sign] heights[curX][curY] heights[x][y]){dfs(heights,curX,curY,sign);}}}
}二、力扣827. 最大人工岛
class Solution {int[][] arr new int[][]{{1,0},{-1,0},{0,1},{0,-1}};int count;public int largestIsland(int[][] grid) {MapInteger,Integer map new HashMap();int flag 2;int res Integer.MIN_VALUE;int m grid.length, n grid[0].length;for(int i 0; i m; i ){for(int j 0; j n; j ){if(grid[i][j] 1){count 1;grid[i][j] flag;dfs(grid,i,j,flag);map.put(flag,count);flag ;}}}for(int i 0; i m; i ){for(int j 0; j n; j ){if(grid[i][j] 0){SetInteger set new HashSet();int sum 0;for(int k 0; k 4; k ){int curX i arr[k][0];int curY j arr[k][1];if(curX 0 || curX m || curY 0 || curY n){continue;}if(set.contains(grid[curX][curY]) || !map.containsKey(grid[curX][curY])){continue;}sum map.get(grid[curX][curY]);set.add(grid[curX][curY]);}res Math.max(res,sum);}}}return res Integer.MIN_VALUE ? m * n : res1;}public void dfs(int[][] grid, int x, int y,int flag){for(int i 0; i 4; i){int curX x arr[i][0];int curY y arr[i][1];if(curX 0 || curX grid.length || curY 0 || curY grid[0].length){continue;}if(grid[curX][curY] 1){count ;grid[curX][curY] flag;dfs(grid,curX,curY,flag);}}}
}三、力扣127. 单词接龙
class Solution {public int ladderLength(String beginWord, String endWord, ListString wordList) {DequeString deq new LinkedList();int res 1;MapString,Boolean map new HashMap();for(String s : wordList){map.put(s,false);}if(wordList.size() 0 || !map.containsKey(endWord)){return 0;}deq.offerLast(beginWord);while(!deq.isEmpty()){int size deq.size();for(int j 0; j size; j ){String cur deq.pollFirst();for(int i 0; i wordList.size(); i ){String next wordList.get(i);if(!map.get(next) fun(cur,next)){if(next.equals(endWord)){return res1;}map.put(next,true);deq.offerLast(next);}}}res ;}return 0;}public boolean fun(String cur, String next){int dif 0;for(int i 0; i cur.length(); i ){if(cur.charAt(i) ! next.charAt(i)){dif ;}if(dif 2){return false;}}if(dif 0){return false;}return true;}
}四、力扣841. 钥匙和房间
class Solution {public boolean canVisitAllRooms(ListListInteger rooms) {MapInteger,Boolean map new HashMap();for(int i 0; i rooms.size(); i ){map.put(i,false);}map.put(0,true);DequeInteger deq new LinkedList();deq.offerLast(0);while(!deq.isEmpty()){int size deq.size();for(int i 0; i size; i){int cur deq.pollFirst();for(int j 0; j rooms.get(cur).size(); j ){if(!map.get(rooms.get(cur).get(j))){deq.offerLast(rooms.get(cur).get(j));map.put(rooms.get(cur).get(j),true);}}}}for(Map.EntryInteger,Boolean entrys: map.entrySet()){if(!entrys.getValue()){return false;}}return true;}
}
