hot100之图论

岛屿数量(200)

class Solution {
 
 public int numIslands(char[][] grid) {
 int res = 0;
 int m = grid.length;
 int n = grid[0].length;
 for (int i = 0; i < m ; i++){
 for (int j = 0; j < n; j++){
 if (grid[i][j] == '1'){
 res+=1;
 markLand(grid, i, j);
 }
 
 }
 }
 return res;
 }
 private void markLand(char[][] grid, int i, int j){
 if (i < 0 || i > grid.length-1 || j < 0 || j > grid[0].length-1 || grid[i][j] == '0'){
 return ;
 }
 grid[i][j] = '0';
 markLand(grid, i+1, j);
 markLand(grid, i-1, j);
 markLand(grid, i, j+1);
 markLand(grid, i, j-1);
 }
}

• 分析

简单的四向寻找

腐烂的橘子(994)

class Solution {
 private static final int[][] DIRECTIONS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
 public int orangesRotting(int[][] grid) {
 int res = 0;
 int fresh = 0;
 int m = grid.length;
 int n = grid[0].length;
 Deque<int []> rotArray = new ArrayDeque<>();
 
 for (int i = 0; i < m; i++){
 for (int j = 0; j < n; j++){
 if (grid[i][j] == 1) fresh++;
 else if (grid[i][j] == 2) rotArray.addFirst(new int[] {i, j});
 }
 }
 while (fresh > 0 && !rotArray.isEmpty()){
 res+=1;
 int len = rotArray.size();
 for (int i = 0; i < len; i++){
 int[] temp = rotArray.removeLast();
 for (int[] dir : DIRECTIONS){
 int row = temp[0] + dir[0];
 int col = temp[1] + dir[1];
 if (0 <= row && row < m && 0 <= col && col < n 
	 && grid[row][col] == 1){
 fresh--;
 grid[row][col] = 2;
 rotArray.addFirst(new int[] {row, col});
 }
 }
 }
 }
 return fresh>0 ? -1 : res;
 }
}

• 分析

相比于普通的四向寻找, 难点在于轮次, 可以类比于二叉树的层序遍历, 一层一层扩展

课程表(207)

class Solution {
 public boolean canFinish(int numCourses, int[][] prerequisites) {
 List<Integer>[] line = new ArrayList[numCourses];
 Arrays.setAll(line, i -> new ArrayList<>());
 for (int[] p : prerequisites){
 line[p[1]].add(p[0]);
 }
 int[] colors = new int[numCourses];
 for (int i = 0; i < numCourses; i++){
 if (colors[i] == 0 && dfs(i, colors, line)) return false;
 }
 
 return true;
 }
 private boolean dfs(int i, int[] colors, List<Integer>[] line){
 colors[i] = 1;
 for (int j : line[i]){
 if (colors[j] == 1 || colors[j] == 0 && dfs(j, colors, line)){
 return true;
 }
 }
 colors[i] = 2;
 return false;
 }
}

• 分析

判断图中是否有环

利用三色标记法 {0, 1, 2} →{未达, 正在使用, 可达}

实现Tire(208)

代码太长了就不放了

 private static class Node {
 Node[] son = new Node[26];
 boolean end;
 }
 private final Node root;

• 分析

insert() 部分 实际上是开辟道路 if (curr.son[c] == null) curr.son[c] = new Node();

search() 和 startsWith() 实际上都是一路沿son下移, 遇到没开辟完的路线 return false

如果移动结束了, 如果当前节点的end == true 则为完整单词 , 否则为前缀