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

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从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;
        
    }
}


上期推文:

LeetCode1-580题汇总,希望对你有点帮助!
LeetCode刷题实战581:最短无序连续子数组
LeetCode刷题实战582:杀掉进程
LeetCode刷题实战583:两个字符串的删除操作
LeetCode刷题实战584:寻找用户推荐人
LeetCode刷题实战585:2016年的投资
LeetCode刷题实战586:订单最多的客户
LeetCode刷题实战587:安装栅栏
LeetCode刷题实战588:设计内存文件系统
LeetCode刷题实战589:N 叉树的前序遍历
LeetCode刷题实战590:N 叉树的后序遍历
LeetCode刷题实战591:标签验证器
LeetCode刷题实战592:分数加减运算
LeetCode刷题实战593:有效的正方形
LeetCode刷题实战594:最长和谐子序列
LeetCode刷题实战595:大的国家
LeetCode刷题实战596:超过5名学生的课
LeetCode刷题实战597:好友申请 I:总体通过率
LeetCode刷题实战598:范围求和 II
LeetCode刷题实战599:两个列表的最小索引总和

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

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/22783.html

(0)
上一篇 2022年5月4日 13:52
下一篇 2022年5月6日 13:52

相关推荐

发表评论

登录后才能评论