LeetCode Top100:比特位計(jì)數(shù)
給你一個整數(shù) n ,對于 0 <= i <= n 中的每個 i ,計(jì)算其二進(jìn)制表示中 1 的個數(shù) ,返回一個長度為 n + 1 的數(shù)組 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
提示:
0 <= n <= 105
實(shí)現(xiàn):
可以使用動態(tài)規(guī)劃的思想解決此問題。設(shè)dp[i]表示i的二進(jìn)制表示中1的個數(shù),那么有以下狀態(tài)轉(zhuǎn)移方程:
- 當(dāng)i為偶數(shù)時,dp[i]=dp[i//2]
- 當(dāng)i為奇數(shù)時,dp[i]=dp[i-1]+1
因?yàn)榕紨?shù)i的二進(jìn)制表示中,其最低位是0,所以將i向右移一位(相當(dāng)于除以2),其二進(jìn)制表示中1的個數(shù)不變,即dp[i]=dp[i//2]。 而當(dāng)i為奇數(shù)時,其二進(jìn)制表示中最低位為1,所以將i-1(相當(dāng)于將其最低位的1變?yōu)?),其二進(jìn)制表示中1的個數(shù)會減少1,即dp[i]=dp[i-1]+1。
以下是Python的實(shí)現(xiàn)代碼:
class Solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n+1)
for i in range(1, n+1):
if i % 2 == 0:
dp[i] = dp[i//2]
else:
dp[i] = dp[i-1] + 1
return dp
時間復(fù)雜度:O(n)
浙公網(wǎng)安備 33010602011771號