Kruskal 最小生成树算法 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 1135. Connecting Cities With Minimum Costopen in new window🔒 1135. 最低成本联通所有城市open in new window🔒 🟠 1584. Min Cost to Connect All Pointsopen in new window 1584. 连接所有点的最小费用open in new window 🟠 261. Graph Valid Treeopen in new window🔒 261. 以图判树open in new window🔒 🟠 图论中知名度比较高的算法应该就是 Dijkstra 最短路径算法，环检测和拓扑排序，二分图判定算法 以及今天要讲的最小生成树（Minimum Spanning Tree）算法了。 最小生成树算法主要有 Prim 算法（普里姆算法）和 Kruskal 算法（克鲁斯卡尔算法）两种，这两种算法虽然都运用了贪心思想，但 ...

题目不让我干什么，我偏要干什么 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： 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，也就是说这个列表中的每一个元素可能是个整数，可能又是个列表，这样无限递归嵌套下去…… NestedInt ...

一道求中位数的算法题把我整不会了 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： 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&nbs ...

一道数组去重的算法题把我整不会了 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： 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& ...

二分搜索怎么用？我又总结了套路 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： 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 的二分搜索算法。 但是前文总结的二分搜索代码框架仅仅局 ...

带权重的随机选择算法 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 528. Random Pick with Weightopen in new window 528. 按权重随机选择open in new window 🟠 - 剑指 Offer II 071. 按权重生成随机数open in new window 🟠 写这篇的文章的原因是玩 LOL 手游。 我有个朋友抱怨说打排位匹配的队友太菜了，我就说我打排位觉得队友都挺行的啊，好像不怎么坑？ 朋友意味深长地说了句：一般隐藏分比较高的玩家，排位如果排不到实力相当的队友，就会排到一些菜狗。 嗯？我想了几秒钟感觉这小伙子不对劲，他意思是说我隐藏分低，还是说我就是那条菜狗？ 我立马要求和他开黑打一把，证明我不是菜狗，他才是菜狗。开黑结果这里不便透露，大家猜猜吧。 打完之后我就来发文了，因为我对游戏的匹配机制有了一点思考。 所谓「隐藏分」我不知道是不是真的，毕竟匹配机制是所有竞技类游戏的核心环节，想必非常复杂，不是简单几个指标就能搞定的。 但是如果把这个「隐藏分」机制 ...

滑动窗口算法延伸：Rabin Karp 字符匹配算法 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 187. Repeated DNA Sequencesopen in new window 187. 重复的DNA序列open in new window 🟠 28. Find the Index of the First Occurrence in a Stringopen in new window 28. 找出字符串中第一个匹配项的下标open in new window 🟠 经常有读者留言，请我讲讲那些比较经典的算法，我觉得有这个必要，主要有以下原因： 1、经典算法之所以经典，一定是因为有独特新颖的设计思想，那当然要带大家学习一波。 2、我会尽量从最简单、最基本的算法切入，带你亲手推导出来这些经典算法的设计思想，自然流畅地写出最终解法。一方面消除大多数人对算法的恐惧，另一方面可以避免很多人对算法死记硬背的错误习惯。 我之前用状态机的思路讲解了 KMP 算法open in new window，说实话 KMP 算 ...

动态规划穷举的两种视角 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 115. Distinct Subsequencesopen in new window 115. 不同的子序列open in new window 🔴 - 剑指 Offer II 097. 子序列的数目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）怎么做，我发现这一系列题目的点赞非常之高，是比较有代表性和技巧性的动态规划题目，今天就来聊聊这道题目。 打家劫舍系列总共有三 ...