给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。
示例 1:
输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5： 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。 说明: 1 <= n <= 109
class Solution { public: int findIntegers(int num) { if(num<2)return num+1; int f[30]; f[0]=1; f[1]=2; for(int i=2;i<30;i++) { //第1位为0，第2位随便，为f(i-1),第1位为1，第2位为0，第3位随便，为f(i-2) f[i]=f[i-1]+f[i-2]; } int ans=0; for(int i=29;i>=0;i--) { if((num>>i)&1) { ans+=f[i]; if(num>>(i+1)&1) { return ans; } } } return ans+1; } }; //参考下面某位老兄的思路，在当num>=2^k+2^(k-1)直接计算，小于时递归计算num-2^k class Solution { public: //动态规划思路，考虑i+1的情况 int findIntegers(int num) { if(num<=2){ return (num+1); } int n = floor(log2l(num+1)); vector<int> dp(n+1,0); dp[1]=1; dp[2]=1; int sum=3; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; sum+=dp[i]; } if(num>=(3<<n-1)) sum+=dp[n]+dp[n-1]; else sum+=findIntegers(num-(1<<n)); return sum; } };