leetcode Counting Bits

leetcode Counting Bits

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.

题目地址:leetcode Counting Bits

题意:给定一个数num,求0~num中每个数的1的个数

思路:

方法一

想一想,当一个数为2的整数幂的时候,1的个数为1,比如2(10) 和4(100),8(1000)

在这之后就是前一个序列的数+1 比如 9(1001) = 1(1) + 8 (1) = 2

就是把一个数分解为小于它的最大2的整数幂 + x

C++

Java

Python

 

方法二

倒过来想,一个数 * 2 就是把它的二进制全部左移一位,也就是说 1的个数是相等的。

那么我们可以利用这个结论来做。

res[i /2] 然后看看最低位是否为1即可(上面*2一定是偶数,这边比如15和14除以2都是7,但是15时通过7左移一位并且+1得到,14则是直接左移)

所以res[i] = res[i >>1] + (i&1)

 

C++

Java

Python

 

 

本题是leetcode 338  Counting Bits题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Counting Bits
本文地址:https://www.hrwhisper.me/leetcode-counting-bits/

您的支持将鼓励我继续创作!

Leetcode , , , , . permalink.

5 thoughts on “leetcode Counting Bits

Leave a Reply

Your email address will not be published. Required fields are marked *