本节我们将汇总一些 LeetCode 和数学相关的题。
数学是什么，我们就不需要长篇累牍地说了，从小学到大的。数学在很多很多领域发挥着中流砥柱的作用，这也当然包括了计算机领域了，数学问题很多时候都要数学公式或者原理可循的，本节我们就来汇总一些 LeetCode 和数学相关的题吧。
所有题均来自于leetcode。
阶乘后的零
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
这个题肯定不能把阶乘后的结果求出来，再数0的个数，那样时间复杂度大于 ，我们需要找规律，这是阶乘的公式。
那么在阶乘里面，什么因素会早就末尾的0呢？这是个数论问题。简单来说，就是要知道 里面有多少个10，根据质因数分解，相当于知道
里面有多个2和5，最后结果即2的个数和5的个数取较小值。这个方法当然可以，可惜时间复杂度是
，超时了。
找规律，如果我们列出一些数的阶乘展开式，我们会发现 质因数里2的个数总是要比5的个数多，这个缺乏严格数学证明，但是是一个很明显的规律。
这里， 后面有多少个0，
就有多少个质因数 5。
注：这里简单说明下这个规律(不严谨)，如果一个数有 n 个质因数5，那么考虑4作为因数的个数是要大于等于质因数5的，那质因数2的个数是不是要比4作为因数要多呢？
现在的问题就是要求 有多少个质因数 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和自身整除，那合数？
合数至少能被两个数整除，那什么样的数会被奇数个小于等于它本身的数整除呢？
考虑因数分解。
那它有 m，n 这两个因数，那它能被偶数个小于等于它本身的数整除，好像也不行。
真的是这样的吗？
这里可能算是不严谨的地方了。
它有 m，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：加水两次，+，+
这个时候，
这就是这题的规律了，即两个水壶 x，y 经过若干次加水(+)，倒水(-)后得到 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 为正数：
若 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
第一位相同的排列有 种，9/6 = 1，那第一位就是 2 了，之后的排列里面不会出现 2 了，从1，3，4中 选，9%6 =3，第二位有
种，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;
}
};
本节内容到此结束，之后将继续更新数学相关的内容。
网友评论