目錄
一、題目
二、示例
三、思路
四、代碼
一、題目
給定一個非負整數 num，對于 0 ≤ i ≤ num 范圍中的每個數字 i ，計算其二進制數中的 1 的數目并將它們作為陣列回傳，
二、示例
示例 1:
輸入: 2
輸出: [0,1,1]
示例 2:
輸入: 5
輸出: [0,1,1,2,1,2]
進階:
- 給出時間復雜度為O(n*sizeof(integer))的解答非常容易，但你可以在線性時間O(n)內用一趟掃描做到嗎？
- 要求演算法的空間復雜度為O(n)，
- 你能進一步完善解法嗎？要求在C++或任何其他語言中不使用任何內置函式（如 C++ 中的 __builtin_popcount）來執行此操作，
三、思路
1、內置函式暴力法
一共只需要兩個步驟：
十進制轉換二進制 --> 計算數字 1 的個數
2、非內置函式暴力法
首先，先補充一個知識：十進制如何轉換成二進制？
以數字 14 為例：藍色為除數，右邊紅色數字為余數
數字 14 的二進制應為右邊余數倒著寫，即 1110
那么，本題為求其二進制中數字 1 的個數，那么直接求右邊余數中數字 1 的個數即可，
3、
對于所有的數字，只有兩類：
奇數：二進制表示中，奇數一定比前面那個偶數多一個 1，因為多的就是最低位的 1，
舉例：
0 = 0 1 = 1
2 = 10 3 = 11
偶數：二進制表示中，偶數中 1 的個數一定和除以 2 之后的那個數一樣多，因為最低位是 0，除以 2 就是右移一位，也就是把那個 0 抹掉而已，所以 1 的個數是不變的，
舉例：
2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
另外，0 的 1 個數為 0，于是就可以根據奇偶性開始遍歷計算了，
此方法參考于 https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/
四、代碼
1、內置函式暴力計演算法
class Solution:
def countBits(self, num: int):
"""
:param num: int
:return: List[int]
"""
ans = []
for i in range(num + 1):
bin_num = format(i, 'b')
ans.append(str(bin_num).count('1'))
return ans
if __name__ == '__main__':
n = 5
s = Solution()
ans = s.countBits(n)
print(ans)2、非內置函式暴力計演算法
class Solution:
def countBits(self, num: int):
"""
:param num: int
:return: List[int]
"""
ans = [0]
# 十進制轉換為二進制后數字1的個數
def numbits(num):
counts = 0 # 數字1的個數
while num != 0:
if num % 2 == 1:
counts += 1
num = num // 2
return counts
for i in range(1, num + 1):
ans.append(numbits(i))
return ans
if __name__ == '__main__':
n = 5
s = Solution()
ans = s.countBits(n)
print(ans)3、
class Solution:
def countBits(self, num: int):
"""
:param num: int
:return: List[int]
"""
ans = [0]
for i in range(1, num + 1):
if i % 2 == 1: # 奇數
ans.append(ans[i - 1] + 1)
else: # 偶數
ans.append(ans[i // 2])
return ans
if __name__ == '__main__':
n = 5
s = Solution()
ans = s.countBits(n)
print(ans)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/265922.html
標籤：python