600. 不含连续1的非负整数 力扣(困难) 数位dp

600. 不含连续1的非负整数

给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。

示例 1:

输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中,只有整数3违反规则(有两个连续的1),其他5个满足规则。
说明: 1 <= n <= 109

题解:

代码:自己写了dfs搜索,TLE,但还是要贴上来

class Solution {
public:
    int N,res;
    void dfs(int k,long long num)
    {
       if(k==0) {if (num<=N) res++; return;}
       if (num>N) return;
       dfs(k-1,num*2+0);
       if(num%2==0) dfs(k-1,num*2+1);
    }
    int findIntegers(int n) {
    int l=0;
    int t=n;
    while(t>0) {t/=2; l++;}
    N=n;
    res=0;
    dfs(l,0);
    return res;
    }
};

 

600. 不含连续1的非负整数 力扣(困难) 数位dp

上一篇:GitHub Windows客户端无法登录


下一篇:JavaScript——内置对象