劍指offer：Python 整數中1出現的次數（從1到n整數中1出現的次數）圖解 絕對讓你看懂！

閱讀目錄

• • • 題目描述
    • 思路和Python實作
    • • 思路一
      • 思路二

題目描述

求出1 ~ 13的整數中1出現的次數，并算出100 ~ 1300的整數中1出現的次數？1~13中包含1的數字有1、10、11、12、13是以共出現6次，但是對于後面問題他就沒轍了。請把問題更加普遍化，可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數）。

思路和Python實作

看了下Python的解法，有投機心的，用字元串統計，或者用遞歸之類的，但是想想如果給的數是億計呢？于是整理了其他的思路

思路一

詳細圖解 逐位周遊

• 準備工作：假設 指針 代表目前位置，設為：midele_value，指針從最後的1位開始向左移動，每次以指針劃分，分為三個部分，指針左側為：高位區 high_value，指針右邊：低位區 low_value；指針不斷的移動，每次midele_value遇到的值，分為三類：0 ，1 ，2~9 ，下面分别讨論1可能出現的個數。

• 移動時，如果遇上0，如下圖，假如要讓它變成1，那麼 34591… 這樣就比原來的數大了，是以出現1的情況，隻能是前面各位為：3458 “1” 變化，從0~3458 總共有 3459個數（可以取0，即這個數是182190），結果發現就是前面存在的數（即是高位high_value），低位區總共的可能數是，有多少位數，每一位數都可以有0 ~ 9 的變化，加上所在位，就是 10 ^（後面的位數）。

  是以總共出現1的次數為：高位 * 10 ^（後面的位數）

  

• 移動時，如果遇到 2 ~ 9 的數，如下圖，指針指向的數不需要借位，可以直接34590 “8”變化，是以前面總共有：0~34590 總共34591個數，

  即是：（高位+1）* 10 ^（後面的位數）

  

• 移動時，如果遇到 1，如下圖，因為1就是我們要找的，是以可以這樣，将1變成0，這樣原來的數需要加上midele_value後面位數的數值，圖中将1變成0就是：34590820 000 + 190 ；這樣就變成了指針還是指向0的情況，那麼按照前面得出的34590820 000 就是：高位 * 10 ^（後面的位數）；緊接着，還有 指針+低位區 還沒處理，190 ，指針指向1時所有出現1的可能為 100~190 總共 91個數，即是低位區+1。

  是以得出：高位 * 10 ^（後面的位數）+ 低位區 + 1

  

• 具體實作需要解決的問題：

  設定一個preceise移動指針，讓它初始等于1，每次向左移動一位需要讓它增大10倍，即是：preceise = preceise * 10 ，不斷的循環移動，那麼

  指針 所分成的三塊區域 不斷變化過程如下圖：

  

  

  

• 如下圖：高位區 等于0 ，指針指向最左側的數，那麼循環就結束

  

• 以 preceise =1 的情況考慮，它将數分成三塊區域：high_value，midele_value 以及0，是以根據取一個數的每一個數的方法可以得出通式：

  high_value = n // (10 * preceise)

  midele_value = (n // preceise) % 10

  low_value = n % preceise

  preceise = preceise * 10

  （可以聯想一下判斷回文數和水仙花數，是如何取到每一位的方法來思考該如何實作這個）

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        preceise = 1
        high_value = 1
        # midele_value = 1
        # low_value = 1
        count = 0
        sum_num = 0
        while high_value != 0:
            high_value = n // (10 * preceise)
            midele_value = (n // preceise) % 10
            low_value = n % preceise
            preceise = preceise * 10

            if midele_value == 0:
                num = high_value * pow(10, count)
            elif midele_value > 1:
                num = (high_value + 1) * pow(10, count)
            else:
                num = high_value * pow(10, count) + low_value + 1
            sum_num += num
            count += 1
        return sum_num


obj = Solution()
print(obj.NumberOf1Between1AndN_Solution(131))
           

逐位周遊，其他思路

假設一個數 n = abcde ，其中abcde分别為十進制中各位上的數字。

如果要計算百位上1出現的次數，它要受到3方面的影響：百位上的數字，百位以下（低位）的數字，百位以上（高位）的數字。

• 如果百位上數字為0，百位上可能出現1的次數由更高位決定。比如：12013，則可以知道百位出現1的情況可能是：100-199，1100-1199,2100-2199，……，11100-11199，一共1200個。正好等于更高位數字（12）乘以 目前位數（100）。
• 如果百位上數字為1，百位上可能出現1的次數不僅受更高位影響還受低位影響。比如：12113，則可以知道百位受高位影響出現的情況是：100-199，1100-1199,2100-2199，…，11100-11199，一共1200個。等于更高位數字（12）乘以 目前位數（100）。但同時由于低位為13，百位出現1的情況還可能是：12100~12113,一共14個，等于低位數字（13）+1。
• 如果百位上數字大于1（2-9），則百位上出現1的情況僅由更高位決定，比如12213，則百位出現1的情況是：100-199,1100-1199，2100-2199，…，11100-11199,12100-12199,一共有1300個，等于更高位數字+1（12+1）乘以目前位數（100）。
• 從最低位開始，逐位周遊，統計出現1的次數

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        i = 1  # 記錄位數
        current = 0  # 記錄目前位上的數
        before = 0  # 記錄前邊的數
        after = 0  # 記錄後邊的數
        count = 0  # 記錄1出現的個數
        while (n // i) != 0:  # 位數到最高位為止
            current = ((n % (i * 10)) - (n % i)) / i
            before = n % i
            after = n // (i * 10)
            if current == 0:
                count += after * i
            elif current == 1:
                count += after * i + before + 1
            else:
                count += (after + 1) * i
            i = i * 10  # 每次循環，位數乘10
        return count


obj = Solution()
print(obj.NumberOf1Between1AndN_Solution(131))
           

思路二

數學歸納

整理來自：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6

• 個位：

  我們知道在個位數上，1會每隔10出現一次，例如1、11、21等等，我們發現以10為一個階梯的話，每一個完整的階梯裡面都有一個1，例如數字22，按照10為間隔來分三個階梯，在完整階梯0-9，10-19之中都有一個1，但是19之後有一個不完整的階梯，我們需要去判斷這個階梯中會不會出現1，易推斷知，如果最後這個露出來的部分小于1，則不可能出現1（這個歸納換做其它數字也成立）。

  我們可以歸納個位上1出現的個數為：n/10 * 1+(n%10!=0 ? 1 : 0)

• 十位

  現在說十位數，十位數上出現1的情況應該是10-19，依然沿用分析個位數時候的階梯理論，我們知道10-19這組數，每隔100出現一次，這次我們的階梯是100，例如數字317，分析有階梯0-99，100-199，200-299三段完整階梯，每一段階梯裡面都會出現10次1（從10-19），最後分析露出來的那段不完整的階梯。我們考慮如果露出來的數大于19，那麼直接算10個1就行了，因為10-19肯定會出現；如果小于10，那麼肯定不會出現十位數的1；如果在10-19之間的，我們計算結果應該是k - 10 + 1。例如我們分析300-317，17個數字，1出現的個數應該是17-10+1=8個。

  那麼現在可以歸納：十位上1出現的個數為：

  設k = n % 100，即為不完整階梯段的數字

  歸納式為：(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)

• 百位

  現在說百位1，我們知道在百位，100-199都會出現百位1，一共出現100次，階梯間隔為1000，100-199這組數，每隔1000就會出現一次。這次假設我們的數為2139。跟上述思想一緻，先算階梯數 * 完整階梯中1在百位出現的個數，即n/1000 * 100得到前兩個階梯中1的個數，那麼再算漏出來的部分139，沿用上述思想，不完整階梯數k199，得到100個百位1，100<=k<=199則得到k - 100 + 1個百位1。

  那麼繼續歸納百位上出現1的個數：

  設k = n % 1000

  歸納式為：(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)

  

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        i = 1  # 從個位開始計算，也可以從高為往低位計算
        count = 0  # 1的數量初始化為1
        while i <= n:  # 和n比較大小
            count += (n // (i*10))*i + (lambda x: min(max(x-i+1, 0), i))(n%(i*10))  
            # 個位，十位等1的個數整除去整，餘數上1的個數采用匿名函數，簡單一點，也可以使用if else
            i = i * 10  # 計算下一位的1的個數
        return count  # 傳回