题目
给定一个正整数 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^9
题解
/**
* 时间: 2021-09-11 22:12
* 分析: 判断给定数字的二进制表示是否存在连续的1
* 思路:
* 1. 位运算+dp
* 参考:
* 1. dp (官方解析) (当前实现)
*/
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;
}
}
Q.E.D.