力扣- -階乘函數(shù)后K個(gè)零

文章目錄

• 力扣- -階乘函數(shù)后K個(gè)零
• • 一、172. 階乘后的零
  • 二、分析
  • 三、代碼
  • 四、階乘函數(shù)后K個(gè)零
  • 五、分析
  • 六、完整代碼

一、172. 階乘后的零

二、分析

• 求n!中末尾0的個(gè)數(shù)：
• 0的來(lái)源 2 * 5 ,所以一對(duì)2和5即可產(chǎn)生一個(gè)0,所以0的個(gè)數(shù)即為min(階乘中5的個(gè)數(shù)和2的個(gè)數(shù))
• 又因?yàn)槭?的倍數(shù)的數(shù)一定比是5的倍數(shù)的數(shù)多 所以2的個(gè)數(shù)一定>=5的個(gè)數(shù) 所以只需要統(tǒng)計(jì) 5 的個(gè)數(shù)了

• 例如 5！ = 1 * 2 * 3 * 4 * 5

• 會(huì)產(chǎn)生3個(gè)2和1個(gè)5

• 一個(gè)2和一個(gè)5配對(duì)出現(xiàn)0 ，所以5!末尾只有一個(gè)零

• 而在 n = 25 時(shí) 可以產(chǎn)生5的有 5 10 15 20 25

• 即 n/5 = 5個(gè) 然而 25 = 5*5 所以少算了一個(gè)5

• n>=25時(shí),故而需要補(bǔ)上它 因此所有可以產(chǎn)生25的也要加上

• 即為 n/5 + n/25 然而 125 = 5*25 所以又少算了一個(gè)5

• n>=125時(shí),故而需要補(bǔ)上它。 因此所有可以產(chǎn)生125的也要加上

• 即為 n/5 + n/25 + n/125 然鵝 625 = 5*125 所以又少算了一個(gè)5

• 繼續(xù)補(bǔ)上…

• 所以最終為 n/5 + n/25 + n/125 + n/625 + …

• 即 n/5 + n/5/5 + n/5/5/5 + n/5/5/5/5 + ...

三、代碼

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

四、階乘函數(shù)后K個(gè)零

五、分析

• 現(xiàn)在是給你一個(gè)非負(fù)整數(shù)K，問(wèn)你有多少個(gè)n，使得n!結(jié)果末尾有K個(gè) 0。

• 一個(gè)直觀地暴力解法就是窮舉唄，因?yàn)殡S著n的增加，n!肯定是遞增的，trailingZeroes(n)肯定也是遞增的，偽碼邏輯如下：

class Solution { public:int preimageSizeFZF(int K) {int res = 0;for (int n = 0; n < +inf; n++) {if (trailingZeroes(n) < K) {continue;}if (trailingZeroes(n) > K) {break;}if (trailingZeroes(n) == K) {res++;}}return res;} };

• 這種做法效率比較低，對(duì)于這種具有單調(diào)性的函數(shù)，用 for 循環(huán)遍歷，可以用二分查找進(jìn)行降維打擊

• 搜索有多少個(gè)n滿足trailingZeroes(n) == K，其實(shí)就是在問(wèn)，滿足條件的n最小是多少，最大是多少，最大值和最小值一減，就可以算出來(lái)有多少個(gè)n滿足條件了。

• 那不就是二分查找「搜索左側(cè)邊界」和「搜索右側(cè)邊界」這兩個(gè)事兒嘛？

• 因?yàn)槎植檎倚枰o一個(gè)搜索區(qū)間，也就是上界和下界，上述偽碼中n的下界顯然是 0，但上界是+inf，這個(gè)正無(wú)窮應(yīng)該如何表示出來(lái)呢？

• 首先，數(shù)學(xué)上的正無(wú)窮肯定是無(wú)法編程表示出來(lái)的，我們一般的方法是用一個(gè)非常大的值，大到這個(gè)值一定不會(huì)被取到。

• 比如說(shuō) int 類型的最大值INT_MAX（2^31 - 1，大約 31 億），還不夠的話就 long類型的最大值LONG_MAX（2^63 - 1，這個(gè)值就大到離譜了）。

• 那么我怎么知道需要多大才能「一定不會(huì)被取到」呢？這就需要認(rèn)真讀題，看看題目給的數(shù)據(jù)范圍有多大。

• 這道題目實(shí)際上給了限制，K是在[0,10^9 ]區(qū)間內(nèi)的整數(shù)，也就是說(shuō)，trailingZeroes(n)的結(jié)果最多可能達(dá)到10^9。

• 然后我們可以反推，當(dāng)trailingZeroes(n)結(jié)果為10^9時(shí)，n為多少？這個(gè)不需要你精確計(jì)算出來(lái)，你只要找到一個(gè)數(shù)hi，使得trailingZeroes(hi)比10^9大，就可以把hi當(dāng)做正無(wú)窮，作為搜索區(qū)間的上界。

• 剛才說(shuō)了，trailingZeroes函數(shù)是單調(diào)函數(shù)，那我們就可以猜，先算一下trailingZeroes(INT_MAX)的結(jié)果，比10^{9小一些，那再用LONG_MAX算一下，遠(yuǎn)超10}9了，所以LONG_MAX可以作為搜索的上界。

注意為了避免整型溢出的問(wèn)題，trailingZeroes函數(shù)需要把所有數(shù)據(jù)類型改成 long：

// 邏輯不變，數(shù)據(jù)類型全部改成 long long trailingZeroes(long n) {long res = 0;for (long d = n; d / 5 > 0; d = d / 5) {res += d / 5;}return res; }

現(xiàn)在就明確了問(wèn)題：

• n屬于區(qū)間[0,LONG_MAX]，我們要尋找滿足trailingZeroes(n) == K的左側(cè)邊界和右側(cè)邊界。

六、完整代碼

class Solution { public:/* 主函數(shù) */int preimageSizeFZF(int K) {// 左邊界和右邊界之差 + 1 就是答案return right_bound(K) - left_bound(K) + 1;}/* 搜索 trailingZeroes(n) == K 的左側(cè)邊界 */long left_bound(int target) {long lo = 0, hi = LONG_MAX;while (lo < hi) {long mid = lo + (hi - lo) / 2;if (trailingZeroes(mid) < target) {lo = mid + 1;} else if (trailingZeroes(mid) > target) {hi = mid;} else {hi = mid;}}return lo;}/* 搜索 trailingZeroes(n) == K 的右側(cè)邊界 */long right_bound(int target) {long lo = 0, hi = LONG_MAX;while (lo < hi) {long mid = lo + (hi - lo) / 2;if (trailingZeroes(mid) < target) {lo = mid + 1;} else if (trailingZeroes(mid) > target) {hi = mid;} else {lo = mid + 1;}}return lo - 1;}long trailingZeroes(long n) {long res = 0;for (long d = n; d / 5 > 0; d = d / 5) {res += d / 5;}return res;} };

總結(jié)

以上是生活随笔為你收集整理的力扣- -阶乘函数后K个零的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。