「不包含连续1的非负整数」详解
in 算法 with 0 comment

「不包含连续1的非负整数」详解

in 算法 with 0 comment

google.png

Google面试中的中等难度面试题,你能百分百的过关吗?文末为大家附上了Google面试真题汇总,敬请关注

题目描述

给定一个正整数n,求出0到n中有几个数满足其二进制表示不包含连续的1。1<=n<=10^9

样例

输入:

5

输出:

5

说明:

0到5的二进制表示分别为:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101

这六个数中,只有3的二进制表示包含有连续的1,故答案为5

暴力方法

枚举0到n,判断其二进制是否包含连续的1,时间复杂度为O(n*log(n)),对于题目的n的范围来说比较大。

情况一 case1

考虑一种比较简单的情况,如果n=2^k - 1,其中k为正整数,那么问题就变成二进制数00……0b(k个0)到11……1b(k个1)中有几个数不包含连续的1,设答案为f(k)。

我们可以考虑k位二进制数的第一位:如果第一位是0,那么第二位既可以取0也可以取1,也就是说对后面的k-1位无影响,所以第一位为0的满足条件的数总共有f(k-1)个;如果第一位是1,那么由于不能出现连续的1,第二位只能取0,但是对后面的k-2位无影响,所以第一位为1的满足条件的数总共有f(k-2)个。

这样,我们就得到了:f(k) = f(k-1) + f(k-2)。边界条件为f(1)=2以及f(2)=3,由于f(0)=1满足原问题的题意也满足上述的转移方程,故可以取边界条件f(0)=1,f(1)=2,通过递推就可以得到f(2)=3,以及f(3)=5等等。

注意 tip
对于n不是2^k-1的一般情况,情况则比较复杂。上一种情况中,相当于k位二进制,每一位都可以选0或1,没有约束,而这种情况中则不行。

情况二 case2

举例来说,若n=10,二进制为1010b,如果最高位取0,那么这个数最大不过是0111b,不会超过10;而如果最高位取1,那么次高位如果再取1,就会使这个数超过10。

如何解决这个问题呢?

注意到,如果最高位取0,情况仍与情况1中相同,后面3位仍是无约束,答案为f(3)=5,而我们只需再考虑最高位取1的情况。这其实相当于把原本问题中,求0到10中的满足条件的数,分解成了0到7,以及8到10,分别在两个区间求满足条件的数,0到7的答案可直接参考情况1得到,8到10的部分的答案则可再分析。8到10,即1000b到1010b,由之前的分析,次高位只能取0,否则会使取到的数大于10。

第三位的分析与第一位相似,第三位如果取0,则最后一位无约束,这部分答案为f(1);第三位为1,则进一步分析。这样,就把1000b到1010b再次分成了1000b到1001b和1010b到1010b,即8到9,以及10两部分,8到9这部分的答案是f(1)=2。最后,答案再加上10本身,得到5+2+1=8。

情况三 case3

再看一个n的二进制中包含连续1的情况

n=12,二进制为1100b。和之前一样,先考虑最高位取值,把0到12分成0到7和8到12,0到7的部分的答案为f(3)=5,8到12的部分进一步考虑。8到12,即1000b到1100b,如果只考虑要求的数小于12,那么次高位当然既可以取0,又可以取1,但是,题目的另一个条件为不包含连续1,而最高位已经确定取1,所以次高位只能取0,这样一来,不管后面两位怎么取,得到的数都不会超过12,所以可以直接得到这部分的答案,f(2)=3。最终答案为5+3=8。

这种情况表明:在一步步分解区间时,如果遇到连续的1,就不需要再考虑后面的情况了,直接把前面几位与这一位得到的答案加起来即可。

整理分析

先得到n的二进制,设其长度为k,由高到低枚举n的二进制位。对于n的(由高到低)第i位,如果这一位为0,那么这一位只能取0,不增加答案;如果这一位为1,那么对于满足条件的数,如果这一位取0,那么后面k-i位无约束,这部分答案为f(k-i),加入答案,如果这一位取1,同时前一位也为1,那么可以直接返回答案(情况3),否则应继续考虑下一位二进制位(情况2)。最后,答案再加1,表示n本身(如果n本身包含连续1那么会因为情况3而直接返回答案,不会进入最后的加1)

n的二进制长度为log(n),故该算法的时间复杂度为O(log(n))。代码如下:

参考代码

Java:

public class Solution {
    public int findIntegers(int num) {
        if (num < 2) {
            return num + 1;
        }

        StringBuilder str = new StringBuilder(Integer.toBinaryString(num)).reverse();
        int k = str.length();

        int[] f = new int[k];
        f[0] = 1;
        f[1] = 2;
        for (int i = 2; i < k; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        int ans = 0;
        for (int i = k - 1; i >= 0; i--) {
            if (str.charAt(i) == '1') {
                ans += f[i];
                if (i < k - 1 && str.charAt(i + 1) == '1') {
                    return ans;
                }
            }
        }
        ans++;
        return ans;
    }
}

c++:

class Solution {
public:
    int findIntegers(int num) {
        if (num < 2) {
            return num + 1;
        }

        int k = 30;
        while ((num & (1 << k)) == 0) {
            k--;
        }
        k++;

        vector<int> f(k);
        f[0] = 1;
        f[1] = 2;
        for (int i = 2; i < k; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        int ans = 0;
        for (int i = k - 1; i >= 0; i--) {
            if ((num >> i) & 1) {
                ans += f[i];
                if ((num >> (i + 1)) & 1) {
                    return ans;
                }
            }
        }
        ans++;
        return ans;
    }
};

python:

class Solution(object):
    def findIntegers(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num < 2:
            return num + 1

        str = bin(num).replace('0b', '')
        str = str[::-1]
        k = len(str)

        f = [0] * k
        f[0] = 1
        f[1] = 2
        for i in xrange(2, k):
            f[i] = f[i - 1] + f[i - 2]

        ans = 0
        for i in xrange(k - 1, -1, -1):
            if str[i] == '1':
                ans += f[i]
                if i < k - 1 and str[i + 1] == '1':
                    return ans
        ans += 1
        return ans

面试官角度分析

这道题考察位运算的基本知识和动态规划的思想,难点在于如何原本的逐个统计问题通过二进制分类统计,属于面试中中等难度的题目,给出正确的解法可以达到hire

原文链接

Responses