AI summary
type
status
date
slug
summary
category
tags
icon
password
一行代码解决的算法题
下文是我在刷题过程中总结的三道有趣的「脑筋急转弯」题目，可以使用算法编程解决，但只要稍加思考，就能找到规律，直接想出答案。
Nim 游戏
你和你的朋友，两个人一起玩 Nim 游戏：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合， 你作为先手 。
- 每一回合，轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为n的情况下赢得游戏。如果可以赢，返回true；否则，返回false。
我们解决这种问题的思路一般都是反着思考：
如果我能赢，那么最后轮到我取石子的时候必须要剩下 1~3 颗石子，这样我才能一把拿完。
如何营造这样的一个局面呢？显然，如果对手拿的时候只剩 4 颗石子，那么无论他怎么拿，总会剩下 1~3 颗石子，我就能赢。
如何逼迫对手面对 4 颗石子呢？要想办法，让我选择的时候还有 5~7 颗石子，这样的话我就有把握让对方不得不面对 4 颗石子。
如何营造 5~7 颗石子的局面呢？让对手面对 8 颗石子，无论他怎么拿，都会给我剩下 5~7 颗，我就能赢。
这样一直循环下去，我们发现只要踩到 4 的倍数，就落入了圈套，永远逃不出 4 的倍数，而且一定会输。
石头游戏
前面「动态规划应用」中讲过了。先手必胜。
灯泡开关
初始时有n个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第i轮，你每i个灯泡就切换第i个灯泡的开关。直到第n轮，你只需要切换最后一个灯泡的开关。找出并返回n轮后有多少个亮着的灯泡。
我们当然可以用一个布尔数组表示这些灯的开关情况，然后模拟这些操作过程，最后去数一下就能出结果。但是这样显得没有灵性，最好的解法是这样的：
什么？这个问题跟平方根有什么关系？
首先，因为电灯一开始都是关闭的，所以某一盏灯最后如果是点亮的，必然要被按奇数次开关。
我们假设只有 6 盏灯，而且我们只看第 6 盏灯。需要进行 6 轮操作对吧，请问对于第 6 盏灯，会被按下几次开关呢？这不难得出，第 1 轮会被按，第 2 轮，第 3 轮，第 6 轮都会被按。
为什么第 1、2、3、6 轮会被按呢？因为
6=1*6=2*3。一般情况下，因子都是成对出现的，也就是说开关被按的次数一般是偶数次。但是有特殊情况，比如说总共有 16 盏灯，那么第 16 盏灯会被按几次?16 = 1*16 = 2*8 = 4*4其中因子 4 重复出现，所以第 16 盏灯会被按 5 次，奇数次。现在你应该理解这个问题为什么和平方根有关了吧？
假设现在总共有 16 盏灯，我们求 16 的平方根，等于 4，这就说明最后会有 4 盏灯亮着，它们分别是第
1*1=1 盏、第 2*2=4 盏、第 3*3=9 盏和第 4*4=16 盏。就算有的
n 平方根结果是小数，强转成 int 型（向下取整）即可。常用的位操作
先来看几个有趣（但没卵用）的操作：
如果说前 6 个技巧的用处不大，这第 7 个技巧还是比较实用的，利用的是补码编码的符号位。整数编码最高位是符号位，负数的符号位是 1，非负数的符号位是 0，再借助异或的特性，可以判断出两个数字是否异号。
- X % 2^n = X & (2^n – 1)
模运算
% 对计算机来说其实是一个比较昂贵的操作，所以我们可以用 & 运算来求余数。但是注意这个技巧只适用于数组长度是 2 的幂次方的情况。- n & (n-1)
消除数字
n 的二进制表示中的最后一个 1。位 1 的个数
编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
就是让你返回
n 的二进制表示中有几个 1。因为 n & (n - 1) 可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止。2 的幂
给你一个整数n，请你判断该整数是否是 2 的幂次方。如果是，返回true；否则，返回false。
一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1。注意有 n≤0 的特殊情况。
- a ^ a = 0；a ^ 0 = a
只出现一次的数字
给你一个 非空 整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
对于这道题目，我们只要把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素：
丢失的数字
给定一个包含[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。
这道题不难的，我们应该很容易想到，把这个数组排个序，然后遍历一遍，不就很容易找到缺失的那个元素了吗？
或者说，借助数据结构的特性，用一个 HashSet 把数组里出现的数字都储存下来，再遍历
[0,n] 之间的数字，去 HashSet 中查询，也可以很容易查出那个缺失的元素。排序解法的时间复杂度是 O(NlogN)，HashSet 的解法时间复杂度是 O(N)，但是还需要 O(N) 的空间复杂度存储 HashSet。
这个问题其实还有一个特别简单的解法：等差数列求和公式。
题目的意思可以这样理解：现在有个等差数列
0, 1, 2,..., n，其中少了某一个数字，请你把它找出来。那这个数字不就是 sum(0,1,..n) - sum(nums) 嘛？不过，本文的主题是位运算，我们来讲讲如何利用位运算技巧来解决这道题。
再回顾一下异或运算的性质：一个数和它本身做异或运算结果为 0，一个数和 0 做异或运算还是它本身。而且异或运算满足交换律和结合律。
我们假设先把索引补一位，然后让每个元素和自己相等的索引相对应：
这样做了之后，就可以发现除了缺失元素之外，所有的索引和元素都组成一对儿了，现在如果把这个落单的索引 2 找出来，也就找到了缺失的那个元素。
如何找这个落单的数字呢，只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下，也就达到了我们的目的：
游戏中的随机算法
扫雷游戏中雷的位置应该是随机分布的，本章研究一下地图的随机生成算法。
首先一个优化就是对地图的二维矩阵进行「降维打击」，把二维数组转化成一维数组：
这样，我们只要在
[0, m * n) 中选取一个随机数，就相当于在二维数组中随机选取了一个元素。但问题是，我们现在需要随机选出
k 个不同的位置放雷。你可能说，那在 [0, m * n) 中选出来 k 个随机数不就行了？是的，但实际操作起来有些麻烦，因为你很难保证随机数不重复。如果出现重复的随机数，你就得再随机选一次，直到找到
k 个不同的随机数。如果
k 比较小 m * n 比较大，那出现重复随机数的概率还比较低，但如果 k 和 m * n 的大小接近，那么出现重复随机数的概率非常高，算法的效率就会大幅下降。那么，我们有没有更好的办法能够在线性的时间复杂度解决这个问题？
「洗牌算法」
第一个解决方案，我们可以换个思路，避开「在数组中随机选择
k 个元素」这个问题，把问题转化成「如何随机打乱一个数组」。现在想随机初始化
k 颗雷的位置，你可以先把这 k 颗雷放在 board 开头，然后把 board 数组随机打乱，这样雷不就随机分布到 board 数组的各个地方了吗？洗牌算法，或者叫随机乱置算法就是专门解决这个问题的。
打乱数组
给你一个整数数组nums，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。实现Solutionclass:
Solution(int[] nums)使用整数数组nums初始化对象
int[] reset()重设数组到它的初始状态并返回
int[] shuffle()返回数组随机打乱后的结果
从原始数组中随机取一个之前没取过的数字到新的数组中，直接看代码吧：
洗牌算法的时间复杂度是 O(N)，正确性证明：
一个元素 m 被放入第 i 个位置的概率 P = 前 i-1 个位置选择元素时没有选中 m 的概率 * 第 i 个位置选中 m 的概率，即
「水塘抽样算法」
学会了洗牌算法，扫雷游戏的随机初始化问题就解决了。不过别忘了，洗牌算法只是一个取巧方案，我们还是得面对「在若干元素中随机选择
k 个元素」这个终极问题。要知道洗牌算法能够生效的前提是你使用数组这种数据结构，如果让你在一条链表中随机选择
k 个元素，肯定不能再用洗牌算法来蒙混过关了。再比如，假设我们的扫雷游戏中棋盘的长和宽非常大，已经不能在内存中装下一个大小为
m * n 的 board 数组了，我们只能维护一个大小为 k 的数组记录雷的位置。这样的话，我们必须想办法在
[0, m*n) 中随机选取 k 个不同的数字了。这就是常见的随机抽样场景，常用的解法是水塘抽样算法（Reservoir Sampling）。水塘抽样算法是一种随机概率算法，会者不难，难者不会。
链表随机节点
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。实现Solution类：
Solution(ListNode head)使用整数数组初始化对象。
int getRandom()从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。进阶：
- 如果链表非常大且长度未知，该怎么处理？
- 你能否在不使用额外空间的情况下解决此问题？
先说结论，当你遇到第
i 个元素时，应该有 1/i 的概率选择该元素，1 - 1/i 的概率保持原有的选择。直接看代码：
为什么每次以
1/i 的概率更新结果就可以保证结果是平均随机的？我们来证明一下，假设总共有
n 个元素，那么对于第 i 个元素，他需要在第 i 次被选中，在后面一直不被替换，概率为：同理，如果要在单链表中随机选择
k 个数，只要在第 i 个元素处以 k/i 的概率选择该元素，以 1 - k/i 的概率保持原有选择即可。代码如下：对于算法正确性的数学证明，和上面区别不大：
虽然每次更新选择的概率增大了
k 倍，但是选到具体第 i 个元素的概率还是要乘 1/k，也就回到了上一个推导。「蒙特卡洛验证法」
蒙特卡罗方法也成统计模拟方法，是指使用随机数来解决很多计算问题的方法。他的工作原理就是两件事：不断抽样、逐渐逼近。
比如，我们可以这样检验水塘抽样算法
sample 函数的正确性：当然你可以做更细致的检查，不过粗略看看，各个元素被选中的次数大致是相同的，这个算法实现的应该没啥问题。
对于洗牌算法中的
shuffle 函数也可以采取类似的验证方法，我们可以跟踪某一个元素 x 被打乱后的索引位置，如果 x 落在各个索引的次数基本相同，则说明算法正确。两道常考的阶乘算法题
阶乘后的零
给定一个整数n，返回n!结果中尾随零的数量。
肯定不可能真去把
n! 的结果算出来，阶乘增长可是比指数增长都恐怖，趁早死了这条心吧。首先末尾有多少个 0 ，只需要给当前数乘以一个 10 就可以加一个 0。
再具体对于 5!，也就是 5 * 4 * 3 * 2 * 1 = 120，我们发现结果会有一个 0，原因就是 2 和 5 相乘构成了一个 10。而对于 10 的话，其实也只有 2 * 5 可以构成，所以我们只需要找有多少对 2/5。
我们把每个乘数再稍微分解下，看一个例子。
11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1
对于含有 2 的因子的话是 1 * 2, 2 * 2, 3 * 2, 4 * 2 ...
对于含有 5 的因子的话是 1 * 5, 2 * 5...
含有 2 的因子每两个出现一次，含有 5 的因子每 5 个出现一次，所有 2 出现的个数远远多于 5，换言之找到一个 5，一定能找到一个 2 与之配对。所以我们只需要找有多少个 5。
直接的，我们只需要判断每个累乘的数有多少个 5 的因子即可。
效率还不够高，我们继续分析。
因为每隔 5 个数出现一个 5，所以计算出现了多少个 5，我们只需要用 n/5 就可以算出来。
但还没有结束，继续分析。
... * (1 * 5) * ... * (1 * 5 * 5) * ... * (2 * 5 * 5) * ... * (3 * 5 * 5) * ... * n
每隔 25 个数字，出现的是两个 5，所以除了每隔 5 个数算作一个 5，每隔 25 个数，还需要多算一个 5。
也就是我们需要再加上 n / 25 个 5。
同理我们还会发现每隔 5 * 5 * 5 = 125 个数字，会出现 3 个 5，所以我们还需要再加上 n / 125 。
综上，规律就是每隔 5 个数，出现一个 5，每隔 25 个数，出现 2 个 5，每隔 125 个数，出现 3 个 5... 以此类推。
最终 5 的个数就是 n / 5 + n / 25 + n / 125 ...
阶乘后 K 个零
f(x)是x!末尾是 0 的数量。回想一下x! = 1 * 2 * 3 * ... * x，且0! = 1。
- 例如，
f(3) = 0，因为3! = 6的末尾没有 0 ；而f(11) = 2，因为11!= 39916800末端有 2 个 0 。给定k，找出返回能满足f(x) = k的非负整数x的数量。
现在是给你一个非负整数
K，问你有多少个 n，使得 n! 结果末尾有 K 个 0。一个直观地暴力解法就是用上一题的函数穷举呗。但是
trailingZeroes(n) 是一个递增函数，那么就可以用二分查找了。搜索有多少个
n 满足 trailingZeroes(n) == K，其实就是在问，满足条件的 n 最小是多少，最大是多少，最大值和最小值一减，就可以算出来有多少个 n 满足条件了，对吧？那不就是「二分查找」中「搜索左侧边界」和「搜索右侧边界」这两个事儿嘛？上界设置为 5k 是因为：
所以有
高效寻找素数
计数质数
给定整数n，返回 所有小于非负整数n的质数的数量 。
暴力解法：
这样写的话时间复杂度 O(n^2)，问题很大。首先你用
isPrime 函数来辅助的思路就不够高效。接下来介绍的方法叫做「素数筛选法」，这个方法是古希腊一位名叫埃拉托色尼的大佬发明的。
首先从 2 开始，我们知道 2 是一个素数，那么 2 × 2 = 4, 3 × 2 = 6, 4 × 2 = 8... 都不可能是素数了。
然后我们发现 3 也是素数，那么 3 × 3 = 9, 4 × 3 = 12... 也都不可能是素数了。
代码如下：
埃氏筛法仍有优化空间，它会将一个合数重复多次标记。有没有什么办法省掉无意义的步骤呢？答案是肯定的。
如果能让每个合数都只被标记一次(比如 12 会被 2*6 和 3*4 标记)，那么时间复杂度就可以降到 了。
有一种线性筛法，也叫欧拉筛法，目标是每个数只被它最小的质因数筛去。原理参考，比较难理解，建议背板子。
正确性证明：
假设我们要筛掉合数 a，且 a 的最小质因数为 p，令 a=p*b。那么显然 b<a，b 先被外层循环碰到。现在 b 要筛掉它的倍数。因为 p 是 a 的最小质因数，所以 b 的最小质因数必不小于 p，这样就保证 b 筛掉 a 前不会在第二个 break 处跳出循环。即使 b 的最小质因数等 p，也会先筛掉 a 后再退出循环。这样就保证了每个合数都会被筛掉。
时间复杂度证明：
我们的核心就是要证明一个合数只会被筛掉一次。首先，对于 a=p*b，b 当然只会筛掉 a 一次，因为我们从小到大枚举 prime，也就是说 b*prime[j］递增，因此不可能遇到 a 两次。会不会有其他的数筛掉 a 呢？假设 a 又被 c 筛掉了，其中 a=p’*c，p’ 就是 c 用来筛掉 a 的 prime。
- 若 c>b，则 p’<p，与 p 是 a 最小的质因数矛盾，假设不成立；
- 若 c<b，则 p’>p，这意味着 p 是 c 的质因数。那么 c 从小到大筛掉它的素数倍，在筛到 p*c 时就 break 了，所以根本轮不到 a。
如何高效进行模幂运算
超级次方
你的任务是计算a^b对1337取模，a是一个正整数，b是一个非常大的正整数且会以数组形式给出。
首先明确问题：现在
b 是一个数组，不能表示成整型，而且数组的特点是随机访问，删除最后一个元素比较高效。不考虑求模的要求，以
b = [1,5,6,4] 来举例，结合指数运算的法则，我们可以发现这样的一个规律：
如何处理 (a * b) % base，避免溢出？
(a * b) % k = (a % k) * (b % k) % k完整代码如下：
快速求幂的算法不止一个，就说一个我们应该掌握的基本思路吧。利用幂运算的性质，我们可以写出这样一个递归式：
这个思想肯定比直接用 for 循环求幂要高效，因为有机会直接把问题规模（
b 的大小）直接减小一半，该算法的复杂度肯定是 log 级了。寻找缺失和重复元素
错误的集合
集合s包含从1到n的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。给定一个数组nums代表了集合S发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
之前的位操作章节讲过与索引异或来找缺失的元素，但是这题的技巧不同。
现在的问题是，有一个元素重复了，同时导致一个元素缺失了，这会产生什么现象呢？会导致有两个元素对应到了同一个索引，而且会有一个索引没有元素对应过去。
那么，如果我能够通过某些方法，找到这个重复对应的索引，不就是找到了那个重复元素么？找到那个没有元素对应的索引，不就是找到了那个缺失的元素了么？
那么，如何不使用额外空间判断某个索引有多少个元素对应呢？这就是这个问题的精妙之处了：
将元素视为索引，把对应的元素变成负数，以表示这个索引被对应过一次了。
代码如下：
其实，元素从 1 开始是有道理的，也必须从一个非零数开始。因为如果元素从 0 开始，那么 0 的相反数还是自己，所以如果数字 0 出现了重复或者缺失，算法就无法判断 0 是否被访问过。
几个反直觉的概率问题
男孩女孩问题
假设有一个家庭，有两个孩子，现在告诉你其中有一个男孩，请问另一个也是男孩的概率是多少？
很多人，包括我在内，不假思索地回答：1/2 啊，因为另一个孩子要么是男孩，要么是女孩，而且概率相等呀。但是实际上，答案是 1/3。
上述思想为什么错误呢？因为没有正确计算样本空间，导致原则一计算错误。有两个孩子，那么样本空间为 4，即哥哥妹妹，哥哥弟弟，姐姐妹妹，姐姐弟弟这四种情况。已知有一个男孩，那么排除姐姐妹妹这种情况，所以样本空间变成 3。另一个孩子也是男孩只有哥哥弟弟这 1 种情况，所以概率为 1/3。
生日悖论
生日悖论是由这样一个问题引出的：一个屋子里需要有多少人，才能使得存在至少两个人生日是同一天的概率达到 50%？
答案是 23 个人，也就是说房子里如果有 23 个人，那么就有 50% 的概率会存在两个人生日相同。这个结论看起来不可思议，所以被称为悖论。
我们先计算 23 个人生日都唯一（不重复）的概率。只有 1 个人的时候，生日唯一的概率是
365/365，2 个人时，生日唯一的概率是 365/365 × 364/365，以此类推可知 23 人的生日都唯一的概率：三门问题
这个游戏很经典了：游戏参与者面对三扇门，其中两扇门后面是山羊，一扇门后面是跑车。参与者只要随便选一扇门，门后面的东西就归他（跑车的价值当然更大）。但是主持人决定帮一下参与者：在他选择之后，先不急着打开这扇门，而是由主持人打开剩下两扇门中的一扇，展示其中的山羊（主持人知道每扇门后面是什么），然后给参与者一次换门的机会，此时参与者应该换门还是不换门呢？
和男孩女孩问题一样，把所有可能穷举出来，看图就很明白了，答案是换门，中奖概率为 2/3。