目录

0233:数字 1 的个数(★★)

力扣第 233 题

题目

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

示例 1:

输入:n = 13
输出:6

示例 2:

输入:n = 0
输出:0

提示:

  • 0 <= n <= 109

相似问题:

分析

#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)

0 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

0 ms