[LeetCode] Counting Bits

cyixlq 發布于2019-08-14 15:47 / 3033人閱讀

Problem

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

For num = 5 you should return [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.

Hint

You should make use of what you have produced already.
Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
Or does the odd/even status of the number help you in calculating the number of 1s?

Note

應用公式f[i] = f[i/2] + (i%2);
并優化此公式為f[i] = f[i>>2] + (i&1)，減少計算時間。

Solution

public class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num+1];
        for (int i = 1; i <= num; i++) dp[i] = dp[i>>1] + (i&1);
        return dp;
    }
}

GPU云服務器云服務器 Counting Bits LeetCode bits 服務器擴展

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66012.html

leetcode 338. Counting Bits

摘要：題目要求思路和代碼這里除了暴力的計算每個數字中含有多少個，我們可以使用動態規劃的方法來計算中有幾個。還有一種等價的思路是第位的的個數或是加上位構成的數字的的個數。題目要求 Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number ...

ShevaKuilin 2019-08-16 11:06 評論0 收藏0
LeetCode[191] Number of 1 Bits

摘要：依次移位復雜度思路依次移動位數進行計算。代碼利用性質復雜度，思路代碼 LeetCode[191] Number of 1 Bits Write a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Fo...

Scliang 2019-08-14 15:00 評論0 收藏0
[LeetCode] 191. Number of 1 Bits

Problem Number of 1 BitsWrite a function that takes an unsigned integer and returns the number of ’1 bits it has (also known as the Hamming weight). Example For example, the 32-bit integer 11 has bina...

gitmilk 2019-08-16 12:31 評論0 收藏0
大廠算法面試之leetcode精講9.位運算

摘要：空間復雜度方法是否為最大的冪的約數思路最大的的冪為，判斷是否是的約數即可。復雜度時間復雜度，一個整數統計二進制的復雜度，最壞的情況下是。大廠算法面試之leetcode精講9.位運算視頻教程（高效學習）:點擊學習目錄：1.開篇介紹2.時間空間復雜度3.動態規劃4.貪心5.二分查找6.深度優先&廣度優先7.雙指針...

番茄西紅柿 2021-11-29 10:50 評論0 收藏2637
[Leetcode] Reverse Bits 反轉位

摘要：移位法復雜度時間空間思路最簡單的做法，原數不斷右移取出最低位，賦給新數的最低位后新數再不斷左移。代碼分段相或法復雜度時間空間思路標準的源碼。更好的優化方法是將其按照分成段存儲，節省空間。 Reverse Bits Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (r...

notebin 2019-08-14 16:10 評論0 收藏0