文章目錄

• 題目描述
• 思路 & 代碼
• • • 無注釋二刷

題目描述

• 難點在于 O(n)
  

思路 & 代碼

• 理解題意，分析出 O(n) 復(fù)雜度應(yīng)該是要用到之前的值來得到當(dāng)前值——動態(tài)規(guī)劃
• 核心結(jié)論：奇數(shù)比前一個數(shù)多一個1，偶數(shù)和偶數(shù)除二后的數(shù)的1數(shù)量一樣
• 邊界 & 狀態(tài)轉(zhuǎn)移方程 & 最優(yōu)子結(jié)構(gòu) 見代碼注釋
• 時間復(fù)雜度 O(n)

class Solution {public int[] countBits(int num) {int[] ans = new int[num + 1];// 邊界：ans[0]已經(jīng)初始化為0了for(int i = 1; i <= num; i++){// 兩個狀態(tài)轉(zhuǎn)移方程// 奇數(shù)情況：比前一個偶數(shù)多1if((i & 1) == 1){ans[i] = ans[i - 1] + 1; }// 偶數(shù)情況：和當(dāng)前數(shù)除2后的數(shù)一樣else{ans[i] = ans[i >> 1];}// 最優(yōu)子結(jié)構(gòu)：ans[i - 1] or ans[i >> 1]}return ans;} }

無注釋二刷

• 當(dāng)然，之前的位運(yùn)算寫法確實更有逼格啦。。

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

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】338. 比特位计数（Java、位运算、动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。