600. Non-negative Integers without Consecutive Ones

1. Question

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

2. Examples

Example 1:

Input: n = 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.


Example 2:

Input: n = 1
Output: 2


Example 3:

Input: n = 2
Output: 3


3. Constraints

• 1 <= n <= 109

5. Solutions

class Solution {
public int findIntegers(int n) {
int ans = 0;
// 斐波那契数列
int[] arr = new int[31];
arr[0] = 1;
// 只有一个数的时候有2个值符合要求
arr[1] = 2;
arr[2] = 3;

for (int i = 3; i < 31; i++) {
arr[i] = arr[i-1] + arr[i-2];
}

String str = Integer.toBinaryString(n);

for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '0') {
continue;
} else {
ans += arr[str.length() - i - 1];
}
// 有两个重复的1
if (i > 0 && str.charAt(i - 1) == '1') {
return ans;
}
}
return ans+1;
}
}