600 Non-negative Integers withou

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：

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：

Note: 1 <= n <= 10^9

解释下题目：

如果一个数，将它写成二进制形式，如果没有连续的两个1就说明这个数符合要求，否则就不符合要求。要做的是统计小于给定的数字中，有多少个符合要求。

1. 挨个判断

实际耗时：超时

    private boolean check(int num) {
        int i = 31;
        while (i > 0) {
            if ((num & (1 << i)) != 0 && (num & (1 << (i - 1))) != 0) {
                return false;
            }
            i--;
        }
        return true;
    }

  首先给出结论，这道题不管你用什么方法，只要你遍历了小于num的所有数字，肯定是死翘翘的，也就是说其实你得找规律，然后根据规律做题。然后从这道题我学到的是如何针对位进行运算：
第一种就是上面的代码所示，通过将1左移x位，然后再与num进行&操作，如果不是0，就说明那一位是1。
第二种是Java提供好的封装方法啦，可以通过Integer.toBinaryString()方法把一个int型的数转换成二进制的String，然后进行操作即可。

时间复杂度O(n)

空间复杂度O(1)

2. 动态规划

实际耗时：2ms

    public int findIntegers(int num) {
        StringBuilder sb = new StringBuilder(Integer.toBinaryString(num)).reverse();
        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];
        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;
    }

  首先我观察了一下，在[2^(i) , 2^(i+1)-1]这个区间的，符合要求的数字的个数，正好是斐波那契数列->[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]，利用这点可以极大加快速度，至于之后的怎么判断，说实话我感觉这个涉及到数学，我就先放放了。

时间复杂度O(log(n))

空间复杂度O(1)