动态规划之博弈问题 一、定义 dp 数组的含义 二、状态转移方程 三、代码实现 四、最后总结 动态规划之博弈问题 上一篇文章 几道智力题 中讨论到一个有趣的「石头游戏」，通过题目的限制条件，这个游戏是先手必胜的。但是智力题终究是智力题，真正的算法问题肯定不会是投机取巧能搞定的。所以，本文就借石头游戏来讲讲「假设两个人都足够聪明，最后谁会获胜...

几个反直觉的概率问题 一、男孩女孩问题 二、生日悖论 三、三门问题 几个反直觉的概率问题 上篇文章 洗牌算法详解 讲到了验证概率算法的蒙特卡罗方法，今天聊点轻松的内容：几个和概率相关的有趣问题。 计算概率有下面两个最简单的原则： 原则一、计算概率一定要有一个参照系，称作「样本空间」，即随机事件可能出现的所有结果。事件 A 发生的概率 = ...

经典动态规划问题：高楼扔鸡蛋 一、解析题目 二、思路分析 三、疑难解答 经典动态规划问题：高楼扔鸡蛋 今天要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题，只不过他们觉得扔鸡蛋太浪费，改成扔杯子，扔破碗什么的。 具体的问题等会再说，但是这道题的解法技巧...

经典动态规划问题：高楼扔鸡蛋（进阶） 二分搜索优化 重新定义状态转移 还可以再优化 经典动态规划问题：高楼扔鸡蛋（进阶） 上篇文章聊了高楼扔鸡蛋问题，讲了一种效率不是很高，但是较为容易理解的动态规划解法。后台很多读者问如何更高效地解决这个问题，今天就谈两种思路，来优化一下这个问题，分别是二分查找优化和重新定义状态转移。 如果还不知道高楼扔鸡蛋...

学习数据结构和算法的框架思维 一、数据结构的存储方式 二、数据结构的基本操作 三、算法刷题指南 四、总结几句 学习数据结构和算法的框架思维 这是好久之前的一篇文章「学习数据结构和算法的框架思维」的修订版。之前那篇文章收到广泛好评，没看过也没关系，这篇文章会涵盖之前的所有内容，并且会举很多代码的实例，教你如何使用框架思维。 首先，这里讲的都...

递归详解 递归详解 为什么要写递归 写递归的技巧 分治算法 递归详解 首先说明一个问题，简单阐述一下递归，分治算法，动态规划，贪心算法这几个东西的区别和联系，心里有个印象就好。 递归是一种编程技巧，一种解决问题的思维方式；分治算法和动态规划很大程度上是递归思想基础上的（虽然动态规划的最终版本大都不是递归了，但解题思想还是离不开递归），解决更...

动态规划之KMP字符匹配算法 一、KMP 算法概述 二、状态机概述 三、构建状态转移图 四、代码实现 五、最后总结 动态规划之KMP字符匹配算法 KMP 算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法，效率很高，但是确实有点复杂。 很多读者抱怨 KMP 算法无法理解，这很正常，想到大学教材上关于 KMP 算法...

二分查找详解 零、二分查找框架 一、寻找一个数（基本的二分搜索） 二、寻找左侧边界的二分搜索 三、寻找右侧边界的二分查找 四、逻辑统一 二分查找详解 先给大家讲个笑话乐呵一下： 有一天阿东到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把阿东拦下，要检查一下哪本书没有登记出借。阿东正准备把每一本书在报警器下过一下，以找出引发警报...

一、对称性加密 二、密钥交换算法 三、非对称加密 四、数字签名 五、公钥证书 六、最后总结 说到密码，我们第一个想到的就是登陆账户的密码，但是从密码学的角度来看，这种根本就不算合格的密码。 为什么呢，因为我们的账户密码，是依靠隐蔽性来达到加密作用：密码藏在我心里，你不知道，所以你登不上我的账户。 然而密码技术认为，「保密」信息总有一天会被扒...

团灭 LeetCode 股票买卖问题 团灭 LeetCode 股票买卖问题 很多读者抱怨 LeetCode 的股票系列问题奇技淫巧太多，如果面试真的遇到这类问题，基本不会想到那些巧妙的办法，怎么办？所以本文拒绝奇技淫巧，而是稳扎稳打，只用一种通用方法解决所用问题，以不变应万变 。 这篇文章用状态机的技巧来解决，可以全部提交通过。不要觉得这个名词高大...