題目
給定一個整數(shù) n 灼狰，對于 0 ≤ i ≤ n 中的每個 i ，計算其二進(jìn)制表示中 1 的個數(shù)并把它們返回浮禾。
例如：
給定一個整數(shù)：n = 2交胚，返回結(jié)果：[0, 1, 1]
給定一個整數(shù)：n = 5，返回結(jié)果：[0, 1, 1, 2, 1, 2]
實(shí)現(xiàn)思路1
- 設(shè)置一個列表res盈电，用于存儲 0 ≤ i ≤ n 中的每個 i 對應(yīng)二進(jìn)制數(shù)中1的個數(shù)
- 遍歷1到n+1蝴簇，利用 Python 里的內(nèi)置函數(shù)
bin()把 i 轉(zhuǎn)換為字符串格式的二進(jìn)制數(shù)，比如8轉(zhuǎn)為二進(jìn)制數(shù)為0b1000 - 利用 Python 里的內(nèi)置函數(shù)
count()統(tǒng)計字符串中出現(xiàn)1的次數(shù)匆帚，并依次把出現(xiàn)次數(shù)添加到res中熬词，最后進(jìn)行返回
代碼實(shí)現(xiàn)
def countBits(n):
res = [0]
for i in range(1, n + 1):
res.append(bin(i).count("1"))
return res
實(shí)現(xiàn)思路2
- 針對二進(jìn)制數(shù)，左移一位吸重，代表乘以2互拾；右移一位，代表除以2嚎幸；
- 對于偶數(shù) i 颜矿，其二進(jìn)制數(shù)最低位肯定為0，所以其二進(jìn)制數(shù)整體向右移動一位后并不會影響1的個數(shù)嫉晶。其二進(jìn)制中1的個數(shù)骑疆，也就肯定等于
i // 2
所對應(yīng)的二進(jìn)制數(shù)中1的個數(shù)田篇； - 對于奇數(shù) i ，其二進(jìn)制數(shù)最低位肯定為1箍铭，其二進(jìn)制中1的個數(shù)泊柬，也就肯定等于前一個數(shù)中1的個數(shù)再加1
代碼實(shí)現(xiàn)
def countBits(n):
res = [0]
for i in range(1, n + 1):
if i % 2 != 0:
res.append(res[i - 1] + 1)
else:
res.append(res[i // 2])
return res
實(shí)現(xiàn)思路3
我們還可以利用 Python 里的 位運(yùn)算符 來實(shí)現(xiàn)，其大致與實(shí)現(xiàn)思路2的邏輯一致诈火，但通過位運(yùn)算符兽赁，我們可以讓代碼更簡化。
-
&按位與運(yùn)算符：參與運(yùn)算的兩個二進(jìn)制數(shù), 如果兩個相應(yīng)位都為1, 則該位的結(jié)果為1, 否則為0柄瑰； -
>>右移動運(yùn)算符：如i >> 1闸氮，表示將 i 對應(yīng)的二進(jìn)制數(shù)整體右移一位，其實(shí)也就相當(dāng)于i // 2 - 如果 i 為偶數(shù)教沾，其二進(jìn)制數(shù)最低位肯定為0蒲跨，所以 i & 1 的結(jié)果必為 0；
- 如果 i 為奇數(shù)授翻，其二進(jìn)制數(shù)最低位肯定為1或悲，所以 i & 1 的結(jié)果必為 1。
代碼實(shí)現(xiàn)
def countBits(n):
res = [0]
for i in range(1, n + 1):
res.append(res[i >> 1] + (i & 1))
return res
更多Python編程題堪唐，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
