0233：数字 1 的个数（★★）

2015-08-21 约 549 字预计阅读 2 分钟次阅读

力扣第 233 题

题目

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

0 <= n <= 10⁹

相似问题：

分析

#1

求范围内数字满足某种性质的个数，典型的数位 dp 问题，可以采用通用模板
令 dfs(i, st, bd) 代表某个状态下的结果：
- 遍历到 n 的第 i 位
- 前面取的数中有 st 个 1
- bd 代表前面取的数是否贴着 n 的上界
即可递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def countDigitOne(self, n: int) -> int:
        @cache
        def dfs(i,st,bd):
            if i==len(s):
                return st
            res = 0
            cur = int(s[i])
            up = cur if bd else 9
            for x in range(up+1):
                res += dfs(i+1,st+(x==1),bd and x==cur)
            return res
        s = str(n)
        return dfs(0,0,True)

48 ms

#2

还可以用贡献法，计算每一位上 1 的个数

以百位为例，百位上的数字以 1000 为周期循环，一个完整周期内有 100 个 1
再计算不完整周期，即 m=n%1000 内，分类讨论
- 假如 m<100，百位上没有 1
- 假如 m>=100，百位上 1 的个数是 min(100,m-100+1)
其它位数同理

解答

1
2
3
4
5
6
7
8


class Solution:
    def countDigitOne(self, n: int) -> int:
        res,x = 0,1
        while x<=n:
            q,r = divmod(n,x*10)
            res += q*x+max(0,min(x,r-x+1))
            x *= 10
        return res

33 ms

*附加

数位 dp 也可以写成递推形式
令 f[(st,bd)] 代表某个状态下的个数
- 前面取的数中有 st 个 1
- bd 代表前面取的数是否贴着 n 的上界
遍历时递推维护 f，最后再计算每个状态的个数乘以 st 即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def countDigitOne(self, n: int) -> int:
        f = defaultdict(int)
        f[(0,1)] = 1
        for c in map(int,str(n)):
            g = defaultdict(int)
            for (st,bd),w in f.items():
                up = c if bd else 9
                for x in range(up+1):
                    g[(st+(x==1),bd and x==c)] += w
            f = g
        return sum(st*w for (st,_),w in f.items())

33 ms

目录

0233：数字 1 的个数（★★）

题目

分析

#1

#2

解答

*附加