[LeetCode] 338. Counting Bits

轉自LeetCode

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.

<Solution>
這種題目就是做過才會知道規律

首先，先看不知道規律的時候，最直覺的做法

code 如下

	class Solution {
	public:
	vector<int> countBits(int num) {
	vector<int> ans(num+1, 0);
	for(int i = 1; i <= num; i++) {
	ans[i] = bitset<32>(i).count();
	}
	return ans;
	}
	};

view raw countingBits_1.cpp hosted with ❤ by GitHub

不過題目有說，不要用內建的函式來解

這時候就要觀察規律

i    i-1    i & (i-1)    count[i]
------------------------------
0    N/A      N/A         0 = count[0]
------------------------------
1    0       0x0000       1 = count[1] = count[0] + 1 = count [i & (i-1)] + 1
------------------------------
2    1       0x0000       1 = count[2] = count[0] + 1 = count [i & (i-1)] + 1
3    2       0x0010       2 = count[3] = count[2] + 1 = count [i & (i-1)] + 1
------------------------------
4    3       0x0000       1 = count[4] = count[0] + 1 = count [i & (i-1)] + 1
5    4       0x0100       2 = count[5] = count[4] + 1 = count [i & (i-1)] + 1
6    5       0x0100       2 = count[6] = count[4] + 1 = count [i & (i-1)] + 1
7    6       0x0110       3 = count[7] = count[6] + 1 = count [i & (i-1)] + 1

從上方的表可以看出一個規律

對於數字 i，它有幾個為 1 的 bit 數目，等同於 count [i & (i-1)] + 1

code如下
c++

	class Solution {
	public:
	vector<int> countBits(int num) {
	vector<int> ans(num+1, 0);
	for(int i = 1; i <= num; i++) {
	ans[i] = ans[i & (i-1)] + 1;
	}
	return ans;
	}
	};

view raw countingBits_2.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun countBits(n: Int): IntArray {
	val ans = IntArray(n+1) {0}
	for(i in 1..n) {
	ans[i] = ans[i and (i-1)] + 1
	}
	return ans
	}
	}

view raw counting_bits.kt hosted with ❤ by GitHub