第 43 題：整數(shù)中 1 出現(xiàn)的次數(shù)（從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)）

傳送門：AcWing：從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)薇缅。

輸入一個整數(shù) 眯亦，求從 到 這 個整數(shù)的十進(jìn)制表示中 出現(xiàn)的次數(shù)。

例如輸入 就缆，從 到 這些整數(shù)中包含 的數(shù)字有 ，， 和 晒来，“” 一共出現(xiàn)了 次。

樣例：

輸入： 12
輸出： 5

同 LeetCode 第 233 題：數(shù)字 的個數(shù)郑现。

大雪菜的解法：

C++ 代碼：

《劍指 Offer （第 2 版）》第 43 題：整數(shù)中 1 出現(xiàn)的次數(shù)（從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)）-1

思路：

《劍指 Offer （第 2 版）》第 43 題：整數(shù)中 1 出現(xiàn)的次數(shù)（從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)）-2

Python 代碼：

# 56. 從1到n整數(shù)中1出現(xiàn)的次數(shù)
#
# 輸入一個整數(shù)n，求從1到n這n個整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)。
#
# 例如輸入12冠骄，從1到12這些整數(shù)中包含“1”的數(shù)字有1片排，10，11和12辛友，其中“1”一共出現(xiàn)了5次薄扁。
#
# 樣例
# 輸入： 12
# 輸出： 5
class Solution(object):
    def numberOf1Between1AndN_Solution(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0

        number = []
        while n:
            number.append(n % 10)
            n //= 10

        res = 0
        for i in range(len(number) - 1, -1, -1):
            left = 0
            right = 0
            # 想清楚這里 t 為什么從 1 開始
            t = 1
            for j in range(len(number) - 1, i, -1):
                left = left * 10 + number[j]

            for j in range(i - 1, -1, -1):
                right = right * 10 + number[j]
                t *= 10
            # print(left, right)
            # 至少有左邊的數(shù)這么多
            res += left * t
            # print(number[i], left, right, t, left * t)
            if number[i] == 1:
                res += right + 1
            elif number[i] > 1:
                res += t
        return res


if __name__ == '__main__':
    solution = Solution()
    n = 45032
    result = solution.numberOf1Between1AndN_Solution(n)
    print('result', result)

解法1：從 到 遍歷，每個數(shù)通過對 求余數(shù)判斷整數(shù)的個位數(shù)字是不是 废累，大于 的除以 之后再判斷邓梅。我們對每個數(shù)字都要做除法和求余運(yùn)算以求出該數(shù)字中 出現(xiàn)的次數(shù)。如果輸入數(shù)字 邑滨， 有 位日缨，我們需要判斷每一位是不是 ，那么時間復(fù)雜度為 驼修。這樣做殿遂，計(jì)算量大，效率不高乙各。

本文采用《數(shù)學(xué)之美》上面提出的方法墨礁，設(shè)定整數(shù)點(diǎn)（如 、耳峦、等等）作為位置點(diǎn)（對應(yīng) 的個位恩静、十位、百位等等）蹲坷，分別對每個數(shù)位上有多少包含 的點(diǎn)進(jìn)行分析驶乾。

根據(jù)設(shè)定的整數(shù)位置，對 進(jìn)行分割循签，分為兩部分级乐，高位 ，低位 县匠；

1风科、當(dāng) 表示百位撒轮，且百位對應(yīng)的數(shù) ，

例如 贼穆，此時考慮 题山，則 ，故痊。

此時百位為 的次數(shù)有 批次顶瞳，具體如下：

說明：第 1 批次：，一共 個數(shù)愕秫；

第 2 批次：慨菱，一共 個數(shù)；

……

第 32 批次：豫领，一共 個數(shù)抡柿；

最高兩位 ，每一批次都包含 個連續(xù)的點(diǎn)等恐，即共有 個點(diǎn)的百位為 洲劣；

2、當(dāng) 表示百位课蔬，且百位對應(yīng)的數(shù)為 囱稽，

例如 ，二跋，則 战惊，，此時百位對應(yīng)的就是 扎即。

第 1 批次：吞获，一共 個數(shù)；

第 2 批次：谚鄙，一共 個數(shù)各拷；

……

第 31 批次：，一共 個數(shù)闷营；

第 32 批次：烤黍，一共 個數(shù)；

則共有 次是包含 個連續(xù)點(diǎn)傻盟，最高兩位 速蕊。

當(dāng)最高兩位為 （即 ），本次只對應(yīng)局部點(diǎn) 娘赴，共 次规哲，所有點(diǎn)加起來共有 ，這些點(diǎn)百位對應(yīng)為 ;

3诽表、當(dāng) 表示百位媳叨，且百位對應(yīng)的數(shù)為 腥光，如 ，糊秆，則 ，议双。

第 1 批次：痘番，一共 個數(shù)；

第 2 批次：平痰，一共 個數(shù)汞舱；

……

第 31 批次：，一共 個數(shù)宗雇；

第 32 批次：昂芜，一共 個數(shù)；

此時百位為 的次數(shù)有 赔蒲，最高兩位 泌神；

綜合以上 種情況，當(dāng)百位對應(yīng) 或 時舞虱，有 次包含所有 個點(diǎn)欢际，還有當(dāng)百位為 （），需要增加局部點(diǎn) 矾兜。

之所以補(bǔ) 损趋，是因?yàn)楫?dāng)百位為 ，則 椅寺，當(dāng)百位 浑槽，補(bǔ) 會產(chǎn)生進(jìn)位，效果等同于 返帕。

Python 代碼：

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        i = 1
        while i <= n:
            a = n / i
            b = n % i
            count += (a+8) / 10 * i + (a % 10 == 1)*(b + 1)
            i *= 10
        return count

參考資料：https://blog.csdn.net/qq_38211852/article/details/80863364

https://cuijiahua.com/blog/2017/12/basis_31.html