不含连续1的非负整数Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
给定一个正整数 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
# 思路
int[] help = new int [32];
String s =Integer.toBinaryString(num);
# 解法
class Solution {
public int findIntegers(int num) {
int[] help = new int [32];
help[0] = 1;
help[1] = 2;
help[2] = 3;
//长度为 i 的二进制数中符合条件数字的个数
for (int i = 3;i<help.length;i++){
// 第i位为1那么i-1必为0 对应的有help[i-2]个 第i位为0 有help[i-1]个数
help[i] = help[i-1]+help[i-2];
}
String s =Integer.toBinaryString(num);
//有10000000或者1xxxx10000存在 (即 最右边为1的位置 只取了0的情况,缺失了1的情况)所以 cnt为1
int cnt = 1;
int prebit = 0;
for (int i = 0;i<s.length();i++){
if (s.charAt(i)=='1') {
// 使第 s.length - i 位为 0 num中高位所有为 1 的数为1
// s.length -i 为 1 的情况 交由后面计算否则会产生超界
cnt += help[s.length()-1-i];
//如果有 11 存在 之后不可能使num高位所有为 1 的数为1 break
if (prebit==1){
cnt--;
break;
}
prebit =1;
}else {
prebit =0;
}
}
return cnt; }
}
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
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
# 总结
- 分析出几种情况,然后分别对各个情况实现