frendguo's blog

【LeetCode】338. Counting Bits

原文地址:https://leetcode.com/problems/counting-bits/#/description

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.

起初的一看,这不就是求 1 个数的题吗?别以为变多了几个数就不认识了,然后才看到要求时间复杂度和空间复杂度都是O(n)。

然后就开始懵逼了。。既然是这样的话,那一定有规律我没找到。于是找啊找,顺便看了提示

好像发现了什么,于是在纸上把[2-3], [4-7],[8-15] 的二进制分别写出来,看看有木有什么规律。。

于是,就发现了个公式 f(i) = f(i / 2) + i % 2

接下来就是写代码了:

static int[] CountingBits(int num)
{
	int[] res = new int[num + 1];
	for (int i = 0; i <= num; i++)
	{
		res[i] = res[i >> 1] + (i & 1);
	}
	return res;
}

然后又看到别的大神的一个方法,方法挺简单的,之前用过好几次的方法,可是就是不会~

根据 n & (n - 1) => 去掉 n 的最低位的 1.所以代码就出来了~

static int[] CountingBits2(int num)
{
	int[] res = new int[num + 1];
	for (int i = 0; i <= num; i++)
	{
		res[i] = res[i & (i - 1)] + 1;
	}
	return res;
}

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading