600. Non-negative Integers without Consecutive Ones 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int findIntegers(int n) {
        // 关键点：对于 6 = (110) 这样的数字，我们应该在 (0110) 的视野来进行计算，以便包含左侧 bit 位为 0 的数字

        // 定义 dp[i] 为高度为 i 的根节点为 0 的树中的不含连续 1 的路径数量，易知 dp[i] = dp[i - 1] + dp[i - 2], 对于有符号数，最大高度为 32
        int[] dp = new int[33];
        dp[1] = 1; // 高度为 1 时路径数为 1
        dp[2] = 2; // 高度为 2 时路径数为 2

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

        int preBit = 0, res = 0;
        for (int i = 30; i >= 0; i--) {
            int val = 1 << i;
            if ((n & val) != 0) {
                // 当前根节点为 0 的树存在右子树，那么此时一定存在左子树且左子树为满二叉树，所以此时加上左子树中不含连续 1 的路径数量
                // val 为第 i + 1 位为 1 的 bit 位表示，对应的树的高度为 i + 1
                res += dp[i + 1];

                // 如果父节点值为 1, 说明当前子树不能被纳入，直接返回
                if (preBit == 1) {
                    return res;
                }

                preBit = 1;
            } else {
                // 当前根节点为 0 的树不存在右子树

                preBit = 0;
            }

            // 当 i 等于 0 时，是与 1 做比较，当前是作为 (00) 或 (01) 时的视野。所以整个 for 循环没有处理最后单个 bit 位作为根节点为 0 的树时的情况，此时只能有 1 条路径，即 (0) 自身
            if (i == 0) {
                res++;
            }
        }

        return res;
    }
}

References

600. Non-negative Integers without Consecutive Ones