二叉堆详解实现优先级队列二叉堆（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 力扣 难度 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 游戏的地图肯定可以抽象成一个二维矩阵，就拿扫雷举例吧，我们可以用下面这个类表示扫雷的棋盘： ...

算法就像搭乐高：带你手撸 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 力扣 难度 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 力扣 难度 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 打家劫舍问题读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： 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 力扣 难度 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"；而模式串 ".*" ...