筆試算法模拟題精解之“神奇數字在哪裡”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“50.神奇數字在哪裡”的解法探究。先來看一下題目内容：

題目詳情

等級：中等

知識點：搜尋、遞歸

檢視題目：神奇數字在哪裡

請計算出1-n(1<=n<=1000000000)中有多少個數字中，隻存在'1','2','3'這三個數字，且這三個數字至少都要出現1次。

輸入一個數n。

輸出1-n中符合要求的數字的個數。

示例1

輸入：

232

輸出：

4

解題方法：

注意讀題，本題要求的數字中“隻”含有1，2，3三個數字

方法 1：暴力搜尋

對本題，最簡單的想法是針對每個數字，轉為字元串，然後判斷數字中是否隻同時包含1，2，3三個字元。鑒于本題輸入是int，n最大可以達到2^31-1≈2*10^9，一個這麼長的for循環，時間複雜度還是比較高的，不是最優解法。

時間複雜度：O(n)

方法 2：深度優先搜尋

尋找這種神奇數字，暴力法可以說是從數字中“嘗試”某個數字，是否符合我們的标準，這個過程好比線性搜尋。但換個思路想，我們也可以嘗試用“建構”的方式，建構出所有符合“神奇數字”标準的數字，并挨個計數，完成這個過程。

這個建構數字和搜尋的過程，可以寫一個遞歸做深度搜尋實作：從0開始，給一個較短的數字，不斷讓把的其它位數字移動1位，并把多出來的個位數設為1，2，3，并在搜尋的範圍超過n時，及時停下搜尋。

時間複雜度：O(logn)（或者O(k)，k表示數字的位數）

方法 3：預熱+查找

用過方法二後，我們發現，在限定了n是int類型的情況下，其實這種隻含有1，2，3的數字的數量并不多。甚至可以在靜态初始化方法裡，提前計算好所有這樣的數字，并按大小排列好。然後對輸入的每個n，直接在準備好的數組中二分查找，找到比它小的數字的數量，就可以傳回結果了。

看完之後是不是有了答題思路了呢，快來練練手吧：

50.神奇數字在哪裡

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計内測中，搶先周賽赢好禮！面試考試前，快來刷刷題！