剑指 Offer 43. 1～n整数中1出现的次数

• 题目描述

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

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

 

示例 1：

输入：n = 12
输出：5
示例 2：

输入：n = 13
输出：6
 

限制：

1 <= n < 2^31

• 解答

这道题的考点就是：找规律！

思路呢首先需要回忆下我们平时旅行箱上用的密码锁，或者1分钟跳绳用的绳子的计数器。

将 1 ~ n 的个位、十位、百位、...的 1出现次数相加，即为 1出现的总次数。

那么我们其实可以想象假如固定某一数位为1，求其他数位的全排列。

再看看，假如要求n=2304，求十位为1的出现次数：

我们可以将这个数分成：

高位：high

当前位：cur

低位：low

位因子：10 ^k (k=0,...m)

此时对于2304,1在十位出现的范围为：0010~2219

固定十位的1，那么其他位的排列则为0~229，有230个数（可以凑为公式high * digit）

但此时cur是为0的，那么假如说这个数是2314，假设同样求1在十位的次数，那情况是怎样的呢？

此时high=23，low=4，cur=1，

那么1出现的范围则是0010~2314

此时1在十位出现的次数为000~234，有235个数（同样凑个公式为high*digit + low + 1）

那么假如这个数时2324，此时cur>1，会是怎么样？

此时high = 23，low= 4， cur=2

那么1出现的范围是0010~2319

此时1在十位出现的次数为000~239，有240个数（再凑个公式为(high+1) * digit）

 那么这样看的话，思路是不是就很清晰了。但是还是要注意高位的移动，当前位的移动和低位的移动。循环的结束条件是：当高位为0和当前位均为0，说明当前位已经越过最大数的左边界了。

class Solution:
    def countDigitOne(self, n: int) -> int:
        digit = 1 #初始位因子
        cur = n % 10 #初始当前位
        high = n // 10 #初始高位
        low = 0 #初始低位
        res = 0
        while high != 0 or cur != 0:
            if cur == 1:
                res += high * digit + low + 1
            elif cur == 0:
                res += high * digit
            else:
                res += (high + 1) * digit
            low = low + cur * digit #低位向左移动
            cur = high % 10 #当前位向左移动
            high = high // 10 #高位向左移动
            digit *= 10 
        return res