3007：价值和小于等于 K 的最大数字（2258 分）

2024-01-14 约 704 字预计阅读 2 分钟次阅读

力扣第 380 场周赛第 3 题

题目

给你一个整数 k 和一个整数 x 。整数 num 的价值是它的二进制表示中在 x，2x，3x 等位置处 设置位 的数目（从最低有效位开始）。下面的表格包含了如何计算价值的例子。

x	num	Binary Representation	Price
1	13	000001101	3
2	13	000001101	1
2	233	011101001	3
3	13	000001101	1
3	362	101101010	2

num 的 累加价值 是从 1 到 num 的数字的总价值。如果 num 的累加价值小于或等于 k 则被认为是廉价的。

请你返回最大的廉价数字。

示例 1：

输入：k = 9, x = 1
输出：6
解释：由下表所示，6 是最大的廉价数字。

x	num	Binary Representation	Price	Accumulated Price
1	1	001	1	1
1	2	010	1	2
1	3	011	2	4
1	4	100	1	5
1	5	101	2	7
1	6	110	2	9
1	7	111	3	12

示例 2：

输入：k = 7, x = 2
输出：9
解释：由下表所示，9 是最大的廉价数字。

x	num	Binary Representation	Price	Accumulated Price
2	1	0001	0	0
2	2	0010	1	1
2	3	0011	1	2
2	4	0100	0	2
2	5	0101	0	2
2	6	0110	1	3
2	7	0111	1	4
2	8	1000	1	5
2	9	1001	1	6
2	10	1010	2	8

提示：

1 <= k <= 10¹⁵
1 <= x <= 8

分析

#1 贡献法

考虑二分，要计算 1 到 n 的总价值
可以用贡献法，类似 0233，计算每一位的贡献
- 以从低到高第 i 位为例
- i 位上的 1 以 2^(i+1) 为周期循环，一个完整周期内有 2^i 个 1
- 再计算不完整周期 r 内，有 max(0,r-2^i+1) 个 1

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


class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        def check(n):
            y = 1<<(x-1)
            res = 0
            while y<=n:
                q,r = divmod(n,2*y)
                res += q*y+max(0,r-y+1)
                y <<= x
            return res>k
        ma = (1<<x)*(k+1)
        return bisect_left(range(ma),True,key=check)-1

111 ms

#2 试填法

这种针对二进制表示的问题，也可以考虑试填法
- 从高位到低位，先填 1，并计算增加的价值
- 若价值超了，则该位应该填 0
- 否则，该位填 1，并累计价值
对于本题，假如填到第 i 位（即 2^i 的位置），前面已填有价值的1个数为 pre
- 增加的价值来源于前面和后面两部分
- 前面已填有价值的 1 的个数是 pre，每个增加 2^i
- 后面有价值的 1 的位置有 i//x 个，每个增加 2^(i-1)

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        ma = (k+1)<<x
        res,pre = 0,0
        for i in range(ma.bit_length()-1,-1,-1):
            add = (pre<<i)+(i//x<<i>>1)
            if add<=k:
                k -= add
                pre += (i+1)%x==0
                res |= 1<<i
        return res-1

37 ms

目录

3007：价值和小于等于 K 的最大数字（2258 分）

题目

分析

#1 贡献法

#2 试填法

解答