力扣算法篇:不含连续1的非负整数

力扣算法篇:不含连续1的非负整数
题解:

class Solution {
public:
    //dp[i][j]  第i位以j结尾的所求数量 长度为i+1的二进制数 以j结尾的二进制数不包含连续1的个数
    int dp[32][2];
    void calculateF(){
        dp[0][0] = 1;//0
        dp[0][1] = 1;//1
        for(int i = 1;i<32;i++){
            dp[i][0] = dp[i-1][0]+dp[i-1][1];
            dp[i][1] = dp[i-1][0];
        }
    }
    int findIntegers(int n) {
        //0-n中 二进制不包含连续1的个数
        calculateF();
        //二进制数组
        vector<int> num;
        while(n){
            num.push_back(n%2);
            n/=2;
        }
        //结果
        int res = 0;
        //上一位
        int last =  0;
        for(int i = num.size()-1;i>=0;i--){
            if(num[i]){
                //该位为1 
                res+=dp[i][0];
                //上一位是1 连续1 方案数计算完毕
                if(last == 1){
                    break;
                }
            }
            //最后一位 上一位是0 结果+1
            if(i==0 && last == 0){
                res++;
            }
            //最后一位  上一位是1 该位为0 结果+1
            if(i == 0 && last == 1 && num[i] == 0){
                res++;
            }
            last = num[i];
        }
        return res;
    }
};
上一篇:Css之nth-of-type与nth-child的区别


下一篇:疫情期间···