GuilinDev

Lc0338

05 August 2008

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.

题意和分析

给一个整数n，找出0到n间数字二进制表达式中1的个数，给了很多限制条件，就是不让一位一位去算，而是找规律。看了discussion才知道dp是怎样来的：

首先给一个例子：

Index： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

相应的1的个数：0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

四个一组看，很容易看出来重叠子问题了

dp[0] = 0;

dp[1] = dp[0] + 1;

dp[2] = dp[0] + 1;

dp[3] = dp[1] +1;

dp[4] = dp[0] + 1;

dp[5] = dp[1] + 1;

dp[6] = dp[2] + 1;//为了找寻规律，这里就不是dp[6] = dp[1] + 1了

dp[7] = dp[3] + 1;

dp[8] = dp[0] + 1;
…

从上述表达式可以得出递归式：

dp[1] = dp[1-1] + 1;

dp[2] = dp[2-2] + 1;

dp[3] = dp[3-2] +1;

dp[4] = dp[4-4] + 1;

dp[5] = dp[5-4] + 1;

dp[6] = dp[6-4] + 1;

dp[7] = dp[7-4] + 1;

dp[8] = dp[8-8] + 1;
…

dp[index] = dp[index - offset] + 1， 从index = 1开始，其中，如果当前索引i是offset的两倍，那offset自增加倍。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int[] countBits(int num) {
        int[] result = new int[num+1];
        int offset = 1;
        for (int index = 1; index <= num; index++) {
            if (offset*2 == index) {
                offset *= 2;
            }
            result[index] = result[index - offset] + 1;//重叠子问题
        }
        return result;
    }
}

###

1
2
3
4
5
6
7
8
9
10

class Solution {
    public int[] countBits(int num) {
        int[] results = new int[num + 1];//从0到num
        Arrays.fill(results, 0); //results[0] = 0;
        for (int i = 1; i <= num; i++) {
            results[i] = results[i & i - 1] + 1;//dp递推式，下一个元素是上一个元素+1（下一个元素和上一个元素的关系是相差一个二进制的1）
        }
        return results;
    }
}
This site is open source. Improve this page.