这是 LeetCode 上的「600. 不含连续1的非负整数」,难度为「困难」。
Tag : 「数位 DP」
给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。
示例 1:
输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中,只有整数3违反规则(有两个连续的1),其他5个满足规则。
说明: 1 <= n <= 109
这是一道典型的「数位 DP」题。
对于「数位 DP」题,都存在「询问
(
和
均为正整数,且
)区间内符合条件的数值个数为多少」的一般形式,通常我们需要实现一个查询
有多少合法数值的函数 int dp(int x)
,然后应用「容斥原理」求解出
的个数:
。
对于本题,虽然只需要求解
范围内数的个数,但其实拓展到求
区间个数的也不会增加难度。
具体的,对于「数位 DP」问题通常是「从高位到低位」的分情况讨论。
不失一般性的考虑数值
的某一位
是如何被处理的:
的话,由于我们需要满足「小于等于
」的要求,因此如果该位填
的话,后面的低位填什么都是满足要求的,因此我们期望能够查表得出「长度为
,且二进制位置
数值为
时」有多少合法数值,将其累加到答案中;与此同时,我们需要确保当前位选
是合法的,即我们需要记录上一位
是什么,确保
和
不同时为
。
的话,我们只能选
,并决策下一位。
当出现「当前位无法填入
」或者「决策到最低位」时,则完成了所有合法答案的统计。
至于流程
中的查表操作,我们可以使用 static
预处理出 f
数组,定义
为考虑二进制长度为
,且最高位为
(
or
)时的合法数个数(值不超过)。
PS. 值不超过的含义代表了不仅仅统计高位为
的情况。例如
代表长度为
,最高为
,其包含了 1xxx 和 0xxx 的合法数的个数。
❝注意:为了防止重复计数问题,我们在不失一般性的计算
和
时,既能采用诸如
的 “后向查找依赖” 的方式进行转移,也能采用
“前向主动更新” 的方式进行转移。 ❞
不失一般性的考虑
和
能够更新哪些状态:
的话,需要统计所有满足
形式的合法数值,当前位的低一位只能填
(填
会出现重复计数,即需要忽略前导零的数值),此时有:
;
的话,需要统计所有满足
和
形式的合法数值:
时,当前位的低一位只能填
;此时有:
;
时,当前位的低一位只能填
;此时有:
。
代码:
class Solution {
static int N = 50;
// f[i][j] 为考虑二进制长度为 i,而且最高位为 j(0 or 1)时的合法数个数(值不超过)
// 如 f[2][1] 代表二进制长度为 2,且(值不超过)最高位为 1 的合法数的个数:10、01、00
static int[][] f = new int[N][2];
static {
f[1][0] = 1; f[1][1] = 2;
for (int i = 1; i < N - 1; i++) {
f[i + 1][0] = f[i][1];
f[i + 1][1] = f[i][0] + f[i][1];
}
}
int getLen(int n) {
for (int i = 31; i >= 0; i--) {
if (((n >> i) & 1) == 1) return i;
}
return 0;
}
public int findIntegers(int n) {
int len = getLen(n);
int ans = 0, prev = 0;
for (int i = len; i >= 0; i--) {
// 当前位是 0 还是 1
int cur = ((n >> i) & 1);
// 如果当前位是 1,那么填 0 的话,后面随便填都符合,将方案数累加
if (cur == 1) ans += f[i + 1][0];
// 出现连续位为 1,分支结束,方案数被计算完
if (prev == 1 && cur == 1) break;
prev = cur;
if (i == 0) ans++;
}
return ans;
}
}
f
数组的操作使用了 static
修饰(在跑样例数据前已经预处理完,且预处理结果被所有样例数据所共享),因此访问 f
数组是 的查表操作;统计答案的复杂度与二进制长度相关,复杂度为
。整体复杂度为
为预处理数值的大小,固定为
,复杂度为
这是我们「刷穿 LeetCode」系列文章的第 No.600
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。