172.阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示?n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
?思路：
n！中尾随0的数量 = n！可以分解出因子5的个数
因为有因子2和因子5，2X5=10，就可以提供一个0，而n！中只要是偶数就至少可以提供一个因子2，即因子2比因子5多的多，所以n！中的因子5的个数就等于n！中尾随0的个数（拿到一个因子5就可以和因子2凑出一个尾随0）。
class Solution {
public:
//n！的结果中尾随0的数量 = n！可以分解出因子5的个数
//例子：125！=125*124*123*...*2*1
/*
125/5=25，5的倍数肯定可以提供一个因子5，如：5，10，15，20，25...
125/25=5，25的倍数肯定可以提供两个因子5，如：25，50，75，100，125
125/125=1，125的倍数肯定可以提供三个因子5，如：125
所以125！共可以提供25+5+1=31个因子5，也就有31个尾随0。
*/
int trailingZeroes(int n) {
int res=0;
int dis=5;
while(dis<=n)
{
res+=n/dis;
dis*=5;
}
return res;
}
};
793.阶乘函数后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?的数量。
示例 1：
输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4!?均符合 k = 0 的条件。
示例 2：
输入：k = 5
输出：0
解释：没有匹配到这样的 x!，符合 k = 5 的条件。
思路：二分搜索
要求有多少个数满足阶乘后的0的个数等于k，就是在求满足条件的数中，最小的数是多少，最大的数是多少，最大值最小值一减，差就是结果。
因为在穷举 n = 1 ~ LONG_MAX 的过程中，随着?n?的增加，n!?肯定是递增的，阶乘后的0的个数肯定也是递增的，所以可以利用二分查找，找到符合条件的数的最小值（搜索左侧边界），找到符合条件的数的最大值（搜索右侧边界）。
class Solution {
public:
long countZero(long n)//返回n！后的0的个数
{
long res=0;
long dis=5;
while(dis<=n)
{
res+=n/dis;
dis*=5;
}
return res;
}
int preimageSizeFZF(int k)
{
return rightBound(k)-leftBound(k)+1;
}
long rightBound(int k)//搜索右侧边界
{
long low=0;
long high=LONG_MAX;
while(low<high)//左闭右开区间
{
long mid=low+(high-low)/2;
if(countZero(mid)>k)
{
high=mid;
}
else if(countZero(mid)<k)
{
low=mid+1;
}
else//找到了符合条件的数，但是不返回，依然向右逼近
{
low=mid+1;
}
}
return low-1;
}
long leftBound(int k)//搜索左侧边界
{
long low=0;
long high=LONG_MAX;
while(low<high)//左闭右开区间
{
long mid=low+(high-low)/2;
if(countZero(mid)<k)
{
low=mid+1;
}
else if(countZero(mid)>k)
{
high=mid;
}
else//找到符合条件的数，但是不返回，依然向左逼近
{
high=mid;
}
}
return low;
}
};
|