【综合笔试题】难度 4/5，数位 DP 运用题

题目描述

这是 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」题。

对于「数位 DP」题，都存在「询问

（

和

均为正整数，且

）区间内符合条件的数值个数为多少」的一般形式，通常我们需要实现一个查询

有多少合法数值的函数 int dp(int x)，然后应用「容斥原理」求解出

的个数：

。

对于本题，虽然只需要求解

范围内数的个数，但其实拓展到求

区间个数的也不会增加难度。

具体的，对于「数位 DP」问题通常是「从高位到低位」的分情况讨论。

不失一般性的考虑数值

的某一位

是如何被处理的：

1. 如果当前位

的话，由于我们需要满足「小于等于

」的要求，因此如果该位填

的话，后面的低位填什么都是满足要求的，因此我们期望能够查表得出「长度为

，且二进制位置

数值为

时」有多少合法数值，将其累加到答案中；与此同时，我们需要确保当前位选

是合法的，即我们需要记录上一位

是什么，确保

和

不同时为

。

1. 如果当前位

的话，我们只能选

，并决策下一位。

当出现「当前位无法填入

」或者「决策到最低位」时，则完成了所有合法答案的统计。

至于流程

中的查表操作，我们可以使用 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 原题链接和其他优选题解。