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

1、题目

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

2、思路与解法

先将整数num转换为二进制表示,存入一个向量binaryNum中(存的是二进制表示的逆序)。

2.1、递归解法(超时了)

思路:先将num的二进制逆序表示转换为正常的二进制表示。然后从头开始遍历binaryNum向量,这是需要三个变量辅助记录当前的状态和之前的状态,index表示当前遍历到的向量中的元素的下标,flag表示前面是否有将1变为0,true表示有,false表示没有,frontval记录当前索引的前一位的值(可能为binaryNum中对应位的实际值,可能不是)。
对于每一位,我们根据flag变量作出相应的反应,假设对于第i位(从0开始计数):
(1) flag==false,我们知道对于前面的i+1位没有超出num的二进制的前i+1位的表示范围,此时根据binaryNum[i]的值作出下一步的反应:

  1. binaryNum[i]==0,则该位只能为0(选1的话会超出num值范围),frontval设为1,flag设为false;
  2. binaryNum[i]==1,则该位可以为0或者为1,如果为0,则frontval设为0,flag设为true;如果设为1,前提是frontval!=1,在满足前提的情况下,frontval设为1,flag设为false;

(2) flag==true,则说明前面的部分已经够小了,后面超不超出无所谓了,只要注意不要使得binaryNum[i]和frontval同时为1就可以了。
代码如下:

int findIntegers(int num) {
    
        vector<int> binaryNum;
        while(num!=0){
            binaryNum.push_back(num%2);
            num=num/2;
        }
        int len=binaryNum.size();
        reverse(binaryNum.begin(),binaryNum.end());
    
        int ret=0;
        ret=findInt(binaryNum,1,false,1)+findInt(binaryNum,1,true,0);
        return ret;
    }

    int findInt(vector<int> &binaryNum,int index,bool flag,int frontval){
        if(index>=binaryNum.size()){
            return 1;
        }
        if(!flag){
            if(binaryNum[index]==0)
                return findInt(binaryNum,index+1,false,0);
            else{
                if(frontval==0)
                    return findInt(binaryNum,index+1,false,1)+findInt(binaryNum,index+1,true,0);
                else
                    return findInt(binaryNum,index+1,true,0);
            }
        }
        else{
            if(frontval==0){
                return findInt(binaryNum,index+1,true,1)+findInt(binaryNum,index+1,true,0);
            }
            else
                return findInt(binaryNum,index+1,true,0);
        }
        return 0;
    }

结果显示超时
leetcode刷题----600. 不含连续1的非负整数

2.2非递归解法

思路:和斐波那契数列的递推关系一样。用一个新的向量ret,ret的每一位存储binaryNum对应位为0,且符合要求的数的个数。binaryNum对应的每一位只有两种取值,取0和取1。假设num的二进制表示(逆序)的第i位为0的符合要求的数的数目为ret[i],则ret [i]等于ret [i-1] (第i-1位为0) 加上ret [i-1] (第i-1位为1)。假设len为binaryNum的长度,则最终返回的结果为所有binaryNum上对应位的值位1的ret中值的和,当然不能有两个连续的1。
代码如下:

int findIntegers(int num) {
        if(num<2)
            return num+1;
        
        vector<int> binaryNum;
        while(num!=0){
            binaryNum.push_back(num%2);
            num=num/2;
        }
        int len=binaryNum.size();
        //reverse(binaryNum.begin(),binaryNum.end());
    
        vector<int> ret(len,0);
        ret[0]=1;
        ret[1]=2;
        for(int i=2;i<len;i++)
            ret[i]=ret[i-1]+ret[i-2];
        int res=0;
        for(int j=len-1;j>=0;j--){
            if(binaryNum[j]==1){
                res+=ret[j];
                if(j<len-1 && binaryNum[j+1]==1)
                    return res;
            }
        }
        res+=1;
        return res;
    }

结果:leetcode刷题----600. 不含连续1的非负整数

上一篇:600. 不含连续1的非负整数


下一篇:pyqt5窗体分隔