快速排序详解及应用读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 215. Kth Largest Element in an Arrayopen in new window 215. 数组中的第K个最大元素open in new window 🟠 912. Sort an Arrayopen in new window 912. 排序数组open in new window 🟠 - 剑指 Offer II 076. 数组中的第 k 大的数字open in new window 🟠 前文 归并排序算法详解 通过二叉树的视角描述了归并排序的算法原理以及应用，很多读者大呼精妙，那我就趁热打铁，今天继续用二叉树的视角讲一讲快速排序算法的原理以及运用。 #快速排序算法思路首先我们看一下快速排序的代码框架： java 🟢cpp 🤖python 🤖go 🤖javascript 🤖 void sort(int[] nums, int lo, int hi) { if (lo >= hi) { ...

题目不让我干什么，我偏要干什么读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 341. Flatten Nested List Iteratoropen in new window 341. 扁平化嵌套列表迭代器open in new window 🟠 提示 刷题插件open in new window 集成了手把手刷二叉树功能，按照公式和套路讲解了 150 道二叉树题目，可手把手带你刷完二叉树分类的题目，迅速掌握递归思维。 今天来讲一道非常有启发性的设计题目，为什么说它有启发性，我们后面再说。 #一、题目描述这是力扣第 341 题「扁平化嵌套列表迭代器open in new window」，我来描述一下题目： 首先，现在有一种数据结构 NestedInteger，这个结构中存的数据可能是一个 Integer 整数，也可能是一个 NestedInteger 列表。注意，这个列表里面装着的是 NestedInteger，也就是说这个列表中的每一个元素可能是个整数，可能又是个列表，这样无限递归嵌套下去…… NestedInteger ...

一道求中位数的算法题把我整不会了读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 295. Find Median from Data Streamopen in new window 295. 数据流的中位数open in new window 🔴 - 剑指 Offer 41. 数据流中的中位数open in new window 🔴 如果输入一个数组，让你求中位数，这个好办，排个序，如果数组长度是奇数，最中间的一个元素就是中位数，如果数组长度是偶数，最中间两个元素的平均数作为中位数。 如果数据规模非常巨大，排序不太现实，那么也可以使用概率算法，随机抽取一部分数据，排序，求中位数，作为所有数据的中位数。 本文说的中位数算法比较困难，也比较精妙，是力扣第 295 题「数据流的中位数open in new window」： 295. 数据流的中位数 | 力扣 open in new window | LeetCode open in new window | ...

前缀树算法模板秒杀五道算法题读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 1804. Implement Trie II (Prefix Tree)open in new window🔒 1804. 实现 Trie （前缀树） IIopen in new window🔒 🟠 208. Implement Trie (Prefix Tree)open in new window 208. 实现 Trie (前缀树)open in new window 🟠 211. Design Add and Search Words Data Structureopen in new window 211. 添加与搜索单词 - 数据结构设计open in new window 🟠 648. Replace Wordsopen in new window 648. 单词替换open in new window 🟠 677. Map Sum Pairsopen in new window 677. 键值映射open in n ...

一道数组去重的算法题把我整不会了读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 1081. Smallest Subsequence of Distinct Charactersopen in new window 1081. 不同字符的最小子序列open in new window 🟠 316. Remove Duplicate Lettersopen in new window 316. 去除重复字母open in new window 🟠 关于去重算法，应该没什么难度，往哈希集合里面塞不就行了么？ 最多给你加点限制，问你怎么给有序数组原地去重，这个我们前文 双指针技巧秒杀七道数组题目 讲过。 本文讲的问题应该是去重相关算法中难度最大的了，把这个问题搞懂，就再也不用怕数组去重问题了。 这是力扣第 316 题「去除重复字母open in new window」，题目如下： 316. 去除重复字母 | 力扣 open in new window | LeetCode&nbs ...

二叉堆详解实现优先级队列二叉堆（Binary Heap）没什么神秘，性质比二叉搜索树 BST 还简单。 其主要操作就两个，sink（下沉）和 swim（上浮），用以维护二叉堆的性质。其主要应用有两个，首先是一种排序方法「堆排序」，第二是一种很有用的数据结构「优先级队列」。 那么本文以实现优先级队列（Priority Queue）为例，来讲讲一下二叉堆怎么运作的。 #一、二叉堆概览首先，二叉堆和二叉树有啥关系呢，为什么人们总是把二叉堆画成一棵二叉树？ 因为，二叉堆在逻辑上其实是一种特殊的二叉树（完全二叉树），只不过存储在数组里。一般的链表二叉树，我们操作节点的指针，而在数组里，我们把数组索引作为指针： java 🟢cpp 🤖python 🤖go 🤖javascript 🤖 // 父节点的索引int parent(int root) { return root / 2;}// 左孩子的索引int left(int root) { return root * 2;}// 右孩子的索引int right(int root)  ...

算法就像搭乐高：带你手撸 LFU 算法读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 460. LFU Cacheopen in new window 460. LFU 缓存open in new window 🔴 上篇文章 带你手写LRU算法 写了 LRU 缓存淘汰算法的实现方法，本文来写另一个著名的缓存淘汰算法：LFU 算法。 LRU 算法的淘汰策略是 Least Recently Used，也就是每次淘汰那些最久没被使用的数据；而 LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些使用次数最少的数据。 LRU 算法的核心数据结构是使用哈希链表 LinkedHashMap，首先借助链表的有序性使得链表元素维持插入顺序，同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。 从实现难度上来说，LFU 算法的难度大于 LRU 算法，因为 LRU 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据， ...

动态规划穷举的两种视角读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 115. Distinct Subsequencesopen in new window 115. 不同的子序列open in new window 🔴 - 剑指 Offer II 097. 子序列的数目open in new window 🔴 挺久没写动态规划相关的题目了，本文我带大家复习一下动态规划相关问题的一系列解题套路，然后着重讨论一下动态规划穷举时不同视角的问题。 #动态规划解题组合拳首先，前文 我的刷题心得 讲了，我们刷的算法问题的本质是「穷举」，动态规划问题也不例外，你必须想办法穷举所有可能的解，然后从中筛选出符合题目要求的解。 另外，动态规划问题穷举的过程中会出现重叠子问题导致的冗余计算，所以前文 动态规划核心套路框架 中告诉你如何一步一步把暴力穷举解法优化成效率更高的动态规划解法。 然而，想要写出暴力解需要依据状态转移方程，状态转移方程是动态规划的解题核心，可不是那么容易想出来的。不过，前文 动态规划设计：数学归纳法 告诉你，思考状态转 ...

二分搜索怎么用？我又总结了套路读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 1011. Capacity To Ship Packages Within D Daysopen in new window 1011. 在 D 天内送达包裹的能力open in new window 🟠 410. Split Array Largest Sumopen in new window 410. 分割数组的最大值open in new window 🔴 875. Koko Eating Bananasopen in new window 875. 爱吃香蕉的珂珂open in new window 🟠 - 剑指 Offer II 073. 狒狒吃香蕉open in new window 🟠 我们前文 我写了首诗，把二分搜索变成了默写题 详细介绍了二分搜索的细节问题，探讨了「搜索一个元素」，「搜索左侧边界」，「搜索右侧边界」这三个情况，教你如何写出正确无 bug 的二分搜索算法。 但是前文总结的二分搜索代码框架仅仅局限于「 ...