動態規劃攻略之:位元位計數

語言: CN / TW / HK

「這是我參與11月更文挑戰的第12天,活動詳情檢視:2021最後一次更文挑戰

題目

給你一個整數 n ,對於 0 <= i <= n 中的每個 i ,計算其二進位制表示中 1 的個數 ,返回一個長度為 n + 1 的陣列 ans 作為答案。

示例1:

輸入:n = 2 輸出:[0,1,1] 解釋: 0 --> 0 1 --> 1 2 --> 10

示例2

輸入:n = 5 輸出:[0,1,1,2,1,2] 解釋: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

解題思路

首先來看一個概念:最低設定位

最低設定位是正整數二進位制中最低的 1 所在位。例如,1010 的二進位制表示是 1010,其最低設定位為 2。

於是,定義一個正整數 x, 令 y = x & (x - 1), 則 y 為將 x 的最低設定位從 1 變成 0 之後的數,顯然 0 <= y < x, bits[x] = bits[y] + 1。因此對於任意正整數 x, 都有 bits[x] = bits[x & (x - 1)] + 1。遍歷從 1 到 n 的每個正整數,計算 bits 的值。

程式碼實現

java class Solution { public int[] countBits(int n) { int[] bits = new int[n + 1]; int highBit = 0; for (int i = 1; i <= n; i++) { if ((i & (i - 1)) == 0) { highBit = i; } bits[i] = bits[i - highBit] + 1; } return bits; } }

最後

  • 時間複雜度:O(n)。

  • 空間複雜度:O(1)。

往期文章:

請你喝杯 ☕️ 點贊 + 關注哦~

  1. 閱讀完記得給我點個贊哦,有👍 有動力
  2. 關注公眾號--- HelloWorld傑少,第一時間推送新姿勢

最後,創作不易,如果對大家有所幫助,希望大家點贊支援,有什麼問題也可以在評論區裡討論😄~