2022-02-21：不含连续1的非负整数。 给定一个正整数 n ，返回范围在 [0, n] 都非负整数中

2022-02-21：不含连续1的非负整数。 给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。 输入: n = 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5： 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。 1 <= n <= 10的9次方。 力扣600。

答案2022-02-21：

动态规划。 根据规律，跟斐波那契数列有关，但未找到这种解法。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    n := 15
    ret := findIntegers(n)
    fmt.Println(ret)
}

func findIntegers(n int) int {
    i := 31
    for ; i >= 0; i-- {
        if (n & (1 << i)) != 0 {
            break
        }
    }
    // for循环出来之后，i表示，n最高位的1，在哪？
    // 从这个位置，往右边低位上走！
    dp := make([][][]int, 2)
    for ii := 0; ii < 2; ii++ {
        dp[ii] = make([][]int, 2)
        for j := 0; j < 2; j++ {
            dp[ii][j] = make([]int, i+2)
        }
    }
    return f(0, 0, i, n, dp)
}

func f(pre, alreadyLess, index, num int, dp [][][]int) int {
    if index == -1 {
        return 1
    }
    if dp[pre][alreadyLess][index] != 0 {
        return dp[pre][alreadyLess][index]
    }
    ans := 0
    if pre == 1 {
        ans = f(0, getMax(alreadyLess, twoSelectOne((num&(1<<index)) != 0, 1, 0)), index-1, num, dp)
    } else {
        if (num&(1<<index)) == 0 && alreadyLess == 0 {
            ans = f(0, alreadyLess, index-1, num, dp)
        } else {
            ans = f(1, alreadyLess, index-1, num, dp) + f(0, getMax(alreadyLess, twoSelectOne((num&(1<<index)) != 0, 1, 0)), index-1, num, dp)
        }
    }
    dp[pre][alreadyLess][index] = ans
    return ans
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

执行结果如下：

左神java代码