算法@LeetCode:CountingBits

Log

• 【170425】完成 01 版（Python）提交
• 【170501】研究参考答案，并补充笔记

题目

Counting Bits

【题目类型备注】

动态规划, 位运算

提交

01

【语言】

Python

【时间】

170425

【思路】

既然是 DP 题，肯定要做表记录。

最开始的思路是根据每一个数 k 是否为奇数来判断，若是奇数则该数的 1 个数要么比 k-1 少，要么不变。但这就带来了问题：如何判断究竟是减少还是增加？是否需要引入对数函数云云？

想了一会儿觉得这可能需要用到位运算（事先并没有看题目的 tags），于是在思考，比如若将 k 右移一位后，能不能得到右移出去的数字是 1 还是 0。但很快我就发现：一旦 k 右移一位，得到的数字 k_ 必然比 k 小，也就是之前一定是计算过的；此后，只要根据 k 是否为奇数来决定究竟 bits[k]（k 的二进制表示中 1 的个数）是 bits[k_] + 1 还是 bits[k_] 即可。于是这仍然利用了子问题，只是这个子问题并不是通常以为的小 1~2 个直观规模的子问题，而是在位运算上小 1 个规模的子问题。

于是有了下述代码。

【代码】

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        # Use bit manipulation to calculate bits
        bits = [0]
        for i in range(1, num+1):
          iOdd = (1 == (i % 2))
          i_ = i >> 1
          bits.append(bits[i_])
          if iOdd:
            bits[i] += 1
        # Return the result
        return bits

【结果】

运行时：192 ms

报告链接：https://leetcode.com/submissions/detail/101111975/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 87.03 % of python submissions.

00

参考解法：

• Java
  • 1：思路和我的一致，利用位运算中的「移位」
  • 2：这个思路妙在它利用的另一种模式，即每当遇到 2^n 时，1 的计数自动回到 1，与 2^n - 1 没有直接数量上的关系
• C++：也是运用了位运算，但不是使用「移位」，而是使用了「按位与」（相邻量数「按位与」），解决了二进制进位与否对 1 的数量的影响问题（若二进制进位，则按位与结果为 0，加 1 则正好为 1；若二进制未进位，则按位与结果是上一个数，则可以利用上一个数的计数）

自己实现一遍最优解：

• [language]。。。