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

1,511 阅读8分钟

第一道:除数博弈

题目来源于 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! 中 有 35 (来自其中的5, 10, 15), 所以计算 n/5 就可以 。

但是比如 n=25,依旧计算 n/5 ,可以得到 55,分别来自其中的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;
    }
}