LeetCode 338. Counting Bits
Description
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
描述
給定一個(gè)非負(fù)整數(shù) num。對于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i ，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回。
示例 1:
輸入: 2
輸出: [0,1,1]
示例 2:
輸入: 5
輸出: [0,1,1,2,1,2]
進(jìn)階:
給出時(shí)間復(fù)雜度為O(n*sizeof(integer))的解答非常容易。但你可以在線性時(shí)間O(n)內(nèi)用一趟掃描做到嗎？
要求算法的空間復(fù)雜度為O(n)。
你能進(jìn)一步完善解法嗎？要求在C++或任何其他語言中不使用任何內(nèi)置函數(shù)（如 C++ 中的 __builtin_popcount）來執(zhí)行此操作。
思路
- 二進(jìn)制數(shù) 0 到 7 在前面添加一個(gè) 1 構(gòu)成 8 到 15，二進(jìn)制數(shù) 0 到 15 在前面添加一個(gè) 1 構(gòu)成 16 到 31.
- 每 2 ^ i 到 2 ^ (i+1)-1 為一組，前面的數(shù)的 1 的個(gè)數(shù)加一構(gòu)成當(dāng)前組對應(yīng)二進(jìn)制數(shù) 1 的個(gè)數(shù)。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-04-07 11:54:35
# @Last Modified by: 何睿
# @Last Modified time: 2019-04-07 12:22:34
class Solution:
def countBits(self, num: int) -> [int]:
# 結(jié)果數(shù)組
result, count = [0], 1
while count * 2 <= num:
# 從 resut 數(shù)組中索引對應(yīng)的二進(jìn)制數(shù)前面加
# 一個(gè) 1 構(gòu)成范圍從 count 到 count*2 -1 的數(shù)（包括兩端）
for i in range(count, count * 2):
result.append(1 + result[i - count])
count *= 2
# 處理剩下的數(shù)
for i in range(count, num + 1):
result.append(1 + result[i - count])
return result
源代碼文件在 這里 。
?本文首發(fā)于 何睿的博客 ，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留 文章來源 ，作者信息和本聲明.
