网格DFS通用板子，类似二叉树的DFS：

void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    
    grid[r][c] = 2; // 将格子标记为「已遍历过」
    
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        	&& 0 <= c && c < grid[0].length;
}

岛屿数量

循环访问每个点（i，j），递归DFS用以将某片岛屿全部表记为访问过。

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    //dfs的目标是深度搜索删除这个岛屿
    public void dfs(char[][] g, int i, int j){
        if(i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] == '0') return;
        g[i][j] = '0';
        dfs(g, i + 1, j);
        dfs(g, i, j + 1);
        dfs(g, i - 1, j);
        dfs(g, i, j - 1);
    }
}

腐烂的橘子

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。翻译一下，实际上就是求腐烂橘子到所有新鲜橘子的最短路径。 用层序的BFS，每一层向外迭代，round++，即时间+1。

class Solution {
    int cnt = 0; // 正常的橘子数
    Queue<int[]> q = new LinkedList<>();
    int m;
    int n;
    public int orangesRotting(int[][] grid) {
        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) cnt++;
                if(grid[i][j] == 2){
                    q.add(new int[]{i, j});
                }
            }
        }
        int time = 0;
        // 当队列为空时终止循环
        while(cnt > 0 && !q.isEmpty()){
            time++;
            int n = q.size();
            for(int i = 0; i < n; i++){
                int[] orange = q.poll();
                int x = orange[0];
                int y = orange[1];
                handle(grid, x, y);
            }
        }
        if(cnt > 0) return -1;
        else return time;

    }
    public void handle(int[][] grid, int x, int y){
        if(x >= 1 && grid[x-1][y] == 1){
            grid[x-1][y] = 2;
            cnt--;
            q.add(new int[]{x-1, y});
        }
        if(x + 1 < m && grid[x+1][y] == 1){
            grid[x+1][y] = 2;
            cnt--;
            q.add(new int[]{x+1, y});
        }
        if(y >= 1 && grid[x][y-1] == 1){
            grid[x][y-1] = 2;
            cnt--;
            q.add(new int[]{x, y-1});
        }
        if( y + 1 < n && grid[x][y+1] == 1){
            grid[x][y+1] = 2;
            cnt--;
            q.add(new int[]{x, y+1});
        }
    }
}

课程表

拓扑排序，关键是维护一个入度数组（入度表示课程的依赖情况，如果某个课入度为0，说明前置课程修完了，或者没有前置课程需要修）和一个哈希表（key为课程序号，value为该课程的后置课程集合），用BFS的思路迭代。维护一个队列，队列中的元素为入度为0的课程。每次迭代取出一个入度为0的课（表示这门课修完了），并维护其后置课程（后置课程的入度-1），记录修完课程的数量，最后对比数量得出返回值。

• 初始化的队列，入度数组、哈希表
• 将所有课加入哈希表，维护这些课的后置课
• 将入度为0的课加入队列
• 开始BFS迭代，取出入度为0的课，并维护它们的后置课入度

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 入度数组，用于记录每门课程的入度
        int[] inDegree = new int[numCourses];
        // 哈希表 key为当前课程序号 value为当前课程的后续课程数组
        Map<Integer, List<Integer>> m = new HashMap<>();
        for(int i = 0; i < numCourses; i++){
            m.put(i, new ArrayList<Integer>());
        }
        // 计算每门课程的入度，并构建哈希
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];   // 当前课
            int preCourse = prerequisite[1]; // 当前课的前置课
            inDegree[course]++; // 前置课的后续课是当前课 
            m.get(preCourse).add(course);
        }
        // 存入入度为0的课
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                // 入度为0 可以直接存入数组
                q.add(i);
            }
        }
        int cnt = 0; // 记录已经完成的课
        while(!q.isEmpty()){
            int c = q.poll();
            cnt++;
            // 寻找当前这门课的后续课程 后续课程的入度-1
            List<Integer> l = m.get(c);
            for(Integer x:l){
                inDegree[x]--;
                // 减完后入度为0 直接添加到队列里面
                if(inDegree[x] == 0){
                    q.add(x);
                }
            }
        }
        return cnt == numCourses;

    }
}

实现前缀树

前缀树是一种特殊的多叉树，它的 TrieNode 中 chidren 是一个大小为 26 的一维数组，分别对应了26个英文字符 ‘a’ ~ ‘z’，也就是说形成了一棵 26叉树。

前缀树的结构里面存储了两个信息：

• isWord 表示从根节点到当前节点为止，该路径是否形成了一个有效的字符串
• children 是该节点的所有子节点。

在构建前缀树的时候，按照下面的方法：

• 根节点不保存任何信息；
• 关键词放到「前缀树」时，需要把它拆成各个字符，每个字符按照其在 ‘a’ ~ ‘z’ 的序号，放在对应的 chidren 里面。下一个字符是当前字符的子节点。
• 一个输入字符串构建「前缀树」结束的时候，需要把该节点的 isWord 标记为 true，说明从根节点到当前节点的路径，构成了一个关键词。

class Trie {
    public Trie[] children;
    public boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.children[index] == null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = this;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int index = c - 'a';
            if(node.children[index] == null) return false;
            node = node.children[index];
        }
        if(node.isEnd == false) return false;
        else return true;
    }
    
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.isEmpty()) return false;
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            int index = c - 'a';
            if (node.children[index] == null) return false;
            node = node.children[index];
        }
        return true;  // 只要前缀路径存在即可
    }
}