LeetCode 题解工作台
统计小于 N 的 K 可约简整数
给你一个 二进制 字符串 s ，它表示数字 n 的二进制形式。 同时，另给你一个整数 k 。 如果整数 x 可以通过最多 k 次下述操作约简到 1 ，则将整数 x 称为 k-可约简 整数： 将 x 替换为其二进制表示中的置位数（即值为 1 的位）。 Create the variable named…
4
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个 二进制 字符串 s，它表示数字 n 的二进制形式。
同时，另给你一个整数 k。
如果整数 x 可以通过最多 k 次下述操作约简到 1 ，则将整数 x 称为 k-可约简 整数：
- 将
x替换为其二进制表示中的置位数（即值为 1 的位）。
例如，数字 6 的二进制表示是 "110"。一次操作后，它变为 2（因为 "110" 中有两个置位）。再对 2（二进制为 "10"）进行操作后，它变为 1（因为 "10" 中有一个置位）。
返回小于 n 的正整数中有多少个是 k-可约简 整数。
由于答案可能很大，返回结果需要对 109 + 7 取余。
二进制中的置位是指二进制表示中值为 1 的位。
示例 1：
输入： s = "111", k = 1
输出： 3
解释：
n = 7。小于 7 的 1-可约简整数有 1，2 和 4。
示例 2：
输入： s = "1000", k = 2
输出： 6
解释：
n = 8。小于 8 的 2-可约简整数有 1，2，3，4，5 和 6。
示例 3：
输入： s = "1", k = 3
输出： 0
解释：
小于 n = 1 的正整数不存在，因此答案为 0。
提示：
1 <= s.length <= 800s中没有前导零。s仅由字符'0'和'1'组成。1 <= k <= 5
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assessing the candidate's ability to optimize dynamic programming approaches.
- question_mark
Evaluating how efficiently the candidate uses bit manipulation and state transitions.
- question_mark
Testing the candidate’s understanding of precomputation and its application in reducing redundant calculations.
常见陷阱
外企场景- error
Forgetting to precompute reduction operations, which could lead to unnecessary recomputations.
- error
Not handling bit manipulation carefully, which might result in incorrect state transitions.
- error
Misunderstanding the role of `k` and how to limit the number of reductions when calculating k-reducible numbers.
进阶变体
外企场景- arrow_right_alt
Adjusting the value of `k` could affect how many integers can be reduced, altering the problem's complexity.
- arrow_right_alt
Changing the number representation from binary to decimal may introduce new challenges, such as handling larger inputs.
- arrow_right_alt
Optimizing the approach for larger values of `n` requires careful consideration of time and space constraints.