力扣題解《卑鄙的異鄉(xiāng)人碎乃，巧妙的動態(tài)規(guī)劃（圖解過程））》
方法一：暴力計算
思路
- 從
至
遍歷姊扔，將每一個數(shù)字轉(zhuǎn)換成二進(jìn)制，轉(zhuǎn)換同時計算包含幾個
- 這里采用了模擬短除的方法梅誓，對數(shù)字不斷做除法恰梢，保存余數(shù)佛南，并將數(shù)字用商替換。
復(fù)雜度分析
時間復(fù)雜度
：遍歷需要
嵌言，將每個數(shù)轉(zhuǎn)二進(jìn)制需要
嗅回，其中
表示一個十進(jìn)制數(shù)N，轉(zhuǎn)換為二進(jìn)制后的長度呀页。
空間復(fù)雜度
快樂小視頻
具體代碼
class Solution {
public:
// 搞一個新的函數(shù)妈拌，來將10進(jìn)制轉(zhuǎn)換成2進(jìn)制數(shù)拥坛。
int trans2bit(int num){
int ans = 0;
// 直到num全部轉(zhuǎn)換完成蓬蝶，才退出循環(huán)
while(num > 0){
// 判斷當(dāng)前位是0還是1
// 無論是0還是1都添加到答案中
ans += num % 2;
// 不斷除以2，計算下一位
num /= 2;
}
// 返回二進(jìn)制表示時猜惋，1的個數(shù)
return ans;
}
vector<int> countBits(int num) {
vector<int> ans(num + 1);
// 0的結(jié)果就是0丸氛，因此從1開始循環(huán)
for(int i = 1; i <= num; i++){
ans[i] = trans2bit(i);
}
return ans;
}
};
方法二：簡單的動態(tài)規(guī)劃
思路
這是一道很模板的線性動態(tài)規(guī)劃。個人認(rèn)為線性動態(tài)規(guī)劃就是前人栽樹后人乘涼著摔。每個新結(jié)果的誕生缓窜，都可以依賴于前面已經(jīng)確定的結(jié)果線性變化得出。
-
狀態(tài)定義:
-
表示數(shù)字
對應(yīng)的二進(jìn)制表示中
的數(shù)量谍咆。
-
-
狀態(tài)轉(zhuǎn)移:
-
當(dāng)
dp[i] = dp[i / 2] -
當(dāng)
最終結(jié)果多1。因此
dp[i] = dp[(i - 1) / 2] + 1
-
當(dāng)
轉(zhuǎn)移方程：
-
初始狀態(tài):
-
-
-
返回值:
- 返回
列表。
- 返回
復(fù)雜度分析
時間復(fù)雜度
誓焦。
空間復(fù)雜度
快樂小視頻
具體代碼
class Solution {
public:
vector<int> countBits(int num) {
// 預(yù)先開好空間
vector<int> dp(num + 1);
// 同樣不需要從0開始，因為dp[0] = 0
for(int i = 1; i <= num; i++){
if(i % 2 == 0){ // 偶數(shù)
dp[i] = dp[i / 2];
}
else{ // 奇數(shù)
dp[i] = dp[(i - 1) / 2] + 1;
}
}
// dp數(shù)組即為所求
return dp;
}
};
方法三：卑鄙的異鄉(xiāng)人着帽，巧妙的動態(tài)規(guī)劃
思路
-
這里用到了兩個位運算操作：
-
x & 1：用于判斷奇偶性 -
x & (x-1)：用于刪除二進(jìn)制右數(shù)第一個
原理證明1：
和
做按位與，當(dāng)
原理證明2：
做按位與歉备。假設(shè)
的形式傅是。則
，右數(shù)第一個
-
使用位運算
x & 1书闸，我們可以替換方法一和方法二中尼变，判斷奇偶的操作。即將所有的x % 2替換為x & 1浆劲。但需要注意的是嫌术，位運算的優(yōu)先級較低，判斷時需要加括號：(x & 1) == 0使用位運算
x & (x-1)牌借，我們可以優(yōu)化方法一中的循環(huán)條件度气，每次刪除最右側(cè)的1，直到數(shù)字變?yōu)?膨报。使用位運算
x & (x-1)磷籍，我們還可以優(yōu)化方法二中的動態(tài)規(guī)劃。由于該位運算的操作效果是刪除二進(jìn)制右數(shù)第一個比原結(jié)果
dp[x] = dp[y] + 1-
狀態(tài)定義:
-
-
-
狀態(tài)轉(zhuǎn)移:
-
當(dāng)
-
當(dāng)
dp[i] = dp[i & i - 1)] + 1
-
當(dāng)
-
轉(zhuǎn)移方程：
-
初始狀態(tài):
-
-
-
返回值:
- 返回
- 返回
復(fù)雜度分析
時間復(fù)雜度
空間復(fù)雜度
快樂小視頻
具體代碼
- 方法一優(yōu)化
class Solution {
public:
// 搞一個新的函數(shù)拟烫，計算數(shù)字num二進(jìn)制表示有幾個1。
int trans2bit(int num){
int ans = 0;
// 直到num位0迄本，才退出循環(huán)
while(num > 0){
// num不為零硕淑，說明至少還有一個1
ans++;
// 刪去num最右側(cè)的1
num &= num - 1;
}
// 返回二進(jìn)制表示時，1的個數(shù)
return ans;
}
vector<int> countBits(int num) {
vector<int> ans(num + 1);
// 0的結(jié)果就是0嘉赎，因此從1開始循環(huán)
for(int i = 1; i <= num; i++){
ans[i] = trans2bit(i);
}
return ans;
}
};
- 方法二優(yōu)化
class Solution {
public:
vector<int> countBits(int num) {
// 預(yù)先開好空間
vector<int> dp(num + 1);
// 同樣不需要從0開始置媳，因為dp[0] = 0
for(int i = 1; i <= num; i++){
// 轉(zhuǎn)移方程：
dp[i] = dp[i & (i - 1)] + 1;
}
// dp數(shù)組即為所求
return dp;
}
};
