第一次看到793題的時(shí)候我盯著題目看了兩分鐘第一反應(yīng)是這題和二分有什么關(guān)系階乘、尾零、K三個(gè)詞放在一起像是一道背結(jié)論的數(shù)學(xué)題。等我把“二分答案”四個(gè)字重新讀進(jìn)腦子才反應(yīng)過(guò)來(lái)真正的考點(diǎn)其實(shí)不在階乘怎么算而在“怎么把一個(gè)求個(gè)數(shù)的問(wèn)題變成一個(gè)在值域上二分查找的問(wèn)題”。這道題的全名很長(zhǎng)——階乘函數(shù)后 K 個(gè)零刷過(guò)在線題庫(kù)的應(yīng)該都見(jiàn)過(guò)編號(hào)是793。題面一句話給定非負(fù)整數(shù)K問(wèn)有多少個(gè)非負(fù)整數(shù)n滿足 n! 的末尾恰好有 K 個(gè)零。很多人一上來(lái)就慌了因?yàn)閚可以巨大K最大能到1e9直接枚舉n肯定不行。但這道題恰恰是“二分答案”這一套路里特別經(jīng)典的入門(mén)題練好它對(duì)后面啃第K小、第K大類(lèi)題目幫助很大。1. 先搞懂題目到底在問(wèn)什么1.1 階乘尾零是怎么算出來(lái)的n! 的末尾有多少個(gè)零本質(zhì)是在問(wèn)“n! 這個(gè)數(shù)因子10出現(xiàn)了多少次”。10 2 × 5所以只要數(shù)一數(shù)n!的質(zhì)因子分解里有幾對(duì)2和5尾零就有幾個(gè)。這里有個(gè)關(guān)鍵直覺(jué)2的個(gè)數(shù)永遠(yuǎn)比5多。1到n之間每?jī)蓚€(gè)數(shù)才有一個(gè)偶數(shù)但每五個(gè)數(shù)才有一個(gè)5的倍數(shù)理論上前者出現(xiàn)的頻率遠(yuǎn)高于后者。所以尾零的個(gè)數(shù)完全由因子5的個(gè)數(shù)決定我們只需要統(tǒng)計(jì)1到n中所有數(shù)一共貢獻(xiàn)了多少個(gè)質(zhì)因子5。怎么數(shù)用除法連除累加零的個(gè)數(shù) f(n) n/5 n/25 n/125 ...為什么這么加n/5 表示1到n中有多少個(gè)5的倍數(shù)每個(gè)至少貢獻(xiàn)一個(gè)5但像25、50、75這類(lèi)數(shù)本身有兩個(gè)5因子第二個(gè)5因子被漏掉了所以再加 n/25同理125有三個(gè)5因子前兩步只統(tǒng)計(jì)了兩個(gè)于是再加 n/125一直加到商為0為止?？磧蓚€(gè)小例子。10! 3628800末尾2個(gè)零。用公式算10/5 210/25 0總數(shù)為2正確。25!末尾6個(gè)零。公式算25/5 525/25 125/125 0總數(shù)為6。手算也能驗(yàn)證25這個(gè)數(shù)內(nèi)部就藏了2個(gè)5因子所以比f(wàn)(24)多跳了2。這個(gè)公式和實(shí)現(xiàn)都不復(fù)雜復(fù)雜的是“知道有公式之后接下來(lái)怎么用它”。1.2 尾零個(gè)數(shù)序列的真實(shí)長(zhǎng)相平臺(tái)、跳躍與單調(diào)按n從小到大把f(n)列出來(lái)你會(huì)看到一段很有意思的序列n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... f 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 ...規(guī)律很明顯f(n)是單調(diào)不減的n變大尾零數(shù)只會(huì)增加或持平不會(huì)減少。連續(xù)5個(gè)數(shù)往往共享同一個(gè)f值。因?yàn)橥瑯游擦銛?shù)量會(huì)一直持續(xù)到下一個(gè)5的倍數(shù)之前平臺(tái)寬度最多是5。每到5的倍數(shù)值會(huì)往上跳但有時(shí)跳1有時(shí)跳更多。比如f(24)4但f(25)6直接跳過(guò)5這個(gè)值。這里有一層容易忽略的信息既然f(n)會(huì)跳檔那么K5這種值就找不到任何n對(duì)應(yīng)它。題目問(wèn)“有多少個(gè)n滿足f(n)K”答案完全可能是0。這不是特殊情況而是這道題的常態(tài)。想通這條序列后面寫(xiě)二分時(shí)才能明白為什么要找左邊界和右邊界。2. 為什么這題要二分“答案”而不是二分“下標(biāo)”2.1 單調(diào)性是二分答案的入場(chǎng)券很多同學(xué)一提到二分腦子里只有“給一個(gè)有序數(shù)組二分查找某個(gè)元素”。但二分真正的價(jià)值在于只要一個(gè)函數(shù)在定義域上是單調(diào)的我們就可以在值域上做查找而不需要精確知道函數(shù)長(zhǎng)什么樣。f(n)滿足非嚴(yán)格單調(diào)遞增這是一個(gè)非常好的性質(zhì)?，F(xiàn)在問(wèn)題變成了給定K找到所有“通過(guò)f(n)映射等于K”的n。我們完全可以拿mid當(dāng)自變量算f(mid)然后比較f(mid)和K的大小關(guān)系。如果f(mid) K說(shuō)明n取小了左邊界往右挪如果f(mid) K說(shuō)明有可能已經(jīng)進(jìn)入“等于K”的區(qū)域就往左收縮找更小的可行位置。整個(gè)過(guò)程不是直接枚舉n而是通過(guò)二分不斷逼近邊界。這就像在字典里找一個(gè)姓氏的頁(yè)碼范圍不用一頁(yè)頁(yè)翻先翻中間看首字母比目標(biāo)大了還是小了然后不斷縮小區(qū)間。2.2 第K小/第K大問(wèn)題的通用思考框架把793題掛上“二分答案”的標(biāo)簽是因?yàn)樗鸵活?lèi)更高頻的題目共用同一套思想第K小或第K大。這類(lèi)題目有個(gè)共同特征直接排序所有候選值往往做不到因?yàn)楹蜻x值的數(shù)量可能大到無(wú)法枚舉但判定“有多少個(gè)值小于等于mid”卻很容易。經(jīng)典套路如下確定候選值的范圍[lo, hi]這通常是整個(gè)數(shù)據(jù)的最小值和最大值。取mid lo (hi - lo) / 2寫(xiě)一個(gè)判定函數(shù) cnt(mid)統(tǒng)計(jì)滿足條件比如小于等于mid的候選值個(gè)數(shù)。如果 cnt(mid) K說(shuō)明第K小的候選值不會(huì)比mid更大收縮右邊界 hi mid。否則說(shuō)明第K小候選值至少比mid大收縮左邊界 lo mid 1。最終lo停下的位置就是第K小。這其實(shí)是“二分答案”的通用骨架。第K大可以換個(gè)方向或者數(shù)學(xué)上轉(zhuǎn)化成第總數(shù)-K1小本質(zhì)一模一樣。為什么大家愿意用二分答案因?yàn)榕卸ê瘮?shù)往往只要O(N)掃一遍甚至像793題只需要O(logN)而候選值域再大二分也就幾十次迭代。這種收益在數(shù)據(jù)量大的時(shí)候極其明顯。2.3 793問(wèn)的不是第K小為什么也歸到這里嚴(yán)格來(lái)說(shuō)793題問(wèn)的不是“第K小是什么”而是“有多少個(gè)數(shù)的函數(shù)值等于K”。但它依然落在“二分答案”這個(gè)分類(lèi)里原因是我們要在n的值域上找到滿足 f(n) K 的區(qū)間端點(diǎn)。換句話說(shuō)題目問(wèn)的是這個(gè)區(qū)間的長(zhǎng)度而區(qū)間端點(diǎn)必須靠二分找。你無(wú)法用普通二分“找到K然后往兩邊擴(kuò)展”的辦法因?yàn)閚可能到4e9量級(jí)線性擴(kuò)展會(huì)直接超時(shí)。正確做法是第一次二分找“第一個(gè)f(n) K”的位置這是左端點(diǎn)。第二次二分找“第一個(gè)f(n) K”的位置再減1這是右端點(diǎn)。兩個(gè)端點(diǎn)一減加1就是答案。這比單純的“求第K小”多了一點(diǎn)點(diǎn)變化但底層邏輯完全相通利用單調(diào)性把問(wèn)題歸結(jié)為找邊界。3. 二分邊界怎么定5K到底夠不夠3.1 上界選取與證明寫(xiě)二分前先解決一個(gè)大問(wèn)題n的范圍到底設(shè)到多少題目給出的K最大是1e9。f(n)的漸近形態(tài)可以這樣估算f(n) n/5 n/25 n/125 ... ≈ n/4這是因?yàn)槭醉?xiàng)1/5后面每項(xiàng)是前一項(xiàng)除以5等比求和極限正好是1/4。所以要讓f(n)達(dá)到Kn大約需要4K。為了保險(xiǎn)二分上界取h 5*K基本足夠。之所以說(shuō)“基本”最好是證明一下對(duì)任意正整數(shù)K令n 5K那么f(5K) K K/5 K/25 ...這個(gè)值一定不小于K。這就說(shuō)明在區(qū)間[0, 5K]內(nèi)一定能找到f(n)至少為K的位置左端點(diǎn)二分不會(huì)跑空。對(duì)K0時(shí)區(qū)間[0,0]也完全沒(méi)有問(wèn)題。這里的細(xì)節(jié)是類(lèi)型。K本身是int但5*K當(dāng)K1e9時(shí)達(dá)到5e9早就超出32位int的范圍。所以上界必須用long long存不然大概率會(huì)出現(xiàn)負(fù)數(shù)邊界二分直接崩掉。很多第一次寫(xiě)這題的人就是栽在這一步。3.2 兩次二分的寫(xiě)法第一次二分找左邊界l 0 r 5 * K while l r: mid (l r) / 2 if trailingZeroes(mid) K: r mid else: l mid 1這個(gè)模板的語(yǔ)義是不斷壓低右邊界找到第一個(gè)滿足“尾零數(shù)K”的n存到l。第二次二分找右邊界l 0 r 5 * K while l r: mid (l r) / 2 if trailingZeroes(mid) K: r mid else: l mid 1它找的是第一個(gè)“尾零數(shù)大于K”的n找到后減1就是最后一個(gè)“尾零數(shù)等于K”的位置。有人會(huì)問(wèn)為什么第一個(gè)找“”第二個(gè)找“”因?yàn)槲覀円膮^(qū)間左閉右開(kāi)。第二個(gè)位置本身不屬于答案屬于右邊第一個(gè)超出區(qū)間的點(diǎn)。兩次二分用的是同一個(gè)值域判定條件差一個(gè)等號(hào)這就是區(qū)間端點(diǎn)二分的標(biāo)準(zhǔn)姿勢(shì)。3.3 完整C實(shí)現(xiàn)下面給一份可以直接跑通的代碼注釋寫(xiě)在關(guān)鍵位置方便對(duì)照理解class Solution { public: int preimageSizeFZF(int K) { // 上界取5*KK最大1e9時(shí)不會(huì)超過(guò)long long范圍 long long left 0, right 5LL * K; // 第一次二分找第一個(gè) f(n) K 的位置 long long l left, r right; while (l r) { long long mid l (r - l) / 2; if (trailingZeroes(mid) K) { r mid; } else { l mid 1; } } long long lo l; // 如果這個(gè)位置算出來(lái)的尾零數(shù)不等于K說(shuō)明K被跳過(guò)了直接返回0 if (trailingZeroes(lo) ! K) { return 0; } // 第二次二分找第一個(gè) f(n) K 的位置 l left, r right; while (l r) { long long mid l (r - l) / 2; if (trailingZeroes(mid) K) { r mid; } else { l mid 1; } } long long hi l - 1; return hi - lo 1; } long long trailingZeroes(long long n) { long long count 0; while (n 0) { n / 5; count n; } return count; } };這里我做了一個(gè)小優(yōu)化如果第一次二分結(jié)束lo位置的f(lo)不等于K說(shuō)明K這個(gè)值根本不存在直接返回0沒(méi)必要再跑第二次二分。這個(gè)優(yōu)化雖然小但能讓無(wú)解分支的速度快一倍。4. 常見(jiàn)坑點(diǎn)與調(diào)試實(shí)錄4.1 溢出不是小問(wèn)題剛開(kāi)始寫(xiě)這題的某同學(xué)第一次提交用int存二分上界K傳1e9的時(shí)候5*K直接變成了負(fù)的二分區(qū)間完全錯(cuò)亂。當(dāng)時(shí)他把trailingZeroes函數(shù)也寫(xiě)成int型n/5累加在大數(shù)下溢出結(jié)果跑了幾個(gè)樣例全錯(cuò)。這是個(gè)特別容易忽略的點(diǎn)只要N的范圍允許到5e9那么所有跟n打交道的位置都要用long long。判定函數(shù)的參數(shù)、返回值和臨時(shí)變量全部要帶類(lèi)型。我見(jiàn)過(guò)不少人只把right改成long long但trailingZeroes里還在用int接收參數(shù)照樣錯(cuò)。4.2 死循環(huán)與mid取整二分模板里有人習(xí)慣寫(xiě)mid (l r 1) / 2有人習(xí)慣寫(xiě)mid (l r) / 2。這兩種對(duì)應(yīng)不同的邊界更新習(xí)慣。在這個(gè)題里兩個(gè)二分都是“左邊界向右側(cè)收縮”的模式用下取整不會(huì)死循環(huán)。因?yàn)楫?dāng)l r時(shí)mid (lr)/2恒小于r一定會(huì)有變化而l只會(huì)變成mid1或保持r的值也不會(huì)卡住。千萬(wàn)別把“找左邊界”和“找右邊界”的模板混用如果你在右邊界收縮時(shí)用了上取整在某種情況下可能陷入死循環(huán)。最穩(wěn)妥的做法是統(tǒng)一用下取整配合“如果滿足條件把當(dāng)前mid作為新的r”這種寫(xiě)法。4.3 無(wú)解判定的地方還有一種容易漏掉的場(chǎng)景K非常小比如K0。f(0)0f(1)0一直到f(4)0所以K0時(shí)應(yīng)該有5個(gè)n滿足條件。如果二分區(qū)間設(shè)成[0, 5K]那么[0,0]區(qū)間是可以的第一次二分會(huì)在l0停住f(0)0 K再找右邊界得到hi4返回5。只要代碼里沒(méi)有特殊把0擋掉這種情況是自然的。但如果你為了圖省事把右邊界設(shè)成5*K1或者更大的額外常數(shù)也能跑只是沒(méi)必要。判定“K無(wú)解”時(shí)陷阱在于直接判斷f(lo) ! K。如果lo已經(jīng)超出了二分上界或者區(qū)間根本沒(méi)覆蓋到就會(huì)出錯(cuò)。好在前面定了5K的上界并證明過(guò)一定有f(n)K所以不會(huì)出現(xiàn)lo越界的問(wèn)題。這里要注意當(dāng)K很大且f(5K)遠(yuǎn)大于K時(shí)左端點(diǎn)一定會(huì)在某個(gè)f(n)K或者被跳過(guò)的地方停下如果跳過(guò)了就會(huì)返回0這也是正確的。4.4 用手算樣例驗(yàn)證調(diào)試時(shí)建議備一張手動(dòng)驗(yàn)算表比盲目試錯(cuò)快得多。Kf(n)序列情況返回結(jié)果0n0到4f都為051n5到9f都為152n10到14f都為255f(24)4f(25)65被跳過(guò)01000000000二分快速定位區(qū)間長(zhǎng)度必然為5或0-特別注意K5這一行這是理解“跳檔”的最佳樣例。如果你代碼里的判定方向?qū)懛戳撕苡锌赡茉谶@個(gè)樣例上直接返回5而不是0那就說(shuō)明二分的“”和“”用混了。5. 從793擴(kuò)散二分答案的思路還能用在哪5.1 識(shí)別“二分答案可解”的氣質(zhì)做過(guò)幾道二分答案題之后我總結(jié)出一個(gè)經(jīng)驗(yàn)一個(gè)題能不能用二分答案主要看三點(diǎn)。第一候選答案存在一個(gè)有序的取值范圍。這個(gè)范圍可以是數(shù)組元素的值域也可以是n本身的值域。第二我們能寫(xiě)一個(gè)判定函數(shù)輸入一個(gè)mid快速返回“有多少個(gè)候選值滿足某條件”。這個(gè)判定函數(shù)往往是O(N)掃一遍有時(shí)候是O(logN)。第三目標(biāo)形式是“求滿足某條件的最小/最大值”或者像793題這樣“統(tǒng)計(jì)滿足等于某個(gè)值的區(qū)間長(zhǎng)度”。如果你在題目里看到“第K小”“最大值最小”“最小值最大”“個(gè)數(shù)不少于K”這些字眼而且直接做很難先往二分答案上想大概率路是通的。5.2 兩個(gè)值得動(dòng)手的變式順著793的思路有幾道同類(lèi)型題目很適合練習(xí)某個(gè)有序矩陣中求第K小的元素。候選值域就是矩陣最小值和最大值判定函數(shù)統(tǒng)計(jì)小于等于mid的元素個(gè)數(shù)整體復(fù)雜度O(N log(Max-Min))比直接用優(yōu)先隊(duì)列還干凈。乘法表中第K小的數(shù)。同樣先定值域然后對(duì)每個(gè)候選mid統(tǒng)計(jì)“乘法表里有多少個(gè)數(shù)小于等于它”這個(gè)統(tǒng)計(jì)可以按行計(jì)算很快。這兩道題我把它們歸類(lèi)為“二分答案 掃描統(tǒng)計(jì)”的組合跟793的關(guān)系是793的判定函數(shù)是數(shù)學(xué)公式那兩題的判定函數(shù)是掃描內(nèi)核完全一致。5.3 “答案只能是0或5”這個(gè)殺手級(jí)結(jié)論寫(xiě)到這里忍不住分享一個(gè)我剛發(fā)現(xiàn)時(shí)覺(jué)得很妙的小結(jié)論這道題的答案只會(huì)是0或5。為什么觀察序列每次尾零數(shù)量增加都發(fā)生在n恰好是5的倍數(shù)的時(shí)候。比如n從4到5f從0跳到1n從24到25f從4跳到6。那么在兩個(gè)連續(xù)的5的倍數(shù)之間比如從5到9一共5個(gè)連續(xù)nf值都不變。所以同一個(gè)尾零數(shù)量K如果有對(duì)應(yīng)的n必然是一整段5個(gè)連續(xù)整數(shù)。但n25這里f(24)4f(25)6跳過(guò)了5于是K5沒(méi)有對(duì)應(yīng)區(qū)間。這說(shuō)明一個(gè)K要么沒(méi)有區(qū)間要么區(qū)間寬度正好是5。所以一旦第一次二分確認(rèn)f(lo) K想都不用想直接可以return 5否則return 0。代碼還能再簡(jiǎn)化一半。如果你想把話講清楚證明也很簡(jiǎn)單任意區(qū)間[5t, 5t4]內(nèi)的5個(gè)整數(shù)其中只有5t這一個(gè)數(shù)能貢獻(xiàn)新的5因子剩下4個(gè)數(shù)沒(méi)有新增5因子因此這5個(gè)數(shù)的尾零數(shù)相同。而下一個(gè)能改變f值的點(diǎn)必然出現(xiàn)在5(t1)處。平臺(tái)的寬度就是5不會(huì)有例外。我個(gè)人做這類(lèi)題的習(xí)慣是先把單調(diào)性證明寫(xiě)出來(lái)再想判定函數(shù)的復(fù)雜度最后才動(dòng)筆寫(xiě)二分。很多人一上來(lái)就套模板結(jié)果邊界寫(xiě)錯(cuò)都不知道錯(cuò)在哪。一次在調(diào)試793的時(shí)候我把“找右邊界”的判定從“”改成“”結(jié)果每個(gè)無(wú)解K都返回5折騰了兩個(gè)小時(shí)才想起右邊的區(qū)間是開(kāi)區(qū)間差點(diǎn)把鍵盤(pán)拍碎。作為一道“二分答案”的入門(mén)題793的代碼量不大但包含的知識(shí)密度很高有數(shù)學(xué)推導(dǎo)、有二分邊界、有平臺(tái)區(qū)間、有溢出陷阱。把它吃透后面再去啃第K小和第K大的各類(lèi)變形會(huì)發(fā)現(xiàn)套路都長(zhǎng)得差不多——先找值域再寫(xiě)判定函數(shù)最后二分卡邊界。這個(gè)思路值得你在任何一道看起來(lái)無(wú)從下手的K-th問(wèn)題里第一時(shí)間拿出來(lái)試一遍。