Leetcode 600. 不含连续1的非负整数
题目
给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。
示例:
输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中,只有整数3违反规则(有两个连续的1),其他5个满足规则。
说明: 1 <= n <= 109
题解
动态规划
dp[i]表示i位数字,不含连续1的非负整数的个数。
因此,有两种可能,
- 第i位为1时,第i-1位一定是0,故dp[i] = dp[i-2]
- 第i位为0时,第i-1位就没有约束条件,故dp[i] = dp[i-1]
综上,dp[i] = dp[i-1] + dp[i-2]
我们对num,从高位到低位进行判断,当第i+1位数为1时,我们就假设第i+1位为0,高位和num一致,那么ans += dp[i],即i位有效数字。同时,如何num有连续1的情况下,我们就直接break
详细过程见代码
代码
int findIntegers(int num) {
if(num == 0) return 1;
if(num == 1) return 2;
vector<int> dp(32,0);
dp[0] = 1;
dp[1] = 2;
for(int i=2; i<32; i++) //求解i位数,不含连续1的非负整数的个数
dp[i] = dp[i-1]+dp[i-2];
int ans=1,i=30;
bool pause=false;
while(i>=0){
if((num&(1<<i)) != 0){
ans += dp[i];
if(pause){
ans--; //本身含有连续1,故要去掉自己
break;
}
pause = true;
}else pause=false;
i--;
}
return ans;
}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。