600. Non-negative Integers without Consecutive Ones

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(位数) 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的没有连续1的二进制str，且end in 0.
b[i]： 长度为i的没有连续1的二进制str，且end in 1.
则状态转移方程：
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的，所以先按所有位数n求，作为part1；part2: 再减去

我们怎么确定多了多少种情况呢，假如给我们的数字是8，二进制为1000，我们首先按长度为4算出所有情况，共8种。仔细观察我们十进制转为二进制字符串的写法，发现转换结果跟真实的二进制数翻转了一下，所以我们的t为"0001"，那么我们从倒数第二位开始往前遍历，到i=1时，发现有两个连续的0出现，那么i=1这个位置上能出现1的次数，就到one数组中去找，那么我们减去1，减去的就是0101这种情况，再往前遍历，i=0时，又发现两个连续0，那么i=0这个位置上能出1的次数也到one数组中去找，我们再减去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;
    }
}