Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.
Example 1:
Input: 5
Output: 5
Explanation:
Here are the non-negative integers <= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.
Note: 1 <= n <= 109
先看子問題：
Given a positive integer N(位數(shù)) count all possible distinct binary strings of length N such that there are no consecutive 1’s.
Examples:
Input: N = 2
Output: 3
// The 3 strings are 00, 01, 10
Input: N = 3
Output: 5
// The 5 strings are 000, 001, 010, 100, 101
DP方法解娜搂。a[i]: 長度為i的沒有連續(xù)1的二進(jìn)制str，且end in 0.
b[i]： 長度為i的沒有連續(xù)1的二進(jìn)制str吱抚，且end in 1.
則狀態(tài)轉(zhuǎn)移方程：
a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1]
代碼：
int a[] = new int [n];
int b[] = new int [n];
a[0] = b[0] = 1;
for (int i = 1; i < n; i++)
{
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
}
int result = a[n-1] + b[n-1];
Solution：
思路：再看本問題百宇，是要求<= num的，所以先按所有位數(shù)n求秘豹，作為part1携御；part2: 再減去
我們怎么確定多了多少種情況呢，假如給我們的數(shù)字是8既绕，二進(jìn)制為1000啄刹，我們首先按長度為4算出所有情況，共8種凄贩。仔細(xì)觀察我們十進(jìn)制轉(zhuǎn)為二進(jìn)制字符串的寫法誓军，發(fā)現(xiàn)轉(zhuǎn)換結(jié)果跟真實(shí)的二進(jìn)制數(shù)翻轉(zhuǎn)了一下，所以我們的t為"0001"疲扎，那么我們從倒數(shù)第二位開始往前遍歷昵时，到i=1時，發(fā)現(xiàn)有兩個連續(xù)的0出現(xiàn)椒丧，那么i=1這個位置上能出現(xiàn)1的次數(shù)壹甥，就到one數(shù)組中去找，那么我們減去1壶熏，減去的就是0101這種情況句柠，再往前遍歷，i=0時棒假，又發(fā)現(xiàn)兩個連續(xù)0俄占，那么i=0這個位置上能出1的次數(shù)也到one數(shù)組中去找，我們再減去1淆衷，減去的是1001這種情況缸榄，參見代碼如下：
Time Complexity: O(N) Space Complexity: O(N)
Solution Code：
public class Solution {
public int findIntegers(int num) {
// part1
StringBuilder sb = new StringBuilder(Integer.toBinaryString(num));
int n = sb.length();
int a[] = new int[n];
int b[] = new int[n];
a[0] = b[0] = 1;
for (int i = 1; i < n; i++) {
a[i] = a[i - 1] + b[i - 1];
b[i] = a[i - 1];
}
int result = a[n - 1] + b[n - 1];
// part2
sb = sb.reverse();
for (int i = n - 2; i >= 0; i--) {
if (sb.charAt(i) == '1' && sb.charAt(i + 1) == '1') break;
if (sb.charAt(i) == '0' && sb.charAt(i + 1) == '0') result -= b[i];
}
return result;
}
}
