《剑指 Offer （第 2 版）》第 43 题：整数中 1 出现的次数（从 1 到 n 整数中 1 出现的次数）

第 43 题：整数中 1 出现的次数（从 1 到 n 整数中 1 出现的次数）

传送门：AcWing：从 1 到 n 整数中 1 出现的次数。

输入一个整数 ，求从 到 这 个整数的十进制表示中 出现的次数。

例如输入 ，从 到 这些整数中包含 的数字有 ，， 和 ，“” 一共出现了 次。

样例：

输入： 12
输出： 5

同 LeetCode 第 233 题：数字 的个数。

大雪菜的解法：

C++ 代码：

《剑指 Offer （第 2 版）》第 43 题：整数中 1 出现的次数（从 1 到 n 整数中 1 出现的次数）-1

思路：

《剑指 Offer （第 2 版）》第 43 题：整数中 1 出现的次数（从 1 到 n 整数中 1 出现的次数）-2

Python 代码：

# 56. 从1到n整数中1出现的次数
#
# 输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
#
# 例如输入12，从1到12这些整数中包含“1”的数字有1，10，11和12，其中“1”一共出现了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)
            # 至少有左边的数这么多
            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：从 到 遍历，每个数通过对 求余数判断整数的个位数字是不是 ，大于 的除以 之后再判断。我们对每个数字都要做除法和求余运算以求出该数字中 出现的次数。如果输入数字 ， 有 位，我们需要判断每一位是不是 ，那么时间复杂度为 。这样做，计算量大，效率不高。

本文采用《数学之美》上面提出的方法，设定整数点（如 、、等等）作为位置点（对应 的个位、十位、百位等等），分别对每个数位上有多少包含 的点进行分析。

根据设定的整数位置，对 进行分割，分为两部分，高位 ，低位 ；

1、当 表示百位，且百位对应的数 ，

例如 ，此时考虑 ，则 ，。

此时百位为 的次数有 批次，具体如下：

说明：第 1 批次：，一共 个数；

第 2 批次：，一共 个数；

……

第 32 批次：，一共 个数；

最高两位 ，每一批次都包含 个连续的点，即共有 个点的百位为 ；

2、当 表示百位，且百位对应的数为 ，

例如 ，，则 ，，此时百位对应的就是 。

第 1 批次：，一共 个数；

第 2 批次：，一共 个数；

……

第 31 批次：，一共 个数；

第 32 批次：，一共 个数；

则共有 次是包含 个连续点，最高两位 。

当最高两位为 （即 ），本次只对应局部点 ，共 次，所有点加起来共有 ，这些点百位对应为 ;

3、当 表示百位，且百位对应的数为 ，如 ，，则 ，。

第 1 批次：，一共 个数；

第 2 批次：，一共 个数；

……

第 31 批次：，一共 个数；

第 32 批次：，一共 个数；

此时百位为 的次数有 ，最高两位 ；

综合以上 种情况，当百位对应 或 时，有 次包含所有 个点，还有当百位为 （），需要增加局部点 。

之所以补 ，是因为当百位为 ，则 ，当百位 ，补 会产生进位，效果等同于 。

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