题解:
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;
}
};