【LeetCode Hot100】图论篇
前言
本文用于整理LeetCode Hot100中题目解答，因题目比较简单且更多是为了面试快速写出正确思路，只做简单题意解读和一句话题解方便记忆。但代码会全部给出，方便大家整理代码思路。
200. 岛屿数量
一句话题意
求所有上下左右的‘1’的连通块数量。
一句话题解
DFS or BFS 搜一下就行了。
class Solution {int[][] fx = {{1,0},{0,1},{-1,0},{0,-1}};int n;int m;char[][] grid;void dfs(int x,int y){grid[x][y]='0';for(int i=0;i<4;i++){int xx=x+fx[i][0];int yy=y+fx[i][1];if(xx<0||xx>=n||yy<0||yy>=m||grid[xx][yy]=='0')continue;dfs(xx,yy);}}public int numIslands(char[][] grid) {this.grid=grid;int ans=0;n=grid.length;m=grid[0].length;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]=='1'){dfs(i,j);ans++;}}}return ans;}
}994. 腐烂的橘子
一句话题意
给定一个二维数组，二维数组上的每个2为一个烂掉的橘子，1为正常橘子，0为空位。每个坏橘子会每秒向周围四个方向腐烂好的橘子，空位不能传播，问最少多少时间全坏。
一句话题解
多源点广搜，将所有坏的橘子放进去，没搜到一个好的橘子就让他变坏，然后接着搜即可。
class Solution {class Node {int x,y,t;Node(int x,int y,int t){this.x=x;this.y=y;this.t=t;}}public int orangesRotting(int[][] grid) {Queue<Node> q = new LinkedList<>();int ans=0;int sum=0;int n=grid.length;int m=grid[0].length;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(grid[i][j]==2)q.add(new Node(i,j,0));else if(grid[i][j]==1)sum++;}}int[][] fx={{1,0},{0,1},{-1,0},{0,-1}};while(q.size()>0){Node o = q.poll();ans=Math.max(ans,o.t);if(sum==0)continue;for(int i=0;i<4;i++){int xx=o.x+fx[i][0];int yy=o.y+fx[i][1];if(xx<0||xx>=n||yy<0||yy>=m||grid[xx][yy]!=1)continue;grid[xx][yy]=0;sum--;q.add(new Node(xx,yy,o.t+1));}}if(sum!=0)ans=-1;return ans;}
}207. 课程表
一句话题意
给定一些课程的前后学习关系，问是否能全部学习。
一句话题解
拓扑排序。
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> to = new ArrayList<>();int[] in = new int[numCourses];for (int i = 0; i < numCourses; i++)to.add(new ArrayList<>());for (int[] a : prerequisites) {to.get(a[1]).add(a[0]);in[a[0]]++;}Queue<Integer> q = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (in[i] == 0)q.add(i);}while (q.size() > 0) {int x = q.poll();numCourses--;for (Integer y : to.get(x)) {in[y]--;if (in[y] == 0)q.add(y);}}return numCourses == 0;}
}
208. 实现 Trie (前缀树)
一句话题意
请你实现 Trie 类：
-
Trie()初始化前缀树对象。 -
void insert(String word)向前缀树中插入字符串word。 -
boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。 -
boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
一句话题解
实现一棵26岔树。
class Trie {Trie[] children;boolean isEnd;public Trie() {children = new Trie[26];isEnd = false;}public void insert(String word) {Trie node = this;for(char c: word.toCharArray()){if(node.children[c-'a'] == null){node.children[c-'a'] = new Trie();}node = node.children[c-'a'];}node.isEnd = true;}public boolean search(String word) {Trie node = this.searchPrefix(word);return node!=null&&node.isEnd;}public boolean startsWith(String prefix) {return this.searchPrefix(prefix) != null;}public Trie searchPrefix(String s){Trie node = this;for(Character c:s.toCharArray()){if(node.children[c-'a']==null)return null;node=node.children[c-'a'];}return node;}
}