LeetCode 338 Counting Bits

• 2019 年 12 月 29 日
• 筆記

比特位計數

題意

給定一個非負整數 num. 對於 0 ≤ i ≤ num 範圍中的每個數字 i, 計算其二進位數中的 1 的數目並將它們作為數組返回.

示例 1:

輸入: 2  輸出: [0,1,1]

示例 2:

輸入: 5  輸出: [0,1,1,2,1,2]

解法

此題是 LeetCode 191 Number of 1 Bits 的拓展版, 可以利用那道題的兩種演算法, 只不過套個循環, 時間和空間複雜度都是 O(n).

那兩種解法就不說了. 這裡說下另一種解法.

這裡分為 2 的倍數 和 非 2 的倍數 兩種數.

他們有一個區別就是二進位的最低位是否為 1.

2 的倍數其二進位最低位都是 0. 非 2 的倍數其二進位最低位都是 1.

除 2 或右移一位後, 等於是去掉最低位, 那麼既然 2 的倍數最後一位都是 0, 所以對於 2 的倍數 除 2 或右移一位後, 數字 1 的個數並不會變.

那麼對於非 2 的倍數 n, n 肯定比 n - 1 的二進位中 1 的個數多一位. 如 n = 1111, n – 1 = 1110.

class Solution {      public int[] countBits(int num) {          int[] arr = new int[num + 1];          for (int i = 0; i <= num; i++) {              if (i % 2 == 0) {                  arr[i] = arr[i >> 1];              } else {                  arr[i] = arr[i - 1] + 1;              }          }          return arr;      }  }

時間複雜度 O(n), 空間複雜度 O(n).