600 不含连续1的非负整数（数位dp）

红太狼 2022-09-01 07:59 145阅读 0赞

**1. 问题描述：**

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含连续的1 的个数。

**示例 1:**

输入: 5  
输出: 5

**解释:**

下面是带有相应二进制表示的非负整数<= 5：  
0 : 0  
1 : 1  
2 : 10  
3 : 11  
4 : 100  
5 : 101  
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。  
说明: 1 <= n <= 10 ^ 9  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones

**2. 思路分析：**

这道题目属于经典的**数位dp**的题目，数位dp的题目一般求解的是小于等于n的满足某种性质的数目或者是求解一个区间满足某种性质的数目，对于第二种求解一个区间中满足某种性质的数目也是类似的，也需要求解出0~n的方案数目，然后两个区间的数目相减就是答案。这道题目求解的是小于等于n的二进制表示中不包含连续的1 的个数。对于数位dp的题目一般有两个步骤，① 预处理 ② 按位考虑（可以参照下面的树形图），对于预处理的过程我们考虑的是一般的情况，预处理其实也是一个递推的过程，一般需要定义一个二维数组，其中dp\[i\]\[j\]为总共有i位最高位填j的情况。对于第二个步骤我们需要先将数字n的每一位存储到一个列表中（python），从高位到低位枚举每一位可能填的数字的情况，对于当前的这一位x = num\[i\]，我们首先考虑填0~x-1的数字这样剩余的位可以随便填，结合预处理的情况我们就可以直接计算出当前有i位，并且当前这一位填0~x-1的数目，当枚举到下一位的时候那么这一位填的就是x，这样从高位到低位开始枚举考虑每一位可能填的数字情况就可以将总的数目计算出来。对于这道题目来说预处理的时候我们可以考虑dp\[i\]\[0\]和dp\[i\]\[1\]，dp\[i\]\[0\]表示总共有i位最高位填0的情况，这个时候上一个位就可以填0或者是1，dp\[i\]\[1\]表示总共有i位最高位填1的情况，这个时候上一位就只能填0，所以通过递推就就可以将一般的情况处理出来。接下来就是按位考虑的过程，从高位到低位开始枚举，使用last变量来记录上一位的数字这样可以判断是否存在连续的两个1，对于当前位是1那么我们可以考虑当前位为填0的情况，这个时候答案累加上dp\[i\]\[0\]即可，枚举下一个低位的时候那么当前位填的就是1，并且需要判断上一个数字是否是1如果是1那么直接返回答案即可，因为后面的分支都是不合法的，当循环结束没有返回结果的时候需要加上最后一个满足要求的填1的数目即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

class Solution:
        def findIntegers(self, n: int) -> int:
            nums = list()
            # 将n的每一位存储到列表中
            while n > 0:
                nums.append(n % 2)
                n //= 2
            # 预处理, 声明一个预处理的二维数组其中dp[i][0]表示当前有i位最高位填0, dp[i][1]表示当前有i位最高位填1
            dp = [[0] * 2 for i in range(len(nums) + 1)]
            dp[1][0] = dp[1][1] = 1
            for i in range(2, len(nums) + 1):
                # 当前这一位为0那么上一位可以随便填
                dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
                # 当前这一位为1那么上一位必须是0
                dp[i][1] = dp[i - 1][0]
            # 逆序从高位开始遍历, last记录上一个数字用来判断是否有两个连续的1
            last = 0
            res = 0
            for i in range(len(nums), 0, -1):
                x = nums[i - 1]
                # 当前位是1那么可以尝试当前位为0的情况
                if x:
                    res += dp[i][0]
                    # 如果有两个连续的1那么直接返回答案即可
                    if last == 1: return res
                last = x
            # 没有返回说明不存在连续的两个1这个时候需要加上最后一位填1的情况
            return res + 1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/3ba2a24bc4fa42f9b6705781792f1ffa.png