LeetCode Js-338. Counting Bits

    AllenLi
    LeetCode Js-String

    Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i. 

    給予一個整數 n，回傳一個陣列 ans 的長度為 n + 1，
讓每個 i (0 <= i <= n)，ans[i] 是 i 的二進位數量表示。

    Example 1:

    Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

    Example 2:

    Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

    Solution:
    1. 建立 ans 陣列為 [0]。
    2. 執行 i = n 的迴圈，
    每一輪 ans 的陣列 i 位置皆為 ans[Math.floor(i / 2)] + i % 2 的和。

    -------------
     0000
     8421
-------------

0    0000    0
-------------
1    0001    1
-------------
2    0010    1
3    0011    2
-------------
4    0100    1
5    0101    2
6    0110    2
7    0111    3
-------------
8    1000    1
9    1001    2
10   1010    2
11   1011    3
12   1100    2
13   1101    3
14   1110    3
15   1111    4

    3. 回傳 ans。

    Code 1:

    var countBits = function(n) {
  if(n === 0) return [0];
  let ans = [0]

  for (let i = 0; i <= n; i++) {
    ans[i] = ans[Math.floor(i / 2)] + i % 2
  }
  return ans
};

    FlowChart:
    Example 1

    Input: n = 2

ans[0] = ans[Math.floor(0 / 2)] + 0 % 2 => [ 0 ]
ans[1] = ans[Math.floor(1 / 2)] + 1 % 2 => [ 0, 1 ]
ans[2] = ans[Math.floor(2 / 2)] + 2 % 2 => [ 0, 1, 1 ]

return ans = [ 0, 1, 1 ]

    Example 2

    Input: n = 5

ans[0] = ans[Math.floor(0 / 2)] + 0 % 2 => [ 0]
ans[1] = ans[Math.floor(0 / 2)] + 0 % 2 => [ 0, 1 ]
ans[2] = ans[Math.floor(1 / 2)] + 0 % 2 => [ 0, 1, 1 ]
ans[3] = ans[Math.floor(2 / 2)] + 0 % 2 => [ 0, 1, 1, 2 ]
ans[4] = ans[Math.floor(3 / 2)] + 0 % 2 => [ 0, 1, 1, 2, 1 ]
ans[5] = ans[Math.floor(4 / 2)] + 0 % 2 => [ 0, 1, 1, 2, 1, 2 ]

return ans = [ 0, 1, 1, 2, 1, 2 ]

    Related Posts