某算法竞赛初试题解 - 3K问题

题目

给定包含N个正整数的非递减数组A，假设该数组以以下形式保存了某个正整数K的值，即：

$K = \sum_{i=0}^N 2^{A[i]}$

例如给定$A=[1,4,5]$，则$K=2^1+2^4+2^5=50$。

则给出一个算法，计算出$3K$的二进制表示中为1的比特个数。 例如$3K=150=10010110_2$，程序返回值为4。

要求：时间复杂度控制在$O(N)$；空间复杂度控制在$O(1)$。

题解

对于二进制的题，一般都要从二进制本质出发，从数组A的定义可以得到：

$3K=3\sum^N_{i=0}2^{A[i]}=(2^0+2^1)\sum^N_{i=0}2^{A[i]}=\sum^N_{i=0}2^{A[i]}+\sum^N_{i=0}2^{A[i+1]}$

然后我们对数组中的每一位都加上1，然后合并回到数组A中，得到新的数组B，那么问题就转化为计算数组B代表的K的二进制中比特1的个数，为了表述方便，我们下文依然用数组A来举例表述。

让我们再次回到二进制的基本概念上来，对于一个二进制数：

$110_2=0\times 2^0 + 1\times 2^1 + 1\times 2^2$

那么数组A所代表的数字就变成了：

$K=2^1+2^4+2^5=1\times2^1+0\times2^2+0\times2^3+1\times2^4+1\times2^5=11001_2$

也就是说，数组A中的每一位数字A[i]，都代表了K的二进制中低A[i]位的比特位为1。

于是问题就简化为，将数组B表示的每个比特位加起来，最后的结果中1的个数，就是我们想要的结果。

代码实现如下：

def solution(A):
    bits = {} # 使用哈希表来存储每一个比特位，可以节省空间
    # 如果键值k存在于bits中，那么代表低k位为1
    for i in A:
        for j in range(i, i + 2):
            t = j
            while t in bits:
                del bits[t] // 逐比特执行加法
                t += 1
            bits[t] = 1
    # 最后输出bits中的键值个数即可
    return len(bits.keys())

题外话

然而，这道题是我在比赛结束一个小时之后才解出来的，认清了自己是菜鸡的事实。