[LeetCode] Counting Bits

cyixlq 發(fā)布于2019-08-14 15:47 / 3035人閱讀

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

應(yīng)用公式f[i] = f[i/2] + (i%2);
并優(yōu)化此公式為f[i] = f[i>>2] + (i&1)，減少計(jì)算時(shí)間。

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云服務(wù)器云服務(wù)器 Counting Bits LeetCode bits 服務(wù)器擴(kuò)展

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66012.html

相關(guān)文章

leetcode 338. Counting Bits

摘要：題目要求思路和代碼這里除了暴力的計(jì)算每個(gè)數(shù)字中含有多少個(gè)，我們可以使用動(dòng)態(tài)規(guī)劃的方法來計(jì)算中有幾個(gè)。還有一種等價(jià)的思路是第位的的個(gè)數(shù)或是加上位構(gòu)成的數(shù)字的的個(gè)數(shù)。題目要求 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 評(píng)論0 收藏0
LeetCode[191] Number of 1 Bits

摘要：依次移位復(fù)雜度思路依次移動(dòng)位數(shù)進(jìn)行計(jì)算。代碼利用性質(zhì)復(fù)雜度，思路代碼 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 評(píng)論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 評(píng)論0 收藏0
大廠算法面試之leetcode精講9.位運(yùn)算

摘要：空間復(fù)雜度方法是否為最大的冪的約數(shù)思路最大的的冪為，判斷是否是的約數(shù)即可。復(fù)雜度時(shí)間復(fù)雜度，一個(gè)整數(shù)統(tǒng)計(jì)二進(jìn)制的復(fù)雜度，最壞的情況下是。大廠算法面試之leetcode精講9.位運(yùn)算視頻教程（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)目錄：1.開篇介紹2.時(shí)間空間復(fù)雜度3.動(dòng)態(tài)規(guī)劃4.貪心5.二分查找6.深度優(yōu)先&廣度優(yōu)先7.雙指針...

番茄西紅柿 2021-11-29 10:50 評(píng)論0 收藏2637
[Leetcode] Reverse Bits 反轉(zhuǎn)位

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

notebin 2019-08-14 16:10 評(píng)論0 收藏0