二叉堆详解实现优先级队列二叉堆（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) ...
如何高效进行模幂运算读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
372. Super Powopen in new window
372. 超级次方open in new window
🟠
今天来聊一道与数学运算有关的题目，力扣第 372 题「超级次方open in new window」，让你进行巨大的幂运算，然后求余数。
java 🤖cpp 🟢python 🤖go 🤖javascript 🤖
// 注意：java 代码由 chatGPT🤖 根据我的 cpp 代码翻译，旨在帮助不同背景的读者理解算法逻辑。// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 cpp 代码对比查看。int superPow(int a, List<Integer> b);
要求你的算法返回幂运算 a^b 的计算结果与 1337 取模（mod，也就是余数）后的结果。就是你先得计算幂 a^b，但是这个 b 会非常大，所以 b 是用数组的形式表示的。
这个算法其实就是广泛应用于离散数学的模幂算法，至于为什么要对 1 ...
前缀树算法模板秒杀五道算法题读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
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
力扣
难度
172. Factorial Trailing Zeroesopen in new window
172. 阶乘后的零open in new window
🟠
793. Preimage Size of Factorial Zeroes Functionopen in new window
793. 阶乘函数后 K 个零open in new window
🔴
笔试题中经常看到阶乘相关的题目，今天说两个最常见的题目：
1、输入一个非负整数 n，请你计算阶乘 n! 的结果末尾有几个 0。
这也是力扣第 172 题「阶乘后的零open in new window」，比如说输入 n = 5，算法返回 1，因为 5! = 120，末尾有一个 0。
函数签名如下：
int trailingZeroes(int n);
2、输入一个非负整数 K，请你计算有多少个 n，满足 n! 的结果末尾恰好有 K 个 0。
这也是力扣第 793 题「阶乘后 K 个零open i ...
谈谈游戏中的随机算法读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
382. Linked List Random Nodeopen in new window
382. 链表随机节点open in new window
🟠
384. Shuffle an Arrayopen in new window
384. 打乱数组open in new window
🟠
398. Random Pick Indexopen in new window
398. 随机数索引open in new window
🟠
没事儿的时候我喜欢玩玩那些经典的 2D 网页小游戏，我发现很多游戏都要涉及地图的随机生成，比如扫雷游戏中雷的位置应该是随机分布的：
再比如经典炸弹人游戏，障碍物的位置也是有一定随机性的：
这些 2D 游戏相较现在的大型 3D 游戏虽然看起来有些简陋，但依然用到很多有趣算法技巧，本文就来深入研究一下地图的随机生成算法。
2D 游戏的地图肯定可以抽象成一个二维矩阵，就拿扫雷举例吧，我们可以用下面这个类表示扫雷的棋盘： ...
一个方法团灭 LeetCode 打家劫舍问题读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
198. House Robberopen in new window
198. 打家劫舍open in new window
🟠
213. House Robber IIopen in new window
213. 打家劫舍 IIopen in new window
🟠
337. House Robber IIIopen in new window
337. 打家劫舍 IIIopen in new window
🟠
-
剑指 Offer II 089. 房屋偷盗open in new window
🟠
-
剑指 Offer II 090. 环形房屋偷盗open in new window
🟠
有读者私下问我 LeetCode 「打家劫舍」系列问题（英文版叫 House Robber）怎么做，我发现这一系列题目的点赞非常之高，是比较有代表性和技巧性的动态规划题目，今天就来聊聊这道题目。
打家劫舍系列总共有三道，难 ...
动态规划穷举的两种视角读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
115. Distinct Subsequencesopen in new window
115. 不同的子序列open in new window
🔴
-
剑指 Offer II 097. 子序列的数目open in new window
🔴
挺久没写动态规划相关的题目了，本文我带大家复习一下动态规划相关问题的一系列解题套路，然后着重讨论一下动态规划穷举时不同视角的问题。
#动态规划解题组合拳首先，前文 我的刷题心得 讲了，我们刷的算法问题的本质是「穷举」，动态规划问题也不例外，你必须想办法穷举所有可能的解，然后从中筛选出符合题目要求的解。
另外，动态规划问题穷举的过程中会出现重叠子问题导致的冗余计算，所以前文 动态规划核心套路框架 中告诉你如何一步一步把暴力穷举解法优化成效率更高的动态规划解法。
然而，想要写出暴力解需要依据状态转移方程，状态转移方程是动态规划的解题核心，可不是那么容易想出来的。不过，前文 动态规划设计：数学归纳法 告诉你，思考状态转 ...
动态规划之子序列问题解题模板读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
1312. Minimum Insertion Steps to Make a String Palindromeopen in new window
1312. 让字符串成为回文串的最少插入次数open in new window
🔴
516. Longest Palindromic Subsequenceopen in new window
516. 最长回文子序列open in new window
🟠
子序列问题是常见的算法问题，而且并不好解决。
首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。
而且，子序列问题很可能涉及到两个字符串，比如前文 最长公共子序列，如果没有一定的处理经验，真的不容易想出来。所以本文就来扒一扒子序列问题的套路，其实就有两种模板，相关问题只要往这两种思路上想，十拿九稳。
一般来说，这类问题都是让你求一个最长子序列，因为最短 ...
经典动态规划：最长公共子序列读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
1143. Longest Common Subsequenceopen in new window
1143. 最长公共子序列open in new window
🟠
583. Delete Operation for Two Stringsopen in new window
583. 两个字符串的删除操作open in new window
🟠
712. Minimum ASCII Delete Sum for Two Stringsopen in new window
712. 两个字符串的最小ASCII删除和open in new window
🟠
-
剑指 Offer II 095. 最长公共子序列open in new window
🟠
不知道大家做算法题有什么感觉，我总结出来做算法题的技巧就是，把大的问题细化到一个点，先研究在这个小的点上如何解决问题，然后再通过递归/迭代的方式扩展到整个问题。
比如说我们前文 ...
经典动态规划：高楼扔鸡蛋读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
887. Super Egg Dropopen in new window
887. 鸡蛋掉落open in new window
🔴
本文要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题，只不过他们觉得扔鸡蛋太浪费，改成扔杯子，扔破碗什么的。
具体的问题等会再说，但是这道题的解法技巧很多，光动态规划就好几种效率不同的思路，最后还有一种极其高效数学解法。秉承本书一贯的作风，拒绝过于诡异的技巧，因为这些技巧无法举一反三，学了也不划算。
下面就来用我们一直强调的动态规划通用思路来研究一下这道题。
#一、解析题目这是力扣第 887 题「鸡蛋掉落open in new window」，我描述一下题目：
你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没 ...
