数学篇 LeetCode 刷题小结(一)

本节我们将汇总一些 LeetCode 和数学相关的题。

数学是什么，我们就不需要长篇累牍地说了，从小学到大的。数学在很多很多领域发挥着中流砥柱的作用，这也当然包括了计算机领域了，数学问题很多时候都要数学公式或者原理可循的，本节我们就来汇总一些 LeetCode 和数学相关的题吧。
所有题均来自于leetcode。

阶乘后的零

给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。

示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.

说明: 你算法的时间复杂度应为 O(log n) 。

这个题肯定不能把阶乘后的结果求出来，再数0的个数，那样时间复杂度大于 $O(\log n)$ ，我们需要找规律，这是阶乘的公式。
$n!=1*2*3...*n$
那么在阶乘里面，什么因素会早就末尾的0呢？这是个数论问题。简单来说，就是要知道 $n!$ 里面有多少个10，根据质因数分解，相当于知道 $n!$ 里面有多个2和5，最后结果即2的个数和5的个数取较小值。这个方法当然可以，可惜时间复杂度是 $O(n \log n)$ ，超时了。

找规律，如果我们列出一些数的阶乘展开式，我们会发现 $n!$ 质因数里2的个数总是要比5的个数多，这个缺乏严格数学证明，但是是一个很明显的规律。

这里， $n!$ 后面有多少个0， $n!$ 就有多少个质因数 5。
注：这里简单说明下这个规律(不严谨)，如果一个数有 n 个质因数5，那么考虑4作为因数的个数是要大于等于质因数5的，那质因数2的个数是不是要比4作为因数要多呢？

现在的问题就是要求 $n!$ 有多少个质因数 5。
程序如下：

class Solution {
public:
    int trailingZeroes(int n) {
        int sum=0;
        while(n){
            sum+=(n/5);
            n=n/5;
        }
        return sum;
    }
};

如果这里还不是很理解的话，该题的解题部分有位大佬讲得更详细，点这里。

灯泡开关

初始时有 n 个灯泡关闭。第 1 轮，你打开所有的灯泡。第 2 轮，每两个灯泡你关闭一次。第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。对于第 n 轮，你只切换最后一个灯泡的开关。找出 n 轮后有多少个亮着的灯泡。

示例:

输入: 3
输出: 1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].

你应该返回 1，因为只有一个灯泡还亮着。

咋一看挺简单的，设置一个数组，n次循环解决问题，但对于稍微大点的 n，暴力求解就超时了。

仔细看看这个题，你就会发现，它是个分解因数的问题。
第一轮，所有是1的倍数的数，状态改变。
第二轮，所有是2的倍数的数，状态改变。
以此类推。

那么什么样的数在n次后，还是亮着的呢？
当然是改变奇数次状态的数了，那么什么样的数满足要求呢？
我们这样想，一个数能被奇数个小于等于它本身的数整除，那它是什么数？
质数肯定不是，因为质数能被1和自身整除，那合数？
合数至少能被两个数整除，那什么样的数会被奇数个小于等于它本身的数整除呢？
考虑因数分解。
$a=m* n$
那它有 m，n 这两个因数，那它能被偶数个小于等于它本身的数整除，好像也不行。

真的是这样的吗？
这里可能算是不严谨的地方了。
$a=m* n$
它有 m，n 这两个因数，是有条件的 $(m!=n)$ ，如果 $(m=n)$
$a=n*n$
a 是一个完全平方数，在上面的因数分解中，它只有一个因数 n，而且是唯一的，而且它被奇数个小于等于它本身的数整除。

这个题就变成了找小于等于 n的完全平方数个数。
有了这个思路，这个题很简单了。
程序如下，方法不唯一：

class Solution {
public:
    int bulbSwitch(int n) {
        int res = 0;
        for(int i=1;i<=n;i++){
            if(i*i>n){
                break;
            }
            res++;
        }
        return res;
    }
};

水壶问题

有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？

如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。

你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1: (From the famous "Die Hard" example)

输入: x = 3, y = 5, z = 4
输出: True

示例 2:

输入: x = 2, y = 6, z = 5
输出: False

这个题估计很多人都看过类似的问题，脑筋急转弯里面很常见，一开始我都是直接模拟倒水的过程的，对于小问题还好，但是用程序解决就不会了。

确实，我们可能知道如果一个问题的结果，但是却没有发现通性，我们先看模拟一下倒水的过程，再试着找规律。
就看示例一吧，3:0(左边表示水壶的大小，右边表示水壶当前装的水的量)。
来看看怎么个倒法，可能不唯一。

3:0,5:5
3:3,5:2
3:0,5:2
3:2,5:0
3:2,5:5
3:3,5:4

成功，看看有什么规律，我们发现不管那个水壶，每次加水都是加其容积量，倒水就不一定了，如果倒给对方水壶，取决于对方能装多少水。

再进一步，如果把加水视为+，倒水(不管倒哪)视为-，那么
x：倒水两次，-，-
y：加水两次，+，+

这个时候，
$5+5-3-3=4$

这就是这题的规律了，即两个水壶 x，y 经过若干次加水(+)，倒水(-)后得到 z。
进而
$ax+by=z$
找是否存在这样的 a，b。
这个题就解决了，我们知道数学题很多都有着背后的数学公式和原理的，这题也是，它就是大名鼎鼎的裴蜀定理。
裴蜀定理(或贝祖定理，Bézout's identity)得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程(称为裴蜀等式)：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1。

在密码学中，你也能看到它的身影。

解法可以参考相关资料。
这里只展示程序：

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(x == 0&&y == 0){
            return z == 0;
        }
        return z == 0 || (z % gcd(x,y) == 0 &&x+y >= z);
    }
    int gcd(int x,int y){
        if(y == 0){
            return x;
        }
        int r = x%y;
        return gcd(y,r);
    }
};

Pow(x,n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

这个题如果暴力求解的话，有可能会超时。

若 n 为正数：
$x^{n}=x^{n}$
若 n 为负数：
$x^{n}=(\frac{1}{x})^{n}$
参考了评论区一位大佬的方法，使用二分递归的方法，传送门。

具体的程序如下：

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0)
            return 1;
        if(n==1){
            return x;
        }
        if(n==-1){
            return 1/x;
        }
        double divide=myPow(x,n/2);
        double mode=myPow(x,n%2);
        return divide*divide*mode;
    }
};

第k个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。

示例 1:

输入: n = 3, k = 3
输出: "213"

示例 2:

输入: n = 4, k = 9
输出: "2314"

排列问题在高中我们都学过，如果我们需要列出全部的排列情况，那么我们一般都会按一定的规律列出，不然很容易混淆。
像题目中这样，先排1，再排其他的等等。

这个题的规律还是很明显的。如果是按“标准”来的，我们很容易给出第k个情况，就是实际程序中有些地方需要注意。

首先呢，小于等于n的每个数的阶乘必须知道，这个很好办。之后呢，一位位地来，我们就那示例二来看吧。
n = 4, k = 9
第一位相同的排列有 $(4-1)!$ 种，9/6 = 1，那第一位就是 2 了，之后的排列里面不会出现 2 了，从1，3，4中选，9%6 =3，第二位有 $(3-1)!$ 种，3/2 = 1，第二位就是 3 了，从1，4 中选，1/(2-1)! = 0，第三位就是 1 了，第四位就是4。
所以结果为 “2134”。
具体的程序如下：

class Solution {
public:
    string getPermutation(int n, int k) {
        string nums="1";
        vector<int> f(n+1);
        f[0]=1;
        f[1]=1;
        for(int i=2;i<=n;i++){
            nums=nums+char(i+'0');
            f[i]=i*f[i-1];
        }
        string res="";
        int yushu,t=n;
        for(int i=0;i<t;i++){
            n--;
            yushu=(k-1)/f[n];
            res=res+nums.at(yushu);
            nums.erase(nums.begin()+yushu);
            k=k-yushu*f[n];
        }
        return res;
    }
};

本节内容到此结束，之后将继续更新数学相关的内容。