栈

常规模板：剑指 Offer II 036. 后缀表达式 (opens new window)

class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();

        for (String s : tokens) {
            // 遍历字符依次入栈，遇到符号就将栈顶的两个元素出栈进行计算，然后将计算结果再入栈
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int op1 = stack.pop();
                int op2 = stack.pop();
                int res = 0;
                switch (s) {
                    case "+":
                        res = op2 + op1;
                        break;
                    case "-":
                        res = op2 - op1;
                        break;
                    case "*":
                        res = op2 * op1;
                        break;
                    case "/":
                        res = op2 / op1;
                        break;
                }
                stack.push(res);
            } 
            // 如果栈为空 or s 是数字的话，直接入栈
            else {
                stack.push(new Integer(s));
            }
        }

        // 栈中的最后一个元素就是最终结果
        return stack.pop();
    }
}

单调栈：剑指 Offer II 038. 每日温度 (opens new window)

class Solution {
    public int[] dailyTemperatures(int[] T) {
        if (T == null || T.length == 0) {
            return new int[0];
        }

        int[] res = new int[T.length];
		
        // 单调递减栈
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < T.length; i ++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                res[stack.peek()] = i - stack.peek();
                stack.pop();
            }
            stack.push(i);
        }

        return res;
    }
}

队列

常规模板：TODO

单调队列：239. 滑动窗口最大值 (opens new window)

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        ......

        for (int i = 0; i < nums.length; i ++) {
            // 当前元素 > 队尾元素，则将队尾元素依次出队
            while (!qmax.isEmpty() && nums[i] > nums[qmax.peekLast()]) {
                qmax.pollLast();
            }
            // 再将当前元素从队尾入队
            qmax.addLast(i);

            // 栈顶元素过期, 则将其出队
            if (qmax.peekFirst() == i - k) {
                qmax.pollFirst();
            }

            // 队头就是当前窗口的最大元素
            if (i >= k - 1) {
                res[index ++] = nums[qmax.peekFirst()];
            }
        }

        return res;
    }
}

堆：剑指 Offer II 076. 数组中的第 k 大的数字 (opens new window)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int i = 0; i < nums.length; i ++) {
            // 如果最小堆中元素的数目还小于 k，那么直接将它添加到最小堆中
            if (minHeap.size() < k) {
                minHeap.offer(nums[i]);
            }
            // 如果最小堆中已经有k个元素，那么将其和位于堆顶的最小值进行比较。
            // 如果新的数字大于堆顶的数字，那么堆顶的数字就是第 k + 1 大的数字，可以将它从堆中删除，并将新的数字添加到堆中，这样堆中保存的仍然是到目前为止从数据流中读出的最大的 k 个数字，此时第 k 大的数字正好位于最小堆的堆顶
            else {
                if (nums[i] > minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(nums[i]);
                }
                // else if (nums[i] < minHeap.peek()) 
                // 如果新读出的数字小于或等于堆中的最小值，没有插入的必要
                // 因为堆中的 k 个数字都比 val 大，因此 val 不可能是 k 个最大的数字中的一个
            }
            
        }

        return minHeap.peek();
    }
}

二叉树

先序遍历：144. 二叉树的前序遍历 (opens new window)

递归：

class Solution {
    private List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }
	
        res.add(root.val);
        inorderTraversal(root.left);
        inorderTraversal(root.right);

        return res;
    }
}

迭代：

class Solution {

    private List<Integer> res = new ArrayList<>();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                res.add(cur.val);
                cur = cur.left;
            }

            cur = stack.pop();
            cur = cur.right;
        }

        return res;
    }
}

中序遍历：94. 二叉树的中序遍历 (opens new window)

递归

class Solution {
    private List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }

        inorderTraversal(root.left);
        res.add(root.val);
        inorderTraversal(root.right);

        return res;
    }
}

迭代：

class Solution {
    private List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            res.add(cur.val);

            cur = cur.right;
        }

        return res;
    }
}

后序遍历：145. 二叉树的后序遍历 (opens new window)

递归：

class Solution {
    private List<Integer> res = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }
	
        inorderTraversal(root.left);
        inorderTraversal(root.right);
        res.add(root.val);

        return res;
    }
}

迭代：

class Solution {
    private List<Integer> res = new ArrayList<>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 存储当前读取到的节点的前一个节点
        TreeNode pre = null;

        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left; // 1.往左走
            } 

            // 如果当前到达的节点 cur 有右子节点并且右子节点不是前一个遍历的节点，则表示它有右子树并且右子树还没有遍历过
            // 按照后序遍历的顺序，应该先遍历它的右子树，因此把变量 cur 指向它的右子节点
            cur = stack.peek();
            if (cur.right != null && cur.right != pre) {
                cur = cur.right; // 2. 往右走
            }
            // 如果变量 cur 指向的节点没有右子树或它的右子树已经遍历过，则按照后序遍历的顺序此时可以读取这个节点，于是把它出栈并读取它
            else {
                stack.pop();
                res.add(cur.val); // 3. 读取当前节点

                // 在准备读取下一个节点之前，把 pre 指向当前读取的节点
                pre = cur;
                // 下一个读取的节点一定是 cur 的父节点，而父节点之前已经存放到栈中，所以将变量 cur 重置为 null 就行了
                cur = null;
            }

        }

        return res;
    }
}

层次遍历：102. 二叉树的层序遍历 (opens new window)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>(); // 存储遍历结果
        Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列

        if (root == null) {
            return res;
        }

        queue.offer(root); // 根节点入队
        while (!queue.isEmpty()) {
            List<Integer> line = new ArrayList<>(); // 存储每层的节点
            int sz = queue.size();
            // 遍历当前层
            for (int i = 0; i < sz; i ++) {
                TreeNode cur = queue.poll();
                line.add(cur.val);

                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            // 将该层的遍历出来的所有节点加入结果集
            res.add(line);
        }

        return res;
    }
}

构造二叉树

构建方法 1

下面这套代码对应根据满二叉树层序遍历的结果进行构建：

笔试题一般都是这种构建方法

public class BuildTree {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // str 是满二叉树层序遍历的节点数组（包含 null）
        // ex:1,4,3,1,null,2,null,null,null,null,null,1,null,null,null]
        String[] str = sc.nextLine().split(",");
        TreeNode root = buildTree(str);
        System.out.println("");
    }

    private static TreeNode buildTree(String[] str) {
        if (str == null || str.length == 0) {
            return null;
        }

        // 构造 TreeNode 集合
        List<TreeNode> list = new ArrayList<>();
        for (String node : str) {
            list.add(node.equals("null") ? null : new TreeNode(Integer.parseInt(node)));
        }

        for (int i = 0; i < list.size() / 2; i ++) {
            TreeNode cur = list.get(i);
            // cur == null 的话，那他的左右孩子也就不需要处理了
            if (cur == null) {
                continue;
            }
            cur.left = list.get(i * 2 + 1);
            cur.right = list.get(i * 2 + 2);
        }

        return list.get(0);
    }

    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
}

构建方法 2

如下图，这种格式也是按照的层序遍历的顺序，不过和上面所说的满二叉树格式不同，具体区别就是：如果某个节点是 null 的，那么它的左右孩子节点是不会出现在遍历结果的，举个例子：

所以我们就没有办法像上题一样基于下标来构建了，需要借助层次遍历的队列来进行

public class BuildTree {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // ex: 1,4,3,1,null,2,null,null,null,1,null
        String[] str = sc.nextLine().split(",");
        TreeNode root = buildTree(str);
        System.out.println("");
    }

    private static TreeNode buildTree(String[] str) {
        if (str == null || str.length == 0) {
            return null;
        }

        // 构造 TreeNode 集合
        List<TreeNode> list = new ArrayList<>();
        for (String node : str) {
            list.add(node.equals("null") ? null : new TreeNode(Integer.parseInt(node)));
        }

        TreeNode root = list.get(0);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        // i 指向当前节点 cur 的左子树节点
        int i = 1;
        while (!queue.isEmpty() && i < str.length) {
            TreeNode cur = queue.poll();
            // 此处不需要进行 cur 的判空，因为队列中不会存储 null 的节点

            // cur 的左（i）孩子入队
            cur.left = list.get(i);
            if (cur.left != null) {
                // cur.left == null 的话，那么 cur.left 的左右孩子也一定为 null，就不用入队构建了
                queue.offer(cur.left);
            }
            // cur 的右（i + 1）孩子入队
            cur.right = list.get(i + 1);
            if (cur.right != null) {
                // cur.right == null 的话，那么 cur.right 的左右孩子也一定为 null，就不用入队构建了
                queue.offer(cur.right);
            }

            // 进入下一个节点的左子树节点
            i += 2;
        }
        
        return root;
    }

}

前缀树 TODO

二分查找

标准的二分查找：704. 二分查找 (opens new window)

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int left = 0;
        int right = nums.length -1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

二分查找左边界

情况 1 | 数组部分有序、无重复 or 数组有序、有重复：1351. 统计有序矩阵中的负数 (opens new window)

class Solution {
    public int countNegatives(int[][] grid) {
        int count = 0;

        int rowLen = grid.length; // 行数
        int columnLen = grid[0].length; // 列数
        
        // 【依次二分查找每一行】
        for (int i = 0; i < rowLen; i++) {
            int left = 0;
            int right = columnLen - 1;
            // 【这里是 < 而不是 <=，所以不包含最后一个处理的数 nums[left]】
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                // nums[mid] >= 0, 说明第一个负数在 mid 右边（收缩左边界）
                if (grid[i][mid] >= 0) {
                    left = mid + 1;
                }
                // nums[mid] < 0, 说明第一个负数就是 mid 或者在 mid 左边（收缩右边界）
                else {
                    right = mid;
                }
            }

            // 【对最后一个处理的数打个补丁 nums[left]】
            count += (grid[i][left] >= 0) ? 0 : columnLen - left;
        }

        return count;
    }
}

还有种情况，就是 target 题目并没给出，需要我们自己设定，比如 153. 寻找旋转排序数组中的最小值 (opens new window)

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 手动设定 target
            int target = nums[right];
            int mid = left + ((right - left) >> 1);
            // nums[mid] > target, 说明最小值在 mid 右边（收缩左边界）
            if (nums[mid] > target) {
                left = mid + 1;
            }
            // nums[mid] <= target, 说明最小值在 mid 左边（收缩右边界）
            else {
                right = mid;
            }
        }
        
        // 这道题最小值一定存在，所以不用对 nums[left] 做补偿了
        
        return nums[left];
    }
}

情况 2 | 数组部分有序、有重复：154. 寻找旋转排序数组中的最小值 II (opens new window)

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 手动设定 target
            int target = nums[right];
            int mid = left + ((right - left) >> 1);
            // nums[mid] > target, 说明最小值在 mid 右边（收缩左边界）
            if (nums[mid] > target) {
                left = mid + 1;
            }
            // nums[mid] < target, 说明最小值在 mid 左边（收缩右边界）
            else if (nums[mid] < target) {
                right = mid;
            }
            // nums[mid] = target（保守收缩右边界），比如 [3,3,1,3]
            else {
                right --;
            }
        }
        
        // 这道题最小值一定存在，所以不用对 nums[left] 做补偿了
        
        return nums[left];
    }
}

二分查找右边界 TODO

二分查找极值点：剑指 Offer II 069. 山峰数组的顶部 (opens new window)

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 峰顶
            if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) {
                return mid;
            }
            // 峰顶在 mid 左边
            else if (arr[mid] > arr[mid + 1]) {
                right = mid - 1;
            }
            // 峰顶在 mid 右边
            else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

注意，if 判断中一定要先处理 nums[mid + 1]，不然 nums[mid - 1] 很可能下标越界

双指针

左右指针：剑指 Offer II 007. 数组中和为 0 的三个数 (opens new window)

class Solution {

    private final static Integer TARGET = 0;

    public List<List<Integer>> threeSum(int[] nums) {
        // 存储三元组
        List<List<Integer>> res = new ArrayList<>();

        if (nums == null || nums.length < 3) {
            return res;
        }

        // 1. 对数组进行排序
        Arrays.sort(nums);

        // 2. 遍历处理数组
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] > 0) {
                break;
            }
            // 跳过重复元素
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 左右指针
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 跳过重复元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left ++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right --;
                    }

                    // 开始寻找新的解
                    left ++;
                    right --;
                } else if (sum < 0) {
                    left ++;
                } else {
                    right --;
                }
            }
        }

        return res;
    }
}

滑动窗口：剑指 Offer II 016. 不含重复字符的最长子字符串 (opens new window)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        // 无重复的最长子串的长度
        int res = 0;

        // 1.【声明滑动窗口】
        Map<Character, Integer> window = new HashMap<>();
        int left = 0;
        int right = 0;
		
        while (right < s.length()) {
            // 2.【扩大窗口，right 左移】
            // 2.1【扩大窗口】
            char newChar = s.charAt(right);
            right ++;
            // 2.2.【扩大窗口后处理 window】
            window.put(newChar, window.getOrDefault(newChar, 0) + 1);
			
            // 3.【如果窗口中该元素重复，则缩小窗口（left 左移）直至不重复】
            while (window.get(newChar) > 1) {
                // 3.1【缩小窗口】
                char removeChar = s.charAt(left);
                left ++;
                // 3.2【缩小窗口后处理 window】
                window.put(removeChar, window.get(removeChar) - 1);
            }

            // 4.【计算窗口长度】我们的窗口是左开右闭的，所以这里窗口的长度不要 +1 !!!
            res = Math.max(res, right - left);
        }

        return res;
    }
}

快慢指针：剑指 Offer II 022. 链表中环的入口节点 (opens new window)

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode ptr = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            // 找环的入口节点
            if (slow == fast) {
                while (ptr != fast) {
                    ptr = ptr.next;
                    fast = fast.next;
                }
                return ptr;
            }
        }

        return null;
    }
}

排序

计数排序：剑指 Offer II 075. 数组相对排序 (opens new window)

类似于 bitMap 的思想

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 1.【bitMap 整数范围 0 ~ 1000】
        int[] counts = new int[1001];
        // 2.【计数】
        for (int num : arr1) {
            counts[num] ++;
        }

        // 下标（直接在 arr1 上原地修改）
        int index = 0;
        // 填充在 arr2 中出现的元素
        for (int num : arr2) {
            while (counts[num] > 0) {
                arr1[index] = num;
                index ++;
                counts[num] --;
            }
        }

        // 填充未在 arr2 中出现的元素
        for (int num = 0; num < counts.length; num ++) {
            // 此时 counts[num] 仍然 > 0 的话就表示这个 num 没有在 arr2 中出现过
            while (counts[num] > 0) {
                arr1[index] = num;
                index ++; 
                counts[num] --;
            }
        }

        return arr1;
    }
}

快排：剑指 Offer II 076. 数组中的第 k 大的数字 (opens new window)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        return find(nums, k, 0, nums.length - 1);
    }

    // 在 nums[left, right] 中找到第 k 个最大的元素
    private int find(int[] nums, int k, int left, int right) {
        // 基准元素(nums[left])的最终下标
        int pivot = partition(nums, k, left, right);
        if (pivot == nums.length - k) {
            return nums[pivot];
        }
        // 第 k 个最大的元素在 pivot 左边
        else if (pivot > nums.length - k) {
            return find(nums, k, left, pivot - 1);
        }

        // 第 k 个最大的元素在 pivot 右边
        return find(nums, k, pivot + 1, right);
    }

    // 找到基准元素（一般都是用最左元素）的最终下标
    private int partition(int[] nums, int k, int left, int right) {
        if (left == right) {
            return left;
        }

        int pivot = left;
        // 将 pivot 左边比它的数，和右边比它小的数，进行交换（注意这里不要等号 ！！！）
        while (left < right) {
            while (left < right && nums[pivot] <= nums[right]) {
                right --;
            }
            while (left < right && nums[pivot] >= nums[left]) {
                left ++;
            }
            if (left < right) {
                swap(nums, left, right);
            }
        }

        // 将基准数放到最终的位置（基准数归位）
        swap(nums, pivot, left);

        // 返回基准数的最终下标
        return left;
    }

    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

归并排序：剑指 Offer II 078. 合并排序链表 (opens new window)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
		
        return mergeLists(lists, 0, lists.length);
    }

    // 左闭右开, 归并 lists[left, mid) 和 lists[mid, right) 两个数组
    private ListNode mergeLists(ListNode[] lists, int left, int right) {
        if (left + 1 >= right) {
            return lists[left];
        }

        int mid = (left + right) / 2;
        // 1.【归并左边的链表为一个链表】
        ListNode l = mergeLists(lists, left, mid);
        // 2.【归并右边的链表为一个链表】
        ListNode r = mergeLists(lists, mid, right);
		// 3.【合并左边和右边这两个链表】
        return merge(l, r);
    }
	
    // 合并两个链表
    private ListNode merge(ListNode head1, ListNode head2) {
        // 新链表的头节点
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                cur.next = head1;
                head1 = head1.next;
            }
            else {
                cur.next = head2;
                head2 = head2.next;
            }

            cur = cur.next;
        }

        // 处理两个链表中较长的那一段
        cur.next = (head1 == null) ? head2 : head1;

        return dummy.next;
    }
}

回溯

排列树

子集树

贪心

常规模板

区间调度问题

动态规划

背包问题

01 背包

完全背包

打家劫舍问题

买卖股票问题

子串和子序列问题

矩阵路径问题

图

BFS：剑指 Offer II 107. 矩阵中的距离 (opens new window)

BFS 和 DFS 的时间复杂度都是 O(v + e)，v 为节点数量，e 为边数量

BFS 主要用来处理最短路径问题

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        //  mat 中对应位置元素到最近的 0 的距离
        int[][] dists = new int[row][col];
        // 当前位置是否访问过
        boolean[][] visited = new boolean[row][col];

        // 辅助队列
        Queue<int[]> queue = new LinkedList<>();

        // 1.【初始节点入队（值为 0 的位置），并置为已访问】
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        
        // 2.【定义节点的邻居方向】
        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; 
        
        // 3.【循环处理队中节点】
        while (!queue.isEmpty()) {
            // 3.1【队首节点出队】
            int[] cur = queue.poll();
            // 3.2【获取当前节点到队首节点的距离】
            int dist = dists[cur[0]][cur[1]];
            // 3.3【循环处理当前节点的邻居节点】
            for (int[] dir : dirs) {
                int i = cur[0] + dir[0];
                int j = cur[1] + dir[1];

                // 3.3.1【判断这个邻居节点是否是 1 且没有被处理过】
                if (i >= 0 && i < row && j >= 0 && j < col 
                    && !visited[i][j] && mat[i][j] == 1) {
                    // 3.3.2【计算邻居节点（1）到队首节点（0）的距离 -> dist + 1】
                    dists[i][j] = dist + 1;
                    // 3.3.3【邻居节点入队】
                    queue.offer(new int[]{i, j});
                    // 3.3.4【邻居节点置为已访问】
                    visited[i][j] = true;
                }
            }
        }

        return dists;
    }
}

时间复杂度：O(m * n)，其中 m 为矩阵行数，n 为矩阵列数，即矩阵元素个数。广度优先搜索中每个位置最多只会被加入队列一次，因此只需要 O(m * n) 的时间复杂度

DFS

连通性问题一般用 DFS 而不是说 BFS

常规模板（朴素 DFS）：剑指 Offer II 105. 岛屿的最大面积 (opens new window)

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        // 当前位置是否被访问过
        boolean[][] visited = new boolean[row][col];

        // 最大岛屿面积
        int maxArea = 0;

        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                // 1.【当前位置是 1，并且未被访问过，说明发现了一片新岛屿，执行 dfs】
                if (grid[i][j] == 1 && !visited[i][j]) {
                    int area = dfs(grid, visited, i, j);
                    maxArea = Math.max(area, maxArea);
                }
            }
        }

        return maxArea;
    }

    // 2.【获取 grid[row][col] 所在岛屿的面积】
    private int dfs(int[][] grid, boolean[][] visited, int row, int col) {
        // 2.1【当前位置置为已访问】
        visited[row][col] = true;

        // 2.2【初始化面积为 1（只访问了当前位置，面积为 1）】
        int area = 1;

        // 2.3【定义节点的邻居方向】
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 2.4【循环处理当前节点的邻居节点】
        for (int[] dir : dirs) {
            int i = row + dir[0];
            int j = col + dir[1];

            // 2.4.1【判断这个邻居节点是否是 1 且没有被处理过】
            if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length 
                && !visited[i][j] && grid[i][j] == 1) {
                // 2.4.2【递归处理该邻居节点(grid[i][j])的邻居节点】
                area += dfs(grid, visited, i, j);
            }
        }

        return area;
    }
}

时间复杂度：O(m * n)。其中 m 是给定网格中的行数，n 是列数。我们访问每个网格最多一次。

需要存储路径的 DFS（就是回溯）：剑指 Offer II 110. 所有路径 (opens new window)

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        // 起始节点加入 path
        path.add(0);
        // 标志位
        int start = 0;
        // dfs / 回溯
        dfs(graph, res, path, start);

        return res;
    }

    private void dfs(int[][] graph, List<List<Integer>> res, List<Integer> path, int start) {
        // 结束条件
        if (start == graph.length - 1) {
            res.add(new ArrayList<>(path));
            return ;
        }

        for (int neighboor : graph[start]) {
            // 做选择（加入邻居节点）
            path.add(neighboor);
            // 进入下一层（邻居节点）
            dfs(graph, res, path, neighboor);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}

时间复杂度：，其中 N 为图中点的数量，每个节点都有两种选择，加入路径还是不加入路径，时间复杂度为 ，且每条路径长度为 O(N)，因此总时间复杂度为

记忆化 DFS：剑指 Offer II 112. 最长递增路径 (opens new window)

使用记忆化深度优先搜索，当访问到一个单元格 (i,j)时，如果 memo[i][j] == 0 说明该单元格的结果已经计算过，则直接从缓存中读取结果，如果 memo[i][j] != 0，说明该单元格的结果尚未被计算过，则进行搜索，并将计算得到的结果存入缓存中。

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        // 存储最长递增路径的长度
        int res = 0;
        
        // 【存储从 matrix[i][j] 出发的最长递增路径的长度】
        int[][] memo = new int[matrix.length][matrix[0].length];

        for (int i = 0; i < matrix.length; i ++) {
            for (int j = 0; j < matrix[0].length; j ++) {
                int length = dfs(matrix, memo, i, j);
                res = Math.max(res, length);
            }
        }

        return res;
    }

    // 返回从 matrix[row][col] 出发的最长递增路径的长度
    private int dfs(int[][] matrix, int[][] memo, int row, int col) {
        // 【如果 memo[i][j] > 0，就说明之前已经计算过从 matrix[row][col] 出发的最长递增路径的长度，直接返回】
        if (memo[row][col] > 0) {
            return memo[row][col];
        }
        
        int length = 1;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : dirs) {
            // dfs 那一套，此处就省略了....
            ......
        }

        // 【更新 memo 数组】
        memo[row][col] = length;

        return length;
    }
}

时间复杂度：O(m * n)。其中 m 是给定网格中的行数，n 是列数

拓扑排序：剑指 Offer II 113. 课程顺序 (opens new window)

基于 BFS 实现拓扑排序

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 存储课程顺序
        List<Integer> res = new ArrayList<>();

        // 辅助队列
        Queue<Integer> queue = new LinkedList<>();

        // 每个节点的入度
        int[] inDegress = new int[numCourses];

        // 1. 构建邻接表. key: 先修课程 value: 所有的 学完 key 对应的课程之后才能学习的课程
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            // 先修课程
            int pre = prerequisite[1];
            // 后修课程
            int post = prerequisite[0];
            
            map.putIfAbsent(pre, new ArrayList<>());
            // 1.1【如果图中已经存在 pre-> post 的关系了，则不再进行处理，防止入度统计错误】
            if (!map.get(pre).contains(post)) {
                // 1.1.1【该关系加入邻接表】
                map.get(pre).add(post);
                // 1.1.2【后修课程入度增加】
                inDegress[post] ++;
            }
        }


        // 2.【入度为 0 的节点入队】
        for (int i = 0; i < inDegress.length; i ++) {
            if (inDegress[i] == 0) {
                queue.offer(i);
            }
        }

        // 3.【处理队列中节点】
        while (!queue.isEmpty()) {
            // 3.1【队首节点出队，并将该节点添加到拓扑排序序列中】
            int cur = queue.poll();
            res.add(cur);

            // 3.2【获取当前节点的后修课程节点】
            List<Integer> nexts = map.get(cur);
            // 如果 cur 不是任何一门课的先修课程，那么 nexts 为空，这里需要判断下
            if (nexts == null) {
                continue;
            }

            // 3.3【循环处理当前节点的后修课程节点】
            for (int next : nexts) {
                // 3.3.1【将后修课程的入度减 1，这相当于删除从先修课程到后修课程的边】
                inDegress[next] --;
                // 3.3.2【如果发现新的入度为 0 的节点，则将其添加到队列中】
                if (inDegress[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 4. 如果不可能完成所有课程，返回一个空数组
        if (res.size() != numCourses) {
            return new int[0];
        }

        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

时间复杂度: O(n + m)，其中 n 为课程数，m 为先修课程的要求数。其实就是 BFS 时间复杂度。

并查集：剑指 Offer II 116. 省份数量 (opens new window)

class Solution {
    public int findCircleNum(int[][] isConnected) {
        if (isConnected == null || isConnected.length == 0) {
            return 0;
        }
        
        // 节点数量
        int n = isConnected.length;

        // 不连通子图的数量, 此时每个城市都是一个独立的节点
        int res = n;

        // 1.【记录每个节点(城市)所属子图(省份)的根节点】
        int[] fathers = new int[n];
        // 2.【初始化 fathers, 此时每个城市都是一个独立的节点】
        for (int i = 0; i < n; i ++) {
            fathers[i] = i;
        }

        // 3.【根据邻接表循环处理所有城市】
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                // 3.1【如果 i 和 j 连通】
                if (i != j && isConnected[i][j] == 1) {
                    // 3.1.1【查找这俩节点所属子图的根节点】
                    int fathersI = getFather(fathers, i);
                    int fathersJ = getFather(fathers, j);
                    // 3.1.2【如果此时两个节点的根节点不相同，说明它们此时仍然位于不同的子集中，需要进行合并】
                    if (fathersI != fathersJ) {
                        // 将一个子集的根节点的指向父节点的指针指向另一个子集的根节点，这就合并了两个子集
                        fathers[fathersI] = fathersJ;
                        res --;
                    }
                }
            }
        }

        return res;
    }

    // 查找 city 所属子图的根节点
    private int getFather(int[] fathers, int cur) {
        if (fathers[cur] != cur) {
            // 递归查找 city 的根节点 (路径压缩)
            fathers[cur] = getFather(fathers, fathers[cur]);
        }

        return fathers[cur];
    }
}

时间复杂度：