力扣第 233 题
题目
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
相似问题：
分析
#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
15
|
def get(s):
@cache
def dfs(i,st,bd):
if i==len(s):
return st
res = 0
up = int(s[i]) if bd else 9
for x in range(up+1):
res += dfs(i+1,st+(x==1),bd and x==up)
return res
return dfs(0,0,1)
class Solution:
def countDigitOne(self, n: int) -> int:
return get(str(n))
|
3 ms
#2
本题的数位 dp 还有种更优的写法
- 只记忆化非上界的状态，并令 i 代表还剩 i 位
- 这样的状态的结果跟 n 无关，可以通用
- 其实就是分段计数中，把每一段的结果记忆化了
注意一定要先判断状态的结果跟 n 无关，memo 才可以通用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
memo = {}
def get(s):
def dfs(i,st,bd):
if not bd and (i,st) in memo:
return memo[(i,st)]
if i<0:
return st
res = 0
up = int(s[i]) if bd else 9
for x in range(up+1):
res += dfs(i-1,st+(x==1),bd and x==up)
if not bd:
memo[(i,st)] = res
return res
s = s[::-1]
return dfs(len(s)-1,0,1)
class Solution:
def countDigitOne(self, n: int) -> int:
return get(str(n))
|
0 ms
#3
还可以用贡献法，计算每一位上 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