在上一篇文章 算法模式:广度优先搜索 介绍了介绍一种即适用于树,又适用于图的的算法模式。本篇文章,继续介绍一种即适用于树,又适用于图的的算法模式:深度优先搜索。
深度优先搜索 深度优先搜索主要思路是从图中一个未访问的顶点 V 开始,沿着一条路一直走到底,然后从这条路尽头的节点回退到上一个节点,再从另一条路开始走到底…,不断递归重复此过程,直到所有的顶点都遍历完成,它的特点是不撞南墙不回头,先走完一条路,再换一条路继续走。
树是图的一种特例(连通无环的图就是树),所以,深度优先搜索也适用于树。
在对树做深度优先搜索时,可以用递归(或显式栈,如果你想用迭代方式的话)来记录遍历过程中访问过的父节点。运行方式是从根节点开始,如果该节点不是叶子节点,我们需要干三件事:
需要区别我们是先处理根节点(pre-order,前序),处理孩子节点之间处理根节点(in-order,中序),还是处理完所有孩子再处理根节点(post-order,后序)。
递归处理当前节点的左右孩子。
LeetCode 124. 二叉树中的最大路径和 LeetCode - 124. 二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例 1:
1 / \ 2 3 输入:root = [1,2,3] 输出:6 解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6 示例 2:
-10 / \ 9 20 / \ 15 7 输入:root = [-10,9,20,null,null,15,7] 输出:42 解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
在上一篇文章 算法模式:多路归并 介绍了一种利用堆做链表合并的算法模式。本篇文章,介绍一种即适用于树,又适用于图的的算法模式:广度优先搜索。
广度优先搜索 广度优先搜索既适用于树,又适用于图。除此之外,在处理一些矩阵问题时,也会用到广度优先搜索的思想。当然,也可以把矩阵按照图来理解。
树上的广度优先搜索模式是通过把根节点加到队列中,然后不断遍历直到队列为空。每一次循环中,我们都会把队头结点拿出来(remove),然后对其进行必要的操作。在删除每个节点的同时,其孩子节点,都会被加到队列中。借助于队列数据结构,从而能保证树的节点按照他们的层数打印出来。打印完当前层所有元素,才能执行到下一层。所有这种需要遍历树且需要一层一层遍历的问题,都能用这种模式高效解决。
识别树上的广度优先搜索:
如果你被问到去遍历树,需要按层操作的方式(也称作层序遍历)
LeetCode 102. 二叉树的层序遍历 LeetCode - 102. 二叉树的层序遍历 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。(即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2:
输入:root = [1] 输出:[[1]] 示例 3:
输入:root = [] 输出:[] 提示:
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
思路分析 思路与上述描述类似,这里直接看图:
图 1. 广度优先搜索 代码如下:
/** * @author D瓜哥 · https://www.diguage.com * @since 2025-03-31 07:31:39 */ public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { return Collections.emptyList(); } List<List<Integer>> result = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(size); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); // 将下一层节点,从左到右,依次加入到队列中 if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; }
在上一篇文章 算法模式:双堆 介绍了一种利用两个堆选择中间数的算法模式。本篇文章,再来介绍一种关于堆的模式:多路归并。
多路归并 多路归并能帮咱们解决那些涉及到多组排好序的数组的问题。
每当你的输入是 K 个排好序的数组,你就可以用堆来高效顺序遍历其中所有数组的所有元素。你可以将每个数组中最小的一个元素加入到最小堆中,从而得到全局最小值。当我们拿到这个全局最小值之后,再从该元素所在的数组里取出其后面紧挨着的元素,加入堆。如此往复直到处理完所有的元素。
该模式是这样的运行的:
把每个数组中的第一个元素都加入最小堆中
取出堆顶元素(全局最小),将该元素放入排好序的结果集合里面
将刚取出的元素所在的数组里面的下一个元素加入堆
重复步骤 2,3,直到处理完所有数字
识别K路归并:
该问题的输入是排好序的数组,链表或是矩阵
如果问题让咱们合并多个排好序的集合,或是需要找这些集合中最小的元素
LeetCode 23. 合并 K 个升序链表 LeetCode - 23. 合并 K 个升序链表 给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 1:
输入:lists = [[1,4,5],[1,3,4],[2,6]] 输出:[1,1,2,3,4,4,5,6] 解释:链表数组如下: [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2:
输入:lists = [] 输出:[] 示例 3:
输入:lists = [[]] 输出:[] 提示:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] 按 升序 排列
lists[i].length 的总和不超过 104
在上一篇文章 算法模式:循环排序 介绍了一种只需 \$O(1)\$ 时间就可以完成排序的算法模式。本篇文章,来介绍一种可以快速查出数组中位数的模式:双堆。
双堆 很多问题中,我们被告知,我们拿到一大把可以分成两队的数字。为了解决这个问题,我们感兴趣的是,怎么把数字分成两半?使得:小的数字都放在一起,大的放在另外一半。双堆模式就能高效解决此类问题。
正如名字所示,该模式用到了两个堆,是不是很难猜?一个最小堆用来找最小元素;一个最大堆,拿到最大元素。这种模式将一半的元素放在最大堆中,这样你可以从这一堆中秒找到最大元素。同理,把剩下一半丢到最小堆中,\$O(1)\$ 时间找到他们中的最小元素。通过这样的方式,这一大堆元素的中位数就可以从两个堆的堆顶拿到数字,从而计算出来。
判断双堆模式的秘诀:
这种模式在优先队列,计划安排问题(Scheduling)中有奇效
如果问题让你找一组数中的最大/最小/中位数
有时候,这种模式在涉及到二叉树数据结构时也特别有用
图 1. 大堆与小堆 LeetCode 295. 数据流的中位数 LeetCode - 295. 数据流的中位数 中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
示例 1:
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
在上一篇文章 算法模式:快速选择 介绍了如何利用快排思想快速选出第 K 个 最 X 的元素。本篇文章,介绍一种只需 \$O(1)\$ 时间就可以完成排序的算法模式:循环排序。
循环排序 循环排序讲述的是一直很好玩的方法:可以用来处理数组中的数值限定在一定的区间的问题。这种模式一个个遍历数组中的元素,如果当前这个数它不在其应该在的位置的话,咱们就把它和它应该在的那个位置上的数交换一下。你可以尝试将该数放到其正确的位置上,但这复杂度就会是 \$O(n^2)\$。这样的话,可能就不是最优解了。因此循环排序的优势就体现出来了。
图 1. 循环排序 循环排序适用的场景:
包含连续数字的数组(如 1 到 n 或 0 到 n-1)
需要找出缺失/重复数字的问题
需要原地排序且时间复杂度要求高的情况
LeetCode 41. 缺失的第一个正数 LeetCode - 41. 缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 \$O(n)\$ 并且只使用常数级别额外空间的解决方案。
示例 1:
输入:nums = [1,2,0] 输出:3 解释:范围 [1,2] 中的数字都在数组中。 示例 2:
输入:nums = [3,4,-1,1] 输出:2 解释:1 在数组中,但 2 没有。 示例 3:
输入:nums = [7,8,9,11,12] 输出:1 解释:最小的正数 1 没有出现。 提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
在上一篇文章 算法模式:Top K 问题 介绍了如何利用堆快速选出最 X 的 K 个元素。本篇文章,介绍一种可以快速选择第 K 个 最 X 元素的算法模式:快速选择。
快速选择 快速选择起源于快排算法。在快排算法中,把元素根据基准元素分成左右两部分,一边的元素小于基准元素,另外一个的元素大于等于基准元素,再对两边的元素递归处理,最终得到有序结果。受此启发,在将元素根据基准元素分成左右两部分后,这里假设,左边小于基准元素,右边大于等于基准元素,那么会有如下三种情况:
当前基准元素所在位置正好是 K,正好是所求结果,直接返回;
当前基准元素所在位置小于 K,那么 K 位置在当前基准元素的右边;
当前基准元素所在位置大于 K,那么 K 位置在当前基准元素的左边;
所以,该模式不仅适用于求第 K 个之最元素,也适用于求“Top K 问题”。
LeetCode 215. 数组中的第K个最大元素 LeetCode - 215. 数组中的第K个最大元素 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 \$O(n)\$ 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
在上一篇文章 算法模式:单调栈 介绍了单调栈的算法模式。本篇文章,介绍一种堆相关的算法模式:Top K 问题。(英语原文是 Top K Elements,实在没有找到好的翻译,暂时翻译成 “Top K 问题”,后续有好的翻译再改。)
Top K 问题 任何让求解最大/最小/最频繁的K个元素的题,都遵循这种模式。
用来记录这种前 K 类型的最佳数据结构就是堆了(在Java中,对应的结构是优先队列 PriorityQueue )。这种模式借助堆来解决很多这种前 K 个数值的问题。
图 1. 大堆与小堆 这个模式是这样的:
根据题目要求,将K个元素插入到最小堆或是最大堆。
遍历剩下的还没访问的元素,如果当前出来到的这个元素比堆顶元素大或者小,那咱们把堆顶元素先删除,再加当前元素进去。
如果求最大的前 K 个元素,则适合使用小堆,将待检查元素与堆顶元素相比,堆顶元素小,直接删除堆顶元素,将待检查元素添加到堆即可。反之,则用大堆。
注意这种模式下,咱们不需要去排序数组,因为堆具有这种良好的局部有序性,这对咱们需要解决问题就够了。
识别最大 K 个元素模式:
如果你需要求最大/最小/最频繁的前K个元素
如果你需要通过排序去找一个特定的数
LeetCode 347. 前 K 个高频元素 LeetCode - 347. 前 K 个高频元素 给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
在上一篇文章 算法模式:滑动窗口 介绍了滑动窗口的算法模式。本篇文章,介绍一种堆栈相关的算法模式:单调栈。
单调栈 所谓单调栈,就是在栈的基础上,增加了一个附加条件:栈内元素单调递增或者递减,如果不符合要求,则将元素出栈,直到符合条件为止。当需要给当前的元素,找右边/左边第一个比它大/小的位置时,就特别适合使用单调栈。
图 1. 单调递增栈 图 2. 单调递减栈 一般会用到 Deque 的以下四个方法:
stack.isEmpty():如果 deque 不包含任何元素,则返回 true,否则返回 false。因为要栈顶元素在满足要求的时候要弹出,所以需要进行空栈判断。有些场景,可能栈一定不会空的时候,就不需要该方法进行空栈判断。
stack.push(e):将元素 e 入栈。
stack.pop():将栈顶元素弹出,并返回当前弹出的栈顶元素。
stack.peek():获取栈顶元素,不弹出。
// 定义一个单调栈 Deque<Integer> stack = new LinkedList<>(); // 第一个元素,直接添加 stack.push(0); // 注意:栈内存的是数组下标 for (int i = 1; i < nums.length; i++) { // 如果是单调递增栈,那么这里就是大于,即 nums[i] > nums[deque.peek()] if (nums[i] < nums[stack.peek()]) { stack.push(i); } else if (nums[i] == nums[stack.peek()]) { stack.push(i); // 此处除了入栈,在有些场景下,还有可能有其他操作 // .............. } else { // 循环比较,直到遇到当前元素小于栈顶的元素情况,跳出循环 // 单调递增栈,这里是小于,即nums[i] < nums[deque.peek()] while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { //主要逻辑 // ............ // ............ // 弹出栈顶元素 stack.pop(); } stack.push(i); } } 记住这两句话:
单调递增栈,利用波谷剔除栈中的波峰,留下波谷;
单调递减栈,利用波峰剔除栈中的波谷,留下波峰。
LeetCode 316. 去除重复字母 LeetCode - 316. 去除重复字母 给你一个字符串 s,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
示例 1:
输入:s = "bcabc" 输出:"abc" 示例 2:
输入:s = "cbacdcbc" 输出:"acdb" 提示:
1 <= s.length <= 104
s 由小写英文字母组成
在上一篇文章 算法模式:双指针 介绍了双指针的算法模式。本篇文章,介绍一种类似双指针的算法模式:滑动窗口。
滑动窗口 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始,一直往右边一个一个元素挪动。当然了,根据题目要求,我们可能有固定窗口大小的情况,也有窗口的大小变化的情况。
图 1. 滑动窗口 滑动窗口大概思路如下:
// 向前滑动窗口 while (right < array.lenght) { // 扩大窗口,将元素放入窗口 right++; while (缩小窗口条件) { // 处理窗口内的元素 // 缩小窗口,将元素丢出窗口 left++; } } 下面是一些我们用来判断我们可能需要上滑动窗口策略的方法:
问题的输入是一些线性结构:比如链表,数组,字符串之类的
让你去求最长/最短子字符串或是某些特定的长度要求
LeetCode 3. 无重复字符的最长子串 LeetCode - 3. 无重复字符的最长子串 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。 示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
在上一篇文章 算法模式:区间合并 介绍了合并区间所用的算法模式。本篇文章,介绍一种即可以用在数组,又可以用在链表中的算法模式:双指针。
双指针 双指针是这样的模式:两个指针朝着左右方向移动(双指针分为同向双指针和异向双指针),直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如,你需要去比较数组中每个元素和其他元素的关系时,你就需要用到双指针了。
需要双指针的原因是:如果你只用一个指针的话,你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然 Brute F orce 一个指针的解法可能会奏效,但时间复杂度一般会是 \$O(n^2)\$。在很多情况下,双指针能帮助我们找到空间或是时间复杂度更低的解。
识别使用双指针的招数:
一般来说,数组或是链表是排好序的,你得在里头找一些组合满足某种限制条件
这种组合可能是一对数,三个数,或是一个子数组
LeetCode 15. 三数之和 LeetCode - 15. 三数之和 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]] 解释: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意,输出的顺序和三元组的顺序并不重要。