LeetCode刷题实战600：不含连续1的非负整数

栈长 • 2022年5月5日 13:52 • 编程技术 • 阅读 291

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 不含连续1的非负整数，我们先来看题面：

https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含连续的 1 的个数。

示例

示例 1:
输入: n = 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

示例 2:
输入: n = 1
输出: 2

示例 3:
输入: n = 2
输出: 3

解题

https://blog.csdn.net/weixin_44560620/article/details/120243753

dp[i]代表当第i位为0时，不含连续1的个数。

从高位开始遍历n的每个二进制位，当n的第i位为1的时候，那么就会产生两种情况。就是当该位为0和当该位为1的情况，当该位为0，我们可以直接使用dp[i]得出该位为0时，可以产生多少个不含连续1的二进制数。如果该位为1，我们需要检查上一位是否为1，如果上一位为0，说明该位可以取1，继续以同样的方法向下遍历，否则就无法进行向下遍历。

class Solution {
    public int findIntegers(int n) {

        int[] dp=new int[31];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<31;i++)
            dp[i]=dp[i-1]+dp[i-2];
        int pre=0,res=0;
        for(int i=29;i>=0;i--)
        {
            int cur=(1<<i);
            if((n&cur)!=0)
            {
                res+=dp[i+1];
                if(pre==1)
                    break;
                pre=1;
            }else pre=0;
            if(i==0)
                res++;
        }
        
        return res;
        
    }
}