## 题目描述：

LeetCode 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

## 解题思路：

```首先构造斐波那契数列dp = [1, 2, 3, 5, 8, 13 ...]

若bnum[idx] == bnum[idx - 1] == '1'：

说明出现两个连续的1，退出循环

若bnum[idx] == bnum[idx - 1] == '0':

说明出现连个连续的0，ans 减去 dp[size - idx] - dp[size - idx - 1] （等于dp[size - idx - 2]）```

## Python代码：

``````class Solution(object):
def findIntegers(self, num):
"""
:type num: int
:rtype: int
"""
dp = [1, 2]
for x in range(2, 32):
dp.append(dp[x - 1]+ dp[x - 2])
bnum = bin(num)[2:]
size = len(bnum)
ans = dp[size]
for idx in range(1, size):
if bnum[idx] == bnum[idx - 1] == '1':
break
if bnum[idx] == bnum[idx - 1] == '0':
ans -= dp[size - idx] - dp[size - idx - 1]
return ans
``````

Pingbacks已关闭。