算法实现 拓展延伸 我最近在 LeetCode 上做到两道非常有意思的题目，382 和 398 题，关于水塘抽样算法（Reservoir Sampling），本质上是一种随机概率算法，解法应该说会者不难，难者不会。 我第一次见到这个算法问题是谷歌的一道算法题：给你一个未知长度 的链表，请你设计一个算法，只能遍历一次 ，随机地返回链表中的一个节点。 ...

动态规划之子序列问题解题模板 一、两种思路 二、最长回文子序列 三、代码实现 动态规划之子序列问题解题模板 子序列问题是常见的算法问题，而且并不好解决。 首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。 而且，子序列问题很可能涉及到两个字符串，比如...

双指针技巧总结 一、快慢指针的常见算法 二、左右指针的常用算法 双指针技巧总结 我把双指针技巧再分为两类，一类是「快慢指针」，一类是「左右指针」。前者解决主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或者字符串）中的问题，比如二分查找。 一、快慢指针的常见算法 快慢指针一般都初始化指向链表的头结点 head，前进时...

事件经过 本地演示 吸取教训 好吧，我也做了回标题党，像我这么细心的同学，怎么可能让服务器被入侵呢？ 其实是这样的，昨天我和一个朋友聊天，他说他自己有一台云服务器运行了 Redis 数据库，有一天突然发现数据库里的数据全没了 ，只剩下一个奇奇怪怪的键值对，其中值看起来像一个 RSA 公钥的字符串，他以为是误操作删库了，幸好自己的服务器里没啥重要的数...

递归反转链表的一部分 一、递归反转整个链表 二、反转链表前 N 个节点 三、反转链表的一部分 四、最后总结 递归反转链表的一部分 反转单链表的迭代实现不是一个困难的事情，但是递归实现就有点难度了，如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能够递归实现 呢？ 本文就来由浅入深，step by step 地解决这个问题。如果你还不会...

如何使用单调栈解题 如何使用单调栈解题 栈（stack）是很简单的一种数据结构，先进后出的逻辑顺序，符合某些问题的特点，比如说函数调用栈。 单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。 听起来有点像堆（heap）？不是的，单调栈用途不太广泛，只处理一种典型的问题，叫做 Next ...

LRU算法详解 一、什么是 LRU 算法 二、LRU 算法描述 三、LRU 算法设计 四、代码实现 LRU算法详解 一、什么是 LRU 算法 就是一种缓存淘汰策略。 计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续...

二叉堆详解实现优先级队列 一、二叉堆概览 二、优先级队列概览 三、实现 swim 和 sink 四、实现 delMax 和 insert 五、最后总结 二叉堆详解实现优先级队列 二叉堆（Binary Heap）没什么神秘，性质比二叉搜索树 BST 还简单。其主要操作就两个，sink （下沉）和 swim （上浮），用以维护二叉堆的性质。其主...

团灭 LeetCode 打家劫舍问题 House Robber I House Robber II House Robber III 团灭 LeetCode 打家劫舍问题 有读者私下问我 LeetCode 「打家劫舍」系列问题（英文版叫 House Robber）怎么做，我发现这一系列题目的点赞非常之高，是比较有代表性和技巧性的动态规划题目，今...

二叉搜索树操作集锦 二叉搜索树操作集锦 通过之前的文章框架思维 ，二叉树的遍历框架应该已经印到你的脑子里了，这篇文章就来实操一下，看看框架思维是怎么灵活运用，秒杀一切二叉树问题的。 二叉树算法的设计的总路线：明确一个节点要做的事情，然后剩下的事抛给框架。 void traverse ( TreeNode root ) { /...