刷题模板汇总
@[toc]
## 栈
### 常规模板：[剑指 Offer II 036. 后缀表达式](https://leetcode.cn/problems/8Zf90G/)
```java
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. 每日温度](https://leetcode.cn/problems/iIQa4I/)
```java
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. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/)
```java
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 大的数字](https://leetcode.cn/problems/xx4gT2/)
```java
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. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/)
递归：
```java
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;
}
}
```
迭代：
```java
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. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal/)
递归
```java
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;
}
}
```
迭代：
```java
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. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)
递归：
```java
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;
}
}
```
迭代：
```java
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. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
```java
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
下面这套代码对应**根据满二叉树层序遍历的结果进行构建**：
> 笔试题一般都是这种构建方法
```java
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
如下图，这种格式也是按照的层序遍历的顺序，不过和上面所说的满二叉树格式不同，具体区别就是：<u>如果某个节点是 null 的，那么它的左右孩子节点是不会出现在遍历结果的</u>，举个例子：
> 所以我们就没有办法像上题一样基于下标来构建了，需要借助层次遍历的队列来进行
```java
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. 二分查找](https://leetcode.cn/problems/binary-search/)
```java
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. 统计有序矩阵中的负数](https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/)
```java
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. 寻找旋转排序数组中的最小值](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/)
```java
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](https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/)
```java
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. 山峰数组的顶部](https://leetcode.cn/problems/B1IidL/)
```java
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 的三个数](https://leetcode-cn.com/problems/1fGaJU/)
```java
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. 不含重复字符的最长子字符串](https://leetcode.cn/problems/wtcaE1/)
```java
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. 链表中环的入口节点](https://leetcode.cn/problems/c32eOV/)
```java
/**
* 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. 数组相对排序](https://leetcode.cn/problems/0H97ZC/)
类似于 bitMap 的思想
```java
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 大的数字](https://leetcode.cn/problems/xx4gT2/)
```java
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. 合并排序链表](https://leetcode.cn/problems/vvXgSW/)
```java
/**
* 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. 矩阵中的距离](https://leetcode.cn/problems/2bCMpM/)
> BFS 和 DFS 的时间复杂度都是 O(v + e)，v 为节点数量，e 为边数量
BFS 主要用来处理最短路径问题
```java
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. 岛屿的最大面积](https://leetcode.cn/problems/ZL6zAn/)
```java
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. 所有路径](https://leetcode.cn/problems/bP4bmD/)
```java
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);
}
}
}
```
时间复杂度：$O(N * 2^N)$，其中 N 为图中点的数量，每个节点都有两种选择，加入路径还是不加入路径，时间复杂度为 $O(2^N)$，且每条路径长度为 O(N)，因此总时间复杂度为 $O(N * 2^N)$
#### 记忆化 DFS：[剑指 Offer II 112. 最长递增路径](https://leetcode.cn/problems/fpTFWP/)
使用记忆化深度优先搜索，当访问到一个单元格 (i,j)时，**如果 `memo[i][j] == 0` 说明该单元格的结果已经计算过，则直接从缓存中读取结果**，如果 `memo[i][j] != 0`，说明该单元格的结果尚未被计算过，则进行搜索，并将计算得到的结果存入缓存中。
```java
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. 课程顺序](https://leetcode.cn/problems/QA2IGt/)
基于 BFS 实现拓扑排序
```java
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. 省份数量](https://leetcode.cn/problems/bLyHh0/)
```java
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];
}
}
```
时间复杂度：$O(N^2)$