刷题模板汇总
# 栈
# 常规模板:剑指 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);
}
}
}
时间复杂度:
# 记忆化 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];
}
}
时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~