岛屿数量(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  grid.length-1 || 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 rotArray = new ArrayDeque();
        
        for (int i = 0; i  0 && !rotArray.isEmpty()){
            res+=1;
            int len = rotArray.size();
            for (int i = 0; i 0 ? -1 : res;
    }
}

• 分析

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

课程表(207)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List[] 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 [] 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 则为完整单词 , 否则为前缀