Question source

题目描述

求出 1 ~ 13 的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下 1 ~ 13 中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解题思路：数位运算

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

将数位分为3部分：高位(high)，当前位(cur)与低位(low)。我们可以从个位出发，不断遍历各个数位，设为当前位。对于1出现的次数的计算，当前位取值不同，情况不同。有三种情况，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
case 1: cur=0
    if n = 2  3   0  4
    千位和百位可以选00 01 02....22，十位可以取到1，个位可以选0-9( 形如[00|01..|22]1[0-9] 都是<2304 )。
    共有 23 * 10 中排列；
    当千位和百位取23，如果十位取1，那就是形如 231[0-9] > 2304,不满足题意；
    所以当千位和百位取23，十位只能能取0。
    此情况 不 将cur右边数值带入1次数的计算：个位取0-4即 2300 2301 2302 2303 2304可行，但是2301不应该算进来，
    这个 1 是单独出现在个位的。
    由于之前cur在个位出现过，所以此时纳入计算，就会导致重复计算（例如11，121,111这种可以被算多次【2，2，3】）。
    即 count(1|cur=0,cur在十位，n=2304) = 23 * 10。
case 2: cur=1
    if n = 2  3  1  4
    千位和百位可以选00 01 02....22，十位可以取到1，个位可以选0-9，共有 23 * 10 中排列；
    当千位和百位取23,十位取1，个位可以取0-4，即 2310-2314，共5个。
    即 count(1|cur=1,cur在十位，n=2304) = 23 *10 + 4 +1
case 3: cur>1 即2 - 9
    if n = 2  3  2  4
    千位和百位可以选00 01 02....22，十位可以取到1，个位可以选0-9 (形如 [00|01...|22]1[0-9] 都是<2324)。
    共有 23 * 10 中排列；
    当千位和百位取23，十位取1，个位可以取 0-9，即 2310-2319共10个
    （其中2311，被计算了两次，分别是cur在个位和十位各分析得到的1次，所以另一次已经在cur在个位时，计算了）。
    即 count(1|cur>1,cur在十位，n=2304) = 23 *10 + 10

总结规律如下： 1. 当 cur=0 时： 此位 1 的出现次数只由高位（high） 决定，计算公式为 high × digit。

  1. 当 cur=1 时： 此位 1 的出现次数由高位 hig 和低位 low 决定，计算公式为 high×digit+low+1。

  2. 当 cur=2,3,⋯,9 时： 此位 1 的出现次数只由高位 high 决定，计算公式为： (high+1)×digit。

⚠️ 1. 滚轮的密码锁，固定其中的一位密码，拨动其他位置的密码 - 从这个角度，有助于我们理解这个解题思路。固定当前位为cur值，看满足题意，会出现的 1 的次数。

Complexity

  • 时间复杂度 O(logn) ： 循环内的计算操作使用 O(1) 时间；循环次数为数字 n 的位数，即 log_10 ^ n ，因此循环使用 O(logn) 时间。

  • 空间复杂度 O(1) ： 几个变量使用常数大小的额外空间。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        res = 0
        digit, high, cur, low = 1, n//10, n%10, 0
        while high!=0 or cur!=0:
            if cur == 0: res += high * digit
            elif cur == 1: res += high*digit + low + 1
            elif cur >= 2: res += (high+1) * digit

            #cur决定了low的值，high决定了cur的值，所以变量执行顺序是low -> cur -> high

            low += digit * cur # 当 high 和 cur 同时为 0 时，说明已经越过最高位，因此跳出
            cur = high%10 # 将 cur 加入 low ，组成下轮 low
            high //= 10 # 将本轮 high 最低位删除，得到下轮 high
            digit *= 10 # 位因子每轮 × 10
        return res

参考

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/