200 岛屿数量题目给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。classSolution{publicstaticint[][]path{{0,1},{1,0},{-1,0},{0,-1}};publicintnumIslands(char[][]grid){intmgrid.length;intngrid[0].length;boolean[][]visitednewboolean[m][n];intans0;for(inti0;im;i){for(intj0;jn;j){if(!visited[i][j]grid[i][j]1){ans;visited[i][j]true;dfs(visited,i,j,grid);}}}returnans;}privatevoiddfs(boolean[][]visited,intx,inty,char[][]grid){for(inti0;i4;i){intnextxxpath[i][0];intnextyypath[i][1];if(nextx0||nexty0||nextxgrid.length||nextygrid[0].length)continue;if(!visited[nextx][nexty]grid[nextx][nexty]1){visited[nextx][nexty]true;dfs(visited,nextx,nexty,grid);}}}}994 腐烂的橘子题目在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。每分钟腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。classSolution{privatestaticfinalint[][]directions{{-1,0},{1,0},{0,-1},{0,1}};publicintorangesRotting(int[][]grid){intmgrid.length;intngrid[0].length;intfresh0;Listint[]qnewArrayList();for(inti0;im;i){for(intj0;jn;j){if(grid[i][j]1){fresh;}elseif(grid[i][j]2){q.add(newint[]{i,j});}}}intans0;while(fresh0!q.isEmpty()){ans;Listint[]tmpq;qnewArrayList();for(int[]pos:tmp){for(int[]d:directions){intipos[0]d[0];intjpos[1]d[1];if(i0imj0jngrid[i][j]1){fresh--;grid[i][j]2;q.add(newint[]{i,j});}}}}returnfresh0?-1:ans;}}207课程表题目你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则必须先学习课程 bi 。例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1。请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。classSolution{publicbooleancanFinish(intnumCourses,int[][]prerequisites){ListInteger[]gnewArrayList[numCourses];Arrays.setAll(g,i-newArrayList());for(int[]p:prerequisites){g[p[1]].add(p[0]);}int[]colorsnewint[numCourses];for(inti0;inumCourses;i){if(colors[i]0dfs(i,g,colors)){returnfalse;}}returntrue;}privatebooleandfs(intx,ListInteger[]g,int[]colors){colors[x]1;for(inty:g[x]){if(colors[y]1||colors[y]0dfs(y,g,colors)){returntrue;}}colors[x]2;returnfalse;}}208实现前缀树题目Trie发音类似 “try”或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。请你实现 Trie 类Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。classTrie{privatestaticclassNode{Node[]sonnewNode[26];booleanendfalse;}privatefinalNoderootnewNode();publicTrie(){}publicvoidinsert(Stringword){Nodecurroot;for(charc:word.toCharArray()){c-a;if(cur.son[c]null){// 无路可走cur.son[c]newNode();// new 出来}curcur.son[c];}cur.endtrue;}publicbooleansearch(Stringword){returnfind(word)2;}publicbooleanstartsWith(Stringprefix){returnfind(prefix)!0;}privateintfind(Stringword){Nodecurroot;for(charc:word.toCharArray()){c-a;if(cur.son[c]null){return0;}curcur.son[c];}returncur.end?2:1;// 走过同样的路2完全匹配1前缀匹配}}