精华内容
下载资源
问答
  • 题目: 代码: class Solution { public: int fib(int n) { ...= 0) return 1; if (n == 1) return 2; int a = 1; int b = 2; int c = 3; int i = n - 2; while(i--) { a = b; b = c; c = a + b; } r

    题目:
    在这里插入图片描述
    代码:

    class Solution {
    public:
        int fib(int n) {
        if (n <= 0) return 1;
        if (n == 1) return 2;
        int a = 1;
        int b = 2;
        int c = 3;
        int i = n - 2;
        while(i--) {
            a = b;
            b = c;
            c = a + b;
        }
        
        return c;
    }
    
    int findIntegers(int num) {
        if (num == 0) return 1;
        if (num == 1) return 2;
        int nbits = 0;
        while(num>>nbits) {
            ++nbits;
        }
        
        if (num>>(nbits - 2) == 3) {
            return fib(nbits);
        } else {
            int mask = (1 << (nbits - 1)) - 1;
            return fib(nbits - 1) + findIntegers(num & mask);
        }
    }
    };
    

    额外结论:

    在这里插入图片描述

    展开全文
  • 600. 不含连续1非负整数

    千次阅读 2019-05-24 08:47:33
    给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含连续1的个数。 示例 1: 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : ...

    给定一个正整数 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

    展开全文
  • 不含连续1非负整数

    2019-07-24 09:19:49
    给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含连续1的个数。 示例 1: 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101...

    给定一个正整数 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

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路:

    不存在连续1的数字里面,1的后一位必定是0

    所以我们把这个数字右移一位,然后和自身位与的结果必定是0

    连续1的组合都是源自两个 11

    所以我们碰到11XXX  的时候就把后面的数字全部PASS,

    怎么处理呢?

    比如我们遇到了1100    

    就需要PASS掉1100 1101 1110 1111    

    一共4个数字,其实就是第两位能构成的数字个数

    也就是100,所以我们 还是把这个数字右移一位,然后和自身位与,就可以得到100

     

    class Solution {
    public:
        int findIntegers(int n) 
        {
            int ans = 0;
            for(int i=0;i<=num;i++)
            {
                int tmp = i&(i>>1);
                if(tmp==0)
                    ans++;
                else 
                {
                    i=i+tmp-1;
                    
                }
                cout<<i<<endl;
                    
            }
            return ans;
    
            
        }
    };

     

    展开全文
  • 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含连续1的个数。 示例 1: 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101...

    给定一个正整数 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

    思路:从高位到低位按位进行操作,假设我们要找到n位不包含连续1的数字,我们可以用递归的方法搞定,我们设f[i]表示求出了i位符合要求二进制串的数目,为了求出f[n],我们考虑如下情况:

                 

    上图中,我们可以知道如果我们知道 f[n-1]和 f[n-2] 的值,为了求出需要的 n位数字,我们可以给 f[n−1] 中所有数字后面添加 0,这样不会产生任何不合法数字。这些数字使得 f[n]中会包含 f[n-1]的结果。但我们不能直接给所有这些数字后加 1,因为可能会导致有连续 1 出现。所以如果我们要在后面加 1,我们必须确保上一个位置是 0。所以我们必须一次性给 f[n−2] 中的字符串最后面加 01。所以我们得到了递推式 f[n]=f[n−1]+f[n−2]。

    对于本题,我们从 num 的最高位开始考虑,对于第 i 个位置遇到的 1 (从低位序号为 0 开始考虑),我们将答案加 f[i],对每个遇到的 0 ,我们不给答案加任何值。我们还要记录上一个位置的数值为多少,一旦我们发现连续的 1 ,我们将第二个 1 变成 0 的影响考虑后即停止遍历。如果我们没有遇到连续的 1 ,我们一直遍历到最低位并将最终答案加 1 ,表示 num 也是合法数字,因为上述过程并没有考虑 num 进去。

    class Solution {
        public int findIntegers(int num) {
            int[] f=new int[32];
            f[0]=1;f[1]=2;
            for(int i=2;i<f.length;i++)
            	f[i]=f[i-1]+f[i-2];
            int i=30,sum=0,prev_bit=0;
            while(i>=0) {
            	if((num&(1<<i))!=0) {
            		sum+=f[i];
            		if(prev_bit==1) {
            			sum--;
            			break;
            		}
            		prev_bit=1;
            	}
            	else
            		prev_bit=0;
            	i--;
            }
            return sum+1;
        }
    }

     

    展开全文
  • 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续1 的个数。 示例 1: 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : ...
  • 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含连续1的个数。 示例 1: 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101...
  • 不含连续1非负整数 题目 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。 示例: 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : ...
  • 先将整数num转换为二进制表示,存入一个向量binaryNum中(存的是二进制表示的逆序)。 2.1、递归解法(超时了) 思路:先将num的二进制逆序表示转换为正常的二进制表示。然后从头开始遍历binaryNum向量,这是需要三...
  • 1。dp[pos][pre[sta] 表示到第pos位,前一位为pre,当前状态为sta的个数。 class Solution { public: int dp[40][2][2]; int bit[40]; int dfs(int pos,int pre,int sta,bool limit) { ...
  • 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续1 的个数。 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 其中,...
  • leetcode600 二进制不含连续1非负整数 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含连续的1的个数。 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 ...
  • 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含连续1的个数。 例如: 输入: 5 输出: 5 解释: 下面是带有相应二进制表示的非负整数<= 5: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100...
  • count = 0 for i in range(0,n+1): k = i str_b = '{:b}'.format(k) if len(str_b) == 1: count += 1 for j in range(len(str_b)-1): if str_b[j:j+2] == '11': ...
  • 实际上整个操作就是不停地从最高位取数,如果连续取到了两个1就终止 不然的话 就加上和1相同高度的那个0的结果,因为在1的那个位置上填0的数比n小,最后到叶节点实际上就是加上全0的这种情况 int findIntegers(int n...
  • 600. 不含连续1的非...
  • 600. 不含连续1非负整数 2021.9.11 600. 不含连续1非负整数 题解 class Solution { public: int findIntegers(int n) { // 预处理第 i 层满二叉树的路径数量 vector<int> dp(31); dp[0] = dp[1] = 1;...
  • Problem Source : https://leetcode-cn.com/problems/non-negative-integers-without-consecutive-ones/ Solution Source: ...600、不含连续1非负整数 给定一个正.
  • 600. 不含连续1非负整数 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。...
  • 不含连续1非负整数 刚开始写了个暴力循环,发现计算到:1000000000 时超时了,然后自己单独计算发现需要4秒才能算完,那么O(n) 时间遍历肯定是不行了。 根据题目提示:二进制不包含连续1,那么应该使用动态规划。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,803
精华内容 721
关键字:

不含连续1的非负整数