solution

1. BFS

(1) 层序遍历

void levelOrderTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // 记录当前遍历到的层数（根节点视为第 1 层）
    int depth = 1;

    while (!q.isEmpty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            // 访问 cur 节点，同时知道它所在的层数
            System.out.println("depth = " + depth + ", val = " + cur.val);

            // 把 cur 的左右子节点加入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
        depth++;
    }
}

(2) 最短路径

输入：

3 3

0 0 0

1 1 0

0 0 0

输出：

4

    // 四个方向
    private static final int[][] DIRS = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };

    private static int bfs(int[][] grid, int m, int n) {
        // 起点或终点是障碍
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
            return -1;
        }
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        // 起点加入队列
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 一层一层遍历
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                // 到达终点
                if (x == m - 1 && y == n - 1) {
                    return step;
                }
                // 四个方向
                for (int[] dir : DIRS) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    // 边界检查
                    if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                        continue;
                    }
                    // 障碍物
                    if (grid[nx][ny] == 1) {
                        continue;
                    }
                    // 已访问
                    if (visited[nx][ny]) {
                        continue;
                    }
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny});
                }
            }
            step++;
        }
        return -1;
    }

(3) 岛屿数量 (bfs感染整个岛屿)

import java.util.*;

public class Main {

    private static final int[][] DIRS = {
            {1, 0},
            {-1, 0},
            {0, 1},
            {0, -1}
    };

    public static int numIslands(char[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        boolean[][] visited =
                new boolean[m][n];

        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1'
                        && !visited[i][j]) {
                    bfs(grid, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private static void bfs(char[][] grid,
                            boolean[][] visited,
                            int x,
                            int y) {
        Queue<int[]> queue =
                new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : DIRS) {
                int nx = cur[0] + dir[0];
                int ny = cur[1] + dir[1];

                if (nx < 0
                        || nx >= grid.length
                        || ny < 0
                        || ny >= grid[0].length) {

                    continue;
                }

                if (grid[nx][ny] == '0'
                        || visited[nx][ny]) {
                    continue;
                }
                visited[nx][ny] = true;
                queue.offer(new int[]{nx, ny});
            }
        }
    }
}

(4) 词语接龙

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

输出：5（hit -> hot -> dot -> dog -> cog）

每次只能改动一次

import java.util.*;

public class Main {

    public int ladderLength(String beginWord,
                            String endWord,
                            List<String> wordList) {

        Set<String> dict =
                new HashSet<>(wordList);

        if (!dict.contains(endWord)) {
            return 0;
        }

        Queue<String> queue =
                new LinkedList<>();
        queue.offer(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                if (word.equals(endWord)) {
                    return step;
                }
                char[] chars = word.toCharArray();
                for (int j = 0;
                     j < chars.length;
                     j++) {
                    char old = chars[j];
                    for (char c = 'a';
                         c <= 'z';
                         c++) {
                        chars[j] = c;
                        String next = new String(chars);
                        if (dict.contains(next)
                                && !visited.contains(next)) {
                            visited.add(next);
                            queue.offer(next);
                        }
                    }
                    chars[j] = old;
                }
            }

            step++;
        }

        return 0;
    }
}

2. DFS

(1) 二叉树前中后序遍历

// 基本的二叉树节点
class TreeNode {
    int val;
    TreeNode left, right;
}

// 二叉树的递归遍历框架
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    //前
    traverse(root.left);
    /中
    traverse(root.right);
    //后
}

(2) 查找二叉树第k小值

public int kthSmallest(TreeNode root, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    dfs(root, minHeap);                 // 遍历整棵树，所有值入堆
    for (int i = 1; i < k; i++) minHeap.poll();
    return minHeap.poll();
}
private void dfs(TreeNode node, PriorityQueue<Integer> heap) {
    if (node == null) return;
    heap.offer(node.val);
    dfs(node.left, heap);
    dfs(node.right, heap);
}

(3) 全排列

import java.util.*;

public class Main {

    List<List<Integer>> result =
            new ArrayList<>();

    List<Integer> path =
            new ArrayList<>();

    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {

        used = new boolean[nums.length];

        dfs(nums);

        return result;
    }

    private void dfs(int[] nums) {

        // 一个排列完成
        if (path.size() == nums.length) {

            result.add(new ArrayList<>(path));

            return;
        }

        for (int i = 0; i < nums.length; i++) {

            if (used[i]) {

                continue;
            }

            // 做选择
            path.add(nums[i]);

            used[i] = true;

            dfs(nums);

            // 撤销选择
            path.remove(path.size() - 1);

            used[i] = false;
        }
    }
}

(4) 二叉树路径和等于某值

import java.util.*;

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Main {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(
            TreeNode root,
            int targetSum) {
        dfs(root, targetSum);
        return result;
    }

    private void dfs(TreeNode node,
                     int remain) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        remain -= node.val;
        // 叶子节点
        if (node.left == null
                && node.right == null
                && remain == 0) {
            result.add(new ArrayList<>(path));
        }
        dfs(node.left, remain);
        dfs(node.right, remain);
        // 回溯
        path.remove(path.size() - 1);
    }
}

3. DP动态规划

(1) 打家劫舍问题

public class Main {

    public int rob(int[] nums) {

        int n = nums.length;

        if (n == 1) {

            return nums[0];
        }
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }
}

(2) 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}