「总结」LeetCode 上一行代码就能解决的智力算法题

电玩女神 2024-04-17 05:41 49阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，天天中午 12:15，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

不知不觉更新了 LeetCode 一百多道题目，今天特意总结 LeetCode 上一行代码就能解决的智力算法题，希望你也能领略算法的魅力。

## 第一道：除数博弈 ##

题目来源于 LeetCode 上第 1025 号问题：除数博弈。

### 题目解析 ###

对于这种博弈类的题目，如果没有思路的话我们不妨多举几个例子，尝试着从中找寻规律。

*  假设 `N = 1`，爱丽丝没得选择，直接失败，即 **鲍勃获胜**；
 *  假设 `N = 2`，爱丽丝有选择，她可以选择 `x = 1`，鲍勃面对的就是 `N = 2 - 1 = 1`，无法操作，**爱丽丝获胜**；
 *  假设 `N = 3`，爱丽丝只能选择 `x = 1`，因为选 `x = 2` 不满足 `3 % 2 = 0`，鲍勃面对的就是 `N = 3 - 1 = 2`，参考上面 `N = 2` 的情形，此时鲍勃为 `N = 2` 的先手，**鲍勃获胜**；
 *  假设 `N = 4`，爱丽丝可以选择 `x = 1` 来使鲍勃遇到 `N = 3` 的情况，**爱丽丝获胜**；

貌似有个规律：N 为奇数时， **鲍勃获胜**；N 为偶数时， **爱丽丝获胜**。

是这样吗？

是的。

事实上，无论 N 为多大，最终都是在 **N = 2** 这个临界点结束的。谁最后面对的是 **N = 2** 的情形，谁就能获胜（这句话不太理解的话，仔细看看 N = 2、N = 3 这两种情形）。

接下来，我们得知道一个数学小知识：**奇数的因子（约数）只能是奇数，偶数的因子（约数）可以是奇数或偶数**。

**千万不要忽略 1 也是因子！**

爱丽丝是游戏开始时的先手。

*  当她面对的 N 为偶数时，她 **一定可以** 选到一个 N 的奇数因子 x（比如 1 ），将 N - x 这个奇数传给鲍勃；用 `N - x` 替换黑板上的数字 `N` ，鲍勃面对的就是奇数 N，只能选择 N 的奇数因子 x，`奇数 - 奇数 = 偶数`，此时传给爱丽丝的又是偶数。这样轮换下去爱丽丝会遇到 **N = 2** 的情形，然后获胜；
 *  当爱丽丝遇到的 N 是奇数时，只能传给鲍勃偶数或无法操作 (N = 1) ，无法获胜。

### 代码实现 ###

//@五分钟学算法
    class Solution {
        public boolean divisorGame(int N) {
            return N % 2 == 0;
        }
    }

## 第二道：灯泡开关 ##

题目来源于 LeetCode 上第 319 号问题：灯泡开关。

### 题目分析 ###

首先，因为电灯一开始都是关闭的，所以某一盏灯最后如果是点亮的，必然要被按奇数次开关。

我们假设只有 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盏。

我们不是想求有多少个可开方的数吗，4 是最大的平方根，那么小于 4 的正整数的平方都是在 1~16 内的，是会被按奇数次开关，最终亮着的灯。

就算有的 n 平方根结果是小数，强转成 int 型，也相当于一个最大整数上界，比这个上界小的所有整数，平方后的索引都是最后亮着的灯的索引。所以说我们直接把平方根转成整数，就是这个问题的答案。

### 代码实现 ###

class Solution {
        public int bulbSwitch(int n) {
             return (int)Math.sqrt(n);
        }
    }

## 第三道：3的幂 ##

题目来源于 LeetCode 上第 326 号问题：3的幂。

### 题目解析 ###

正常的思路是不停地去除以 3，看最后的迭代商是否为 1。这种思路的代码使用到了循环，逼格不够高。

这里取巧的方法 **用到了数论的知识：3 的幂次的质因子只有 3**。

题目要求输入的是 int 类型，正数范围是 0 - 231，在此范围中允许的最大的 3 的次方数为 319 = 1162261467 ，那么只要看这个数能否被 n 整除即可。

### 代码实现 ###

//@五分钟学算法
    class Solution {
        public boolean isPowerOfThree(int n) {
             return n > 0 && 1162261467 % n == 0;
        }
    }

## 第四道：2的幂 ##

题目来源于 LeetCode 上第 231 号问题：2的幂。

### 题目解析 ###

如果一个数是 2 的次方数的话，那么它的二进数必然是最高位为 1，其它都为 0 ，那么如果此时我们减 1 的话，则最高位会降一位，其余为 0 的位现在都为变为 1，那么我们把两数相与，就会得到 0。

### 代码实现 ###

//@五分钟学算法
    class Solution {
    public:
        bool isPowerOfTwo(int n) {
              return n > 0 && ((n & (n - 1)) == 0);
        } 
    };

## 第五道：阶乘后的零 ##

题目来源于 LeetCode 上第 172 号问题：阶乘后的零。

### 题目解析 ###

题目很好理解，数阶乘后的数字末尾有多少个零。

最简单粗暴的方法就是先乘完再说，然后一个一个数。

事实上，你在使用暴力破解法的过程中就能发现规律：**这 9 个数字中只有 2（它的倍数） 与 5 （它的倍数）相乘才有 0 出现**。

所以，现在问题就变成了这个阶乘数中能配 **多少对 2 与 5**。

举个复杂点的例子：

`10！= 【 2 *（ 2 * 2 ）* 5 *（ 2 * 3 ）*（ 2 * 2 * 2 ）*（ 2 * 5）】`

在 10！这个阶乘数中可以匹配两对 2 \* 5 ，所以10！末尾有 2 个 0。

可以发现，一个数字进行拆分后 2 的个数肯定是大于 5 的个数的，所以能匹配多少对取决于 5 的个数。（好比现在男女比例悬殊，最多能有多少对异性情侣取决于女生的多少）。

那么问题又变成了 **统计阶乘数里有多少个 5 这个因子**。

需要注意的是，像 25，125 这样的不只含有一个 5 的数字的情况需要考虑进去。

比如 `n = 15`。那么在 `15!` 中 有 `3` 个 `5` (来自其中的`5`, `10`, `15`)， 所以计算 `n/5` 就可以 。

但是比如 `n=25`，依旧计算 `n/5` ，可以得到 `5` 个`5`，分别来自其中的`5, 10, 15, 20, 25`，但是在 `25` 中其实是包含 `2`个 `5` 的，这一点需要注意。

所以除了计算 `n/5` ， 还要计算 `n/5/5 , n/5/5/5 , n/5/5/5/5 , ..., n/5/5/5,,,/5`直到商为0，然后求和即可。

### 代码实现 ###

//@五分钟学算法
    public class Solution {
        public int trailingZeroes(int n) {
            return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
        }
    }

## 第六道：Nim 游戏 ##

题目来源于 LeetCode 上第 292 号问题：Nim 游戏。

### 题目解析 ###

**我们解决这种问题的思路一般都是反着思考：**

如果我能赢，那么最后轮到我取石子的时候必须要剩下 1~3 颗石子，这样我才能一把拿完。

如何营造这样的一个局面呢？显然，如果对手拿的时候只剩 4 颗石子，那么无论他怎么拿，总会剩下 1~3 颗石子，我就能赢。

如何逼迫对手面对 4 颗石子呢？要想办法，让我选择的时候还有 5~7 颗石子，这样的话我就有把握让对方不得不面对 4 颗石子。

如何营造 5~7 颗石子的局面呢？让对手面对 8 颗石子，无论他怎么拿，都会给我剩下 5~7 颗，我就能赢。

这样一直循环下去，我们发现只要踩到 4 的倍数，就落入了圈套，永远逃不出 4 的倍数，而且一定会输。

### 代码实现 ###

public class Solution {
       bool canWinNim(int n) {
        // 如果上来就踩到 4 的倍数，那就认输吧
        // 否则，可以把对方控制在 4 的倍数，必胜
        return n % 4 != 0;
        }
    }

## 第七道：石子游戏 ##

题目来源于 LeetCode 上第 877 号问题：石子游戏。

### 题目解析 ###

显然，亚历克斯总是赢得 2 堆时的游戏。通过一些努力，我们可以获知她总是赢得 4 堆时的游戏。

如果亚历克斯最初获得第一堆，她总是可以拿第三堆。如果她最初取到第四堆，她总是可以取第二堆。第一 + 第三，第二 + 第四 中的至少一组是更大的，所以她总能获胜。

我们可以将这个想法扩展到 N 堆的情况下。设第一、第三、第五、第七桩是白色的，第二、第四、第六、第八桩是黑色的。亚历克斯总是可以拿到所有白色桩或所有黑色桩，其中一种颜色具有的石头数量必定大于另一种颜色的。

因此，亚历克斯总能赢得比赛。

### 代码实现 ###

class Solution {
        public boolean stoneGame(int[] piles) {
            return true;
        }
    }

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/bb354fbf140b4bbe8a5e4184d886bd73.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485538&idx=1&sn=03adf88e7fe8bb7a6df9c1f77b2651b4&chksm=fa0e67e3cd79eef576563214c99121e5dbfc6332a95e45eade3735efc1472ba4c27be086b9bd&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485556&idx=1&sn=344738dd74b211e091f8f3477bdf91ee&chksm=fa0e67f5cd79eee3139d4667f3b94fa9618067efc45a797b69b41105a7f313654d0e86949607&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/e32acd4fe35f4714b75d2b2b3e29f0b9.png