数位DP+二分答案 | lc380 补题Q3

发表于 阅读次数：

Q3 3007. 价值和小于等于 K 的最大数字

题意

分别给你一个整数 k 和 x ，让你求从1开始的 最大 整数，其二进制数 s，位数 i 满足 i%x == 0 且 s[i] 值为1的 数量 小于等于k。

二进制位数 i 是从右到左从1开始计数的。

题解

数位DP+二分答案。

数位DP的思路和233. 数字 1 的个数一样，再确定一个答案边界，对于每次二分的数使用数位DP去判断是否满足即可。

答案粗略边界 (k+1) << x，如下图所示，左边0到k的过程中第x位都会有1出现

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        def countDigit(num: int) -> int:
            s = bin(num)[2:]
            n = len(s)
            @cache
            def f(i:int, cnt:int, is_limit:bool) -> int:
                if i == len(s):
                    return cnt
                res = 0
                up = int(s[i]) if is_limit else 1
                for d in range(up+1):
                        res += f(i+1, cnt+ (d==1 and ((n-i)%x == 0)) , is_limit and d == up)
                return res
            
            return f(0, 0, True)
        
        num_lim = (k+1) << x
        l = 0
        r = num_lim
        while l <= r:
            m = (l+r) >> 1
            cnt = countDigit(m)
            if cnt > k:
                r = m-1
            elif cnt <= k:
                l = m+1
        return r