2016/07/14

leetcode Counting Bits

leetcode 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.
給一個正整數，輸出 0 ≤ i ≤ num 的二進制數值 1 的數量，明明很簡單的題目。但是後面的條件說要在 O(n) 解決掉，而不能用到 O(n * sizeof(integer))，所以直覺的寫個 function 用 shift 去計算個別數值 1 的數量並不能滿足條件。只好回歸二進制的特性找線索。
二進制每次+1的時候，就是最後一位 0 變 1 或 1 變 0，每個位數從 1 變成 0 的時候，就往前進一位。
所以 1,2,4,8,16,32,64...在進位之後，低位數就開始循環。列個清單來驗證一下這樣的推論

十進制二進制1 的數量
00000 00000
10000 00011
20000 00101
30000 00112
40000 01001
50000 01012
60000 01102
70000 01113
80000 10001
90000 10012
100000 10102
110000 10113
120000 11002
130000 11013
140000 11103
150000 11114
從表格已經可以看出 1 的數量在 1, 2, 4, 8 的時候，就是複製前面 1, 2, 4, 8 個結果，並將新複製的結果 + 1，也就是重複前面的循環但是要再加上本身進位所增加的那一個。

十進制複製輸出結果
0
0
10 00 1
201 0101 12
40112 01120112 1223
801121223 0112122301121223 12232334
確定這個方法可行，開始動手寫程式啦
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* countBits(int num, int* returnSize) {
    int s, ss, i;
    *returnSize = num+1;
    int * retvals = malloc(sizeof(int) * (num+1));
    memset(retvals, 0, sizeof(int));

    s=1;
    retvals[0] = 0;
    while(s <= num)
    {
 if(s*2 > num)
 {
     ss = num - s + 1;
 }
 else
 {
     ss = s;
 }
 memcpy(retvals + s, retvals, sizeof(int) * ss);
 for(i=0;i<ss;i++)
 {
     retvals[s+i]++;
 }
 s = s<<1;
   }
    return retvals;
}

void main(int argc, char *argv[])
{
 int * resarr;
 int rescnt, i;

 if(2 != argc)
 {
  printf("What?\n");
  return;
 }
 
 if(atoi(argv[1]))
 {
  resarr = countBits(atoi(argv[1]), &rescnt);
  printf("[%d", resarr[0]);
  for(i=1; i<rescnt; i++)
  {
   printf(",%d", resarr[i]);
  }
  printf("]\n");
 }
 else
 {
  printf("Oh! Oh!\n");
 }
}
on

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)