LeetCode刷题【600】不含连续1的非负整数

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 1:

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 10⁹

先整个简单的直接dfs，在超时的边缘不断试探

class Solution {
    int max;
    int count = 1;
    public int findIntegers(int n) {
        max = n;
        dfs(1);
        return count;
    }

    public void dfs(int n){
        if(n > max)return;
        count++;
        if((n & 1)==1){
            dfs(n<<1);
        }else{
            dfs(n<<1);
            dfs((n<<1)+1);
        }
    }
}