class Solution {
public:
int findIntegers(int n) {
}
};
600. 不含连续1的非负整数
给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。
示例 1:
输入: n = 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5： 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。
示例 2:
输入: n = 1 输出: 2
示例 3:
输入: n = 2 输出: 3
提示:
1 <= n <= 109原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-16 11:15:39
impl Solution {
pub fn find_integers(n: i32) -> i32 {
let n = n + 1;
let b: Vec<_> = format!("{:b}", n).chars().rev().collect();
let n = b.len();
let dp: Vec<_> = (0..n)
.scan((1, 0), |s, _| {
*s = (s.0 + s.1, s.0);
Some(*s)
})
.collect();
let mut ans = 0;
for i in (0..n).rev() {
if b[i] == '1' {
ans += dp[i].0;
}
if i < b.len() - 1 && b[i] == '1' && b[i + 1] == '1' {
break;
}
}
ans
}
// Rust的Const Expr功能还不是很完善（不能写循环），所以用了普通函数
fn dp() -> Vec<[i32; 2]> {
const N: usize = 33;
// dp[i][j]:二进制长度i 最高位是j(取值0或者1）的满足条件的数的数量
let mut dp = vec![[0, 0]; N];
dp[1][0] = 1;
dp[1][1] = 1;
for i in 1..N - 1 {
dp[i + 1][1] = dp[i][0];//只能是0
dp[i + 1][0] = dp[i][0] + dp[i][1];//可以是0或者1
}
dp
}
pub fn find_integers2(n: i32) -> i32 {
let dp = Self::dp();
let mut len = 0;
for i in (0..32).rev() {
if (n >> i) & 1 == 1 {
len = i;
break;
}
}
let mut ans = 0;
let mut prev = 0;
for i in (0..=len).rev() {
let cur = (n >> i) & 1;
if cur == 1 {
// 那么如果当前位置填了0，后面就都符合要求，所以把当前位置为0的所有方案数都加上
// 但是如果填了1，dp里的方案就不能保证一直小于了，因为我们默认现在从[i,len]的所有能取1的位置都取1了
// 需要继续搜索
ans += dp[i + 1][0];
}
if cur == 1 && prev == 1 {
// 为什么可以break呢？因为已经把当前位取0的方案数加上了，又不能取1，所以只能break了
break;
}
prev = cur;
// 因为遍历到了底部，说明n的二进制表达本身里面就没有连续的1，把n本身也算上一种方案
if i == 0 {
ans += 1
}
}
ans
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-09-16 11:13:38
func findIntegers(n int) int {
s := strconv.FormatInt(int64(n), 2)
m := len(s)
dp := make([][2]int, m)
for i := range dp {
dp[i] = [2]int{-1, -1}
}
var f func(int, int8, bool) int
f = func(i int, pre1 int8, isLimit bool) (res int) {
if i == m {
return 1
}
if !isLimit {
dv := &dp[i][pre1]
if *dv >= 0 {
return *dv
}
defer func() { *dv = res }()
}
up := 1
if isLimit {
up = int(s[i] & 1)
}
res = f(i+1, 0, isLimit && up == 0) // 填 0
if pre1 == 0 && up == 1 { // 可以填 1
res += f(i+1, 1, isLimit) // 填 1
}
return
}
return f(0, 0, true)
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.2 MB, 提交时间: 2023-09-16 11:13:21
class Solution {
public:
int findIntegers(int n) {
int m = __lg(n), dp[m + 1][2];
memset(dp, -1, sizeof(dp));
function<int(int, bool, bool)> f = [&](int i, bool pre1, bool is_limit) -> int {
if (i < 0) return 1;
if (!is_limit && dp[i][pre1] >= 0) return dp[i][pre1];
int up = is_limit ? n >> i & 1 : 1;
int res = f(i - 1, false, is_limit && up == 0); // 填 0
if (!pre1 && up == 1) res += f(i - 1, true, is_limit); // 填 1
if (!is_limit) dp[i][pre1] = res;
return res;
};
return f(m, false, true); // i 从 m 往小枚举，方便位运算
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 38.9 MB, 提交时间: 2023-09-16 11:13:09
class Solution {
char s[];
int dp[][];
public int findIntegers(int n) {
s = Integer.toBinaryString(n).toCharArray();
var m = s.length;
dp = new int[m][2];
for (var i = 0; i < m; i++) Arrays.fill(dp[i], -1);
return f(0, false, true);
}
int f(int i, boolean pre1, boolean isLimit) {
if (i == s.length) return 1;
if (!isLimit && dp[i][pre1 ? 1 : 0] >= 0) return dp[i][pre1 ? 1 : 0];
var up = isLimit ? s[i] - '0' : 1;
var res = f(i + 1, false, isLimit && up == 0); // 填 0
if (!pre1 && up == 1) res += f(i + 1, true, isLimit); // 填 1
if (!isLimit) dp[i][pre1 ? 1 : 0] = res;
return res;
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.2 MB, 提交时间: 2023-09-16 11:12:54
class Solution:
def findIntegers(self, n: int) -> int:
s = str(bin(n))[2:]
@cache
def f(i: int, pre1: bool, is_limit: bool) -> int:
if i == len(s):
return 1
up = int(s[i]) if is_limit else 1
res = f(i + 1, False, is_limit and up == 0) # 填 0
if not pre1 and up == 1: # 可以填 1
res += f(i + 1, True, is_limit) # 填 1
return res
return f(0, False, True)
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-16 11:12:31
func findIntegers(n int) (ans int) {
dp := [31]int{1, 1}
for i := 2; i < 31; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
for i, pre := 29, 0; i >= 0; i-- {
val := 1 << i
if n&val > 0 {
ans += dp[i+1]
if pre == 1 {
break
}
pre = 1
} else {
pre = 0
}
if i == 0 {
ans++
}
}
return
}
javascript 解法, 执行用时: 88 ms, 内存消耗: 41.3 MB, 提交时间: 2023-09-16 11:12:15
/**
* @param {number} n
* @return {number}
*/
var findIntegers = function(n) {
const dp = new Array(31).fill(0);
dp[0] = dp[1] = 1;
for (let i = 2; i < 31; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
let pre = 0, res = 0;
for (let i = 29; i >= 0; --i) {
let val = 1 << i;
if ((n & val) !== 0) {
res += dp[i + 1];
if (pre === 1) {
break;
}
pre = 1;
} else {
pre = 0;
}
if (i === 0) {
++res;
}
}
return res;
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-16 11:12:02
class Solution {
public:
int findIntegers(int n) {
vector<int> dp(31);
dp[0] = dp[1] = 1;
for (int i = 2; i < 31; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int pre = 0, res = 0;
for (int i = 29; i >= 0; --i) {
int val = 1 << i;
if ((n & val) != 0) {
res += dp[i + 1];
if (pre == 1) {
break;
}
pre = 1;
} else {
pre = 0;
}
if (i == 0) {
++res;
}
}
return res;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.6 MB, 提交时间: 2023-09-16 11:11:51
class Solution {
public int findIntegers(int n) {
int[] dp = new int[31];
dp[0] = dp[1] = 1;
for (int i = 2; i < 31; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int pre = 0, res = 0;
for (int i = 29; i >= 0; --i) {
int val = 1 << i;
if ((n & val) != 0) {
res += dp[i + 1];
if (pre == 1) {
break;
}
pre = 1;
} else {
pre = 0;
}
if (i == 0) {
++res;
}
}
return res;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2023-09-16 11:11:37
'''
dp[t] 表示高度为 t−1、根结点为 0 的满二叉树中，不包含连续 1 的从根结点到叶结点的路径数量。
'''
class Solution:
def findIntegers(self, n: int) -> int:
dp = [0] * 31
dp[0] = 1
dp[1] = 1
for i in range(2, 31):
dp[i] = dp[i - 1] + dp[i - 2]
pre = 0
res = 0
for i in range(29, -1, -1):
val = (1 << i)
if n & val:
res += dp[i + 1]
if pre == 1:
break
pre = 1
else:
pre = 0
if i == 0:
res += 1
return res