leetcode-600-不含连续1的非负整数

[博客链接]

菜?的学习之路

掘金首页

[题目链接]

题目链接

[github地址]

github地址

[题目描述]

给定一个正整数 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
表示(a,b) 区间内，某种方案的数量
本题将区间限制到(0,n)
- res(a,b) = dp[b] – dp[a-1]
- res(0,n) = dp[n]
二维dp[i][j]数组表示不超过长度为i，最高位置为j的的所有方案数量
为了做到不会重复运算（重复运算包括类似包含前导0导致的重复方案计算），我们可以使用主动前推来进行dp方程推导
ps：前导0导致的重复方案计算为类似 $(00001)_2$ 与 $(0001)_2$ 方案相同
有如下几种情况需要考虑
- j == 0时 dp[i + 1][0] = dp[i][1]
- j == 1时包含如下两种情况
  - 最高位为1 $(1xxx)_2$ 的时候的方案数量dp[i+1][1] += dp[i][0]
  - 最高位为0 $(0xxx)_2$ 的时候的方案数量dp[i+1][1] += dp[i][1]
同时我们需要观察到当处理当前位数字的时候，如果当前位为1，则需要判断前一位是否为1，所以我们需要记录前1位的值
为了免除前导0的因素的原因一样，我们需要找到n的第一个1的位数，然后开始计算方案，因为前面的0对结果没有影响（当然这个函数不使用也可以，反正也只是减掉了常数级的运算，一般不会卡这个效率）

int getL(int n) {
    for (int i = 31; i >= 0; i--) {
        if ((n >> i & 1) == 1) {
            return i;
        }
    }
    return 0;
}

public int findIntegers(int n) {
    int[][] dp = new int[40][2];
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 1; i < n - 1; i++) {
        dp[i + 1][0] = dp[i][1];
        dp[i + 1][1] = dp[i][1] + dp[i][0];
    }
    int len = getL(n);
    int res = 0, prev = 0;
    for (int i = len; i >= 0; i--) {
        int cur = (n >> i) & 1;
        if (cur == 1){
            res +=dp[i+1][0];
        }
        if (prev == 1 && cur == 1){
            break;
        }
        prev = cur;
        if (i == 0){
            res++;
        }
    }
    return res;


}
复制代码

时间复杂度O(lgn)
空间复杂度O(lgn)

思路二：二叉树模拟的dp思路

我们将n转换为2进制可以发现其表示的数字范围可以通过一个完全二叉树表示出来

每一条从根节点到叶节点的路径能够表示从0到n的每个数字
- 任意高度相同，数值相同的节点，其包含的方案数量相同
由上述条件可以观测当高度为i的时候
dp[i] = dp[i-1] + dp[i-2]
表示的是当高度i的时候，dp[i]可以表示为其左子树的所有方案数量+右子树的左子树的方案数量

public int findIntegers(int n) {
    int[] dp = new int[31];
    dp[0] = dp[1] = 1;
    for (int i = 2; i < dp.length; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    int pre = 0, res = 0;
    for (int i = 29; i >= 0; i--) {
        int val = 1 << i;
        if ((val & n) != 0) {
            n -= val;
            res += dp[i + 1];
            if (pre == 1) {
                break;
            }
            pre = 1;
        } else {
            pre = 0;
        }
        if (i == 0) {
            res += 1;
        }
    }
    return res;
}
复制代码