力扣第 128 场周赛第 4 题
题目
给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。
示例 1：
输入：n = 20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：
输入：n = 100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：
输入：n = 1000
输出：262
提示：
相似问题：
分析
#1
- 可以反过来求数字不重复的个数，即是典型的数位 dp
- 注意前置 0 不加入状态 st 中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
@cache
def dfs(i,st,bd):
if i==len(s):
return 1
res = 0
up = int(s[i]) if bd else 9
for x in range(up+1):
if not st>>x&1:
res += dfs(i+1,0 if st==x==0 else st|1<<x,bd and x==up)
return res
s = str(n)
return n+1-dfs(0,0,1)
|
207 ms
#2
本题还可以用 memo 通用的写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
memo = {}
class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
def dfs(i,st,bd):
if i<0:
return 1
if not bd and (i,st) in memo:
return memo[(i,st)]
res = 0
up = int(s[i]) if bd else 9
for x in range(up+1):
if not st>>x&1:
res += dfs(i-1,0 if st==x==0 else st|1<<x,bd and x==up)
if not bd:
memo[(i,st)] = res
return res
s = str(n)[::-1]
return n+1-dfs(len(s)-1,0,1)
|
7 ms
#3
- 还可以直接分段计算，例如对于 n=8382：
- [0, 1000) 的数字不重复的个数：9*(A(9,0)+A(9,1)+A(9,2))
- [1000, 8000) 的对应个数：7*A(9,3)
- [8000, 8300) 的对应个数：3*A(8,2)
- [8300, 8380) 的对应个数：7*A(7,1)
- [8380, 8382) 的对应个数：0
- 具体实现时，假设 s=str(n) 的长度为 m
- 先计算 0-10^(m-1) 的个数
- 然后遍历 i，固定 s[:i]，求 s[i] 能取的值，再求 s[i+1:] 的排列个数
- 特别注意：
- i=0 时，s[i] 不能取 0
- i=m-1 时，s[i] 可以取到原值，为了方便，可以先将 n 加 1，就不需特别处理
- s[:i] 已经有重复数字时，直接终止
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def numDupDigitsAtMostN(self, n: int) -> int:
s = str(n+1)
m = len(s)
res = 9*sum(perm(9,k) for k in range(m-1))
vis = set()
for i in range(m):
cur = int(s[i])
cand = set(range(int(i==0),cur))-vis
res += len(cand)*perm(9-i, m-i-1)
if cur in vis:
break
vis.add(cur)
return n-res
|
0 ms