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

时间:2022-01-22 20:56:11

本题源自leetcode  600 https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/discuss/

=----------------------------------------------------------------------

思路: 动态规划  用斐波那契数列

代码:

 int findIntegers(int num) {
        vector<int> dp(32,0);
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2; i < 32;i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        int res = 0;
        int pre_bit = 0;
        int k = 30;
        while(k >= 0){
            if(num & (1 << k)){
                res += dp[k];
                if(pre_bit)
                    return res;
                pre_bit = 1;
            }
            else
                pre_bit = 0;
            k--;
        }
        return res + 1;
    }