[数据结构与算法]leetcode600. 不含连续1的非负整数

思路

1. 暴力，每次后移一位与当前值&如果为0，则当前值符合条件
2. dp[i][1] = dp[i-1][0],dp[i][0] = dp[i-1][1]+dp[i-1][0]得出第i位的值是0或者1时的有效数量。1[......]--->0[.....], 0[......]->0[.....]+1[.....]
3. 我们只把第i个有效位1换为0，这个1后面怎么放数字，都会比n小，res = dp[i-1][0]+d[i-1][1]，如果有连续的1，那么就返回res
   

代码

int dp[32][2];
void getdp(){
    int i;
    dp[0][0] = 1;
    dp[1][1] = 1;
    dp[1][0] = 1;
    for(i=2;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) {
    getdp();
    int k = 30;
    int res = 0;
    int pre = 0;
    while (k>=0) {
        if(n&(1<<k)){
            res = res + dp[k][0]+dp[k][1];
            if(pre){
                return res;
            }
            pre = 1;
        }
        else pre = 0;
        k--;
    }
    return res+1;//未出现连续的1，那么其本身也是一个合法的数
    
}