不含连续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。
动态规划。
根据规律,跟斐波那契数列有关,但未找到这种解法。
代码用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
}
}
执行结果如下: