600. 不含連續1的非負整數
給定一個正整數 n，找出小于或等于 n 的非負整數中，其二進制表示不包含 連續的1 的個數。
示例 1:輸入: 5
輸出: 5
解釋:
下面是帶有相應二進制表示的非負整數<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整數3違反規則（有兩個連續的1），其他5個滿足規則。
解題思路
- dp[i]代表當第i位為0時，不含連續1的個數。
- 從高位開始遍歷n的每個二進制位，當n的第i位為1的時候，那么就會產生兩種情況。就是當該位為0和當該位為1的情況，當該位為0，我們可以直接使用dp[i]得出該位為0時，可以產生多少個不含連續1的二進制數。如果該位為1，我們需要檢查上一位是否為1，如果上一位為0，說明該位可以取1，繼續以同樣的方法向下遍歷，否則就無法進行向下遍歷。
代碼
class Solution {public int findIntegers(int n) {int[] dp=new int[31];dp[0]=1;dp[1]=1;for(int i=2;i<31;i++)dp[i]=dp[i-1]+dp[i-2];int pre=0,res=0;for(int i=29;i>=0;i--){int cur=(1<<i);if((n&cur)!=0){res+=dp[i+1];if(pre==1)break;pre=1;}else pre=0;if(i==0)res++;}return res;}
}
)
