二叉堆详解实现优先级队列
二叉堆（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
力扣
难度
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 ...
目标和：背包问题的变体
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
494. Target Sumopen in new window
494. 目标和open in new window
🟠
-
剑指 Offer II 102. 加减的目标值open in new window
🟠
我们前文经常说回溯算法和递归算法有点类似，有的问题如果实在想不出状态转移方程，尝试用回溯算法暴力解决也是一个聪明的策略，总比写不出来解法强。
那么，回溯算法和动态规划到底是啥关系？它俩都涉及递归，算法模板看起来还挺像的，都涉及做「选择」，真的酷似父与子。
那么，它俩具体有啥区别呢？回溯算法和动态规划之间，是否可能互相转化呢？
今天就用力扣第 494 题「目标和open in new window」来详细对比一下回溯算法和动态规划，题目如下：
给你输入一个非负整数数组 nums 和一个目标值 target，现在你可以给每一个元素 nums[i] 添加正号 + 或负号 -，请你计算有几种符号的组合能够使得 nums 中元素的和为 tar ...
经典动态规划：戳气球
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
312. Burst Balloonsopen in new window
312. 戳气球open in new window
🔴
今天我们要聊的这道题「Burst Balloon」和之前我们写过的那篇 经典动态规划：高楼扔鸡蛋问题 分析过的高楼扔鸡蛋问题类似，知名度很高，但难度确实也很大。因此我的公众号就给这道题赐个座，来看一看这道题目到底有多难。
它是力扣第 312 题「戳气球open in new window」，题目如下：
312. 戳气球 | 力扣 open in new window | LeetCode open in new window |有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以 ...
经典动态规划：正则表达式
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
LeetCode
力扣
难度
10. Regular Expression Matchingopen in new window
10. 正则表达式匹配open in new window
🔴
-
剑指 Offer 19. 正则表达式匹配open in new window
🔴
正则表达式是一个非常强力的工具，本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「正则表达式匹配open in new window」就要求我们实现一个简单的正则匹配算法，包括「.」通配符和「*」通配符。
这两个通配符是最常用的，其中点号「.」可以匹配任意一个字符，星号「*」可以让之前的那个字符重复任意次数（包括 0 次）。
比如说模式串 ".a*b" 就可以匹配文本 "zaaab"，也可以匹配 "cb"；模式串 "a..b" 可以匹配文本 "amnb"；而模式串 ".*&quo ...
经典动态规划：高楼扔鸡蛋
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
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，在这层楼将鸡蛋扔下去，鸡 ...
动态规划之子序列问题解题模板
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
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
力扣
难度
1024. Video Stitchingopen in new window
1024. 视频拼接open in new window
🟠
前面发过几个视频，也算是对视频剪辑入了个门。像我这种非专业剪辑玩家，不做什么宏大特效电影镜头，只是做个视频教程，其实也没啥难度，只需要把视频剪流畅，所以用到最多的功能就是切割功能，然后删除和拼接视频片接。
没有剪过视频的读者可能不知道，在常用的剪辑软件中视频被切割成若干片段之后，每个片段都可以还原成原始视频。
就比如一个 10 秒的视频，在中间切一刀剪成两个 5 秒的视频，这两个五秒的视频各自都可以还原成 10 秒的原视频。就好像蚯蚓，把自己切成 4 段就能搓麻，把自己切成 11 段就可以凑一个足球队。
剪视频时，每个视频片段都可以抽象成了一个个区间，时间就是区间的端点，这些区间有的相交，有的不相交……
假设剪辑软件不支持将视频片段还原成原视频，那么如果给我若干视频片段，我怎么将它们还原成原视频呢？
🌟
🌟 ...
