338. Counting Bits [medium] (Python)

题目链接

https://leetcode.com/problems/counting-bits/

题目原文

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Hint:

1. You should make use of what you have produced already.
2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
3. Or does the odd/even status of the number help you in calculating the number of 1s?

思路方法

题目给出的提示，可以方便我们思考，不过不管怎样，最好首先将前几个数的二进制写出来观察。比如前10个数：

0
1
10
11
100
101
110
111
1000
1001
......

这题的关键在于找到规律，本质是个动态规划问题。对于如何利用已有的数据得到新的数据，方法比较多。

思路一

最暴力的思路，数一下每个数的二进制里面1的个数。虽然此做法可以AC，但不符合“Follow up”的要求，效率也低，仅供参考。

代码

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        res = []
        for i in xrange(num + 1):
            res.append(bin(i).count('1'))
        return res

思路二

通过观察前10个数的二进制，可以发现：[2-3]中1的个数是[0-1]中个数对应加一；[4-7]是[0-3]对应加一；[8-15]是[0-7]对应加一；…… 本质上，是将最高位的1变成0得到对应的较小的数。

代码一

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        dp = [0]
        i = 0
        while True:
            for j in xrange(1<<i, 1<<(i+1)):
                if j > num:
                    return dp
                dp.append(1 + dp[j - (1<<i)])
            i += 1
        return dp

说明
基于上面的思路，可以通过Python的列表extend操作解决问题，不过会浪费一些空间。代码如下：

代码二

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        dp = [0, 1]
        while len(dp) <= num:
            dp.extend(map(lambda x:x+1, dp))
        return dp[:num+1]

思路三

上面的思路是将一个数的最高位的1去掉得到较小的数，那么也可以将最低位的1去掉得到较小的数，于是有公式：
dp[i] = dp[i&(i-1)] + 1

代码

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        dp = [0]
        for i in xrange(1, num + 1):
            dp.append(dp[i & (i-1)] + 1)
        return dp

思路四

另外，可以考虑奇偶性，将当前的数右移一位，若当前数是奇数那么1的个数不变；否则1的个数加一，公式如下：
dp[i] = dp[i>>1] + (i&1)

代码

class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        dp = [0]
        for i in xrange(1, num + 1):
            dp.append(dp[i >> 1] + (i & 1))
        return dp

PS: 写错了或者写的不清楚请帮忙指出，谢谢！
转载请注明：http://blog.csdn.net/coder_orz/article/details/52063216