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: 5Output: 5Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations:0 : 01 : 12 : 103 : 114 : 1005 : 101Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.

Note: 1 <= n <= 109

这道题给了我们一个数字，让我们求不大于这个数字的所有数字中，其二进制的表示形式中没有连续1的个数。根据题目中的例子也不难理解题意。我们首先来考虑二进制的情况，对于1来说，有0和1两种，对于11来说，有00，01，10，三种情况，那么有没有规律可寻呢，其实是有的，我们可以，这样我们就可以通过DP的方法求出长度为k的二进制数的无连续1的数字个数。由于题目给我们的并不是一个二进制数的长度，而是一个二进制数，比如100，如果我们按长度为3的情况计算无连续1点个数个数，就会多计算101这种情况。所以我们的目标是要将大于num的情况去掉。下面从头来分析代码，首先我们要把十进制数转为二进制数，将二进制数存在一个字符串中，并统计字符串的长度。然后我们利用中的方法，计算该字符串长度的二进制数所有无连续1的数字个数，然后我们从倒数第二个字符开始往前遍历这个二进制数字符串，如果当前字符和后面一个位置的字符均为1，说明我们并没有多计算任何情况，不明白的可以带例子来看。如果当前字符和后面一个位置的字符均为0，说明我们有多计算一些情况，就像之前举的100这个例子，我们就多算了101这种情况。我们怎么确定多了多少种情况呢，假如给我们的数字是8，二进制为1000，我们首先按长度为4算出所有情况，共8种。仔细观察我们十进制转为二进制字符串的写法，发现转换结果跟真实的二进制数翻转了一下，所以我们的t为"0001"，那么我们从倒数第二位开始往前遍历，到i=1时，发现有两个连续的0出现，那么i=1这个位置上能出现1的次数，就到one数组中去找，那么我们减去1，减去的就是0101这种情况，再往前遍历，i=0时，又发现两个连续0，那么i=0这个位置上能出1的次数也到one数组中去找，我们再减去1，减去的是1001这种情况，参见代码如下：

解法一：

class Solution {public:    int findIntegers(int num) {        int cnt = 0, n = num;        string t = "";        while (n > 0) {            ++cnt;            t += (n & 1) ? "1" : "0";             n >>= 1;        }        vector
     
       zero(cnt), one(cnt);        zero[0] = 1; one[0] = 1;        for (int i = 1; i < cnt; ++i) {            zero[i] = zero[i - 1] + one[i - 1];            one[i] = zero[i - 1];        }        int res = zero[cnt - 1] + one[cnt - 1];        for (int i = cnt - 2; i >= 0; --i) {            if (t[i] == '1' && t[i + 1] == '1') break;            if (t[i] == '0' && t[i + 1] == '0') res -= one[i];        }        return res;    }};
     

下面这种解法其实蛮有意思的，其实长度为k的二进制数字符串没有连续的1的个数是一个斐波那契数列f(k)。比如当k=5时，二进制数的范围是00000-11111，我们可以将其分为两个部分，00000-01111和10000-10111，因为任何大于11000的数字都是不成立的，因为有开头已经有了两个连续1。而我们发现其实00000-01111就是f(4)，而10000-10111就是f(3)，所以f(5) = f(4) + f(3)，这就是一个斐波那契数列啦。那么我们要做的首先就是建立一个这个数组，方便之后直接查值。我们从给定数字的最高位开始遍历，如果某一位是1，后面有k位，就加上f(k)，因为如果我们把当前位变成0，那么后面k位就可以直接从斐波那契数列中取值了。然后标记pre为1，再往下遍历，如果遇到0位，则pre标记为0。如果当前位是1，pre也是1，那么直接返回结果。最后循环退出后我们要加上数字本身这种情况，参见代码如下： 

解法二：

public:    int findIntegers(int num) {        int res = 0, k = 31, pre = 0;        vector
     
       f(32, 0);        f[0] = 1; f[1] = 2;        for (int i = 2; i < 31; ++i) {            f[i] = f[i - 2] + f[i - 1];        }        while (k >= 0) {            if (num & (1 << k)) {                res += f[k];                if (pre) return res;                pre = 1;            } else pre = 0;            --k;        }        return res + 1;    }};
     

参考资料：

本文转自博客园的博客，原文链接：

，如需转载请自行联系原博主。