LeetCode338解题思路

2019年06月29日 |

| algorithm

原题

338. 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 1:

1 2	Input: 2 Output: [0,1,1]

Example 2:

1 2	Input: 5 Output: [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.

解题思路

就像题目要求的，本题如果用简单的方式其实比较容易想到解决方法，就是会牺牲时间复杂度。
那么如果按题目要求的时间和空间复杂度都要是O(n)应该如何解答呢？

如果要保证时间复杂度在O(n)，那么一定要从2的n次方这个方向去思考方案。
首先发现如果i是2的n次方的话，那肯定只有一个1，就是在第n+1位。
接下来要找其他非2的n次方的数字的规律，经过观察发现：3 = 2 + 1，5 = 4 + 1，6 = 4 + 2， 7 = 4 + 3， 9 = 8 + 1， 10 = 8 + 2 依次类推。

代码实现

Golang实现

https://github.com/cook-coder/my-leetcode-solution/tree/master/medium/338

Golang中耗时最短的解法

func countBits(num int) []int {
    result := make([]int, num+1)
    for i := 1; i <= num; i++ {
        result[i] = result[i & (i-1)] + 1
    }
    return result
}