一、子集 二、组合 三、排列 今天就来聊三道考察频率高，而且容易让人搞混的算法问题，分别是求子集（subset），求排列（permutation），求组合（combination）。 这几个问题都可以用回溯算法模板解决，同时子集问题还可以用数学归纳思想解决。读者可以记住这几个问题的回溯套路，就不怕搞不清了。 一、子集 问题很简单，输入一个不包...

动态规划之四键键盘 第一种思路 第二种思路 最后总结 动态规划之四键键盘 四键键盘问题很有意思，而且可以明显感受到：对 dp 数组的不同定义需要完全不同的逻辑，从而产生完全不同的解法。 首先看一下题目： 如何在 N 次敲击按钮后得到最多的 A？我们穷举呗，每次有对于每次按键，我们可以穷举四种可能，很明显就是一个动态规划问题。 第一...

为什么我推荐《算法4》 一、二分图的应用 二、套汇的算法 三、最后说几句 为什么我推荐《算法4》 咱们的公众号有很多硬核的算法文章，今天就聊点轻松的，就具体聊聊我非常“鼓吹”的《算法4》。这本书我在之前的文章多次推荐过，但是没有具体的介绍，今天就来正式介绍一下。。 我的推荐不会直接甩一大堆书目，而是会联系实际生活，讲一些书中有趣有用的知识，无...

FloodFill算法详解及应用 一、构建框架 二、研究细节 三、处理细节 四、拓展延伸：自动魔棒工具和扫雷 FloodFill算法详解及应用 啥是 FloodFill 算法呢，最直接的一个应用就是「颜色填充」，就是 Windows 绘画本中那个小油漆桶的标志，可以把一块被圈起来的区域全部染色。 这种算法思想还在许多其他地方有应用。比如...

动态规划设计：最长递增子序列 一、动态规划解法 二、二分查找解法 动态规划设计：最长递增子序列 很多读者反应，就算看了前文动态规划详解 ，了解了动态规划的套路，也不会写状态转移方程，没有思路，怎么办？本文就借助「最长递增子序列」来讲一种设计动态规划的通用技巧：数学归纳思想。 最长递增子序列（Longest Increasing Subseque...

滑动窗口技巧 一、最小覆盖子串 二、找到字符串中所有字母异位词 三、无重复字符的最长子串 最后总结 滑动窗口技巧 本文详解「滑动窗口」这种高级双指针技巧的算法框架，带你秒杀几道高难度的子字符串匹配问题。 LeetCode 上至少有 9 道题目可以用此方法高效解决。但是有几道是 VIP 题目，有几道题目虽不难但太复杂，所以本文只选择点赞最高，...

一行代码就能解决的算法题 一、Nim 游戏 二、石头游戏 三、电灯开关问题 一行代码就能解决的算法题 下文是我在 LeetCode 刷题过程中总结的三道有趣的「脑筋急转弯」题目，可以使用算法编程解决，但只要稍加思考，就能找到规律，直接想出答案。 一、Nim 游戏 游戏规则是这样的：你和你的朋友面前有一堆石子，你们轮流拿，一次至少拿一颗，最...

动态规划答疑篇 一、最优子结构详解 二、dp 数组的遍历方向 动态规划答疑篇 这篇文章就给你讲明白两个问题： 1、到底什么才叫「最优子结构」，和动态规划什么关系。 2、为什么动态规划遍历 dp 数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历。 一、最优子结构详解 「最优子结构」是某些问题的一种特定性质，并不是动态规划问题...

动态规划之正则表达 一、热身 二、处理点号「.」通配符 三、处理「*」通配符 四、动态规划 五、最后总结 动态规划之正则表达 之前的文章「动态规划详解」收到了普遍的好评，今天写一个动态规划的实际应用：正则表达式。如果有读者对「动态规划」还不了解，建议先看一下上面那篇文章。 正则表达式匹配是一个很精妙的算法，而且难度也不小。本文主要写两个正...

洗牌算法 一、洗牌算法 二、蒙特卡罗方法验证正确性 三、最后总结 洗牌算法 我知道大家会各种花式排序算法，但是如果叫你打乱一个数组，你是否能做到胸有成竹？即便你拍脑袋想出一个算法，怎么证明你的算法就是正确的呢？乱序算法不像排序算法，结果唯一可以很容易检验，因为「乱」可以有很多种，你怎么能证明你的算法是「真的乱」呢？ 所以我们面临两个问题： ...