力扣算法：比特位计数

力扣算法：比特位计数

• 一、比特位计数
• • 1、问题
  • 2、思路
  • 3、代码
  • 4、时间与空间复杂度
• 备注

一、比特位计数

1、问题

2、思路

思路一：

1. 计算一个“非负整数n的二进制数”中所包含1的数目：

• 任一个“非负整数n的二进制数”，每次在经过式子n&(n-1)时，最右边的1会被消除掉。
• 当经过k次n&(n-1)，“非负整数n的二进制数”全部会变为0。
• 此时的k 即为“非负整数n的二进制数”中1的数目。

2. 建立一个循环，计算 0 ≤ n ≤ num中，每个数字n当中1的数目。

举例，计算一个“非负整数n的二进制数”中所包含1的数目：

思路二：

1. 循环遍历0 ≤ i ≤ num 范围中的每个数字 i。
2. 将每个 i 先转化为二进制数，然后将二进制数转化为字符串，最后统计字符串中的“1”的数目返回。

3、代码

#coding:utf-8
from typing import List
class Solution:def countBits1(self, n1: int) -> List[int]:def count_ones(i):count = 0while i:i = i&(i-1)count += 1return countreturn [count_ones(i) for i in range(n1+1)]def countBits2(self, n2: int) -> List[int]:return [str(bin(i)).count("1") for i in range(n2+1)]if __name__ == "__main__":sl = Solution()print(sl.countBits1(5))print(sl.countBits2(5))

4、时间与空间复杂度

思路一：

时间复杂度：O(nlogn)
对从 0 到 n 的每个整数计算「一比特数」，对每个整数计算「一比特数」的时间都不会超过 O(log⁡n)

空间复杂度：O(1)

思路二：

时间复杂度：O(n)
对从 0 到 n 的每个整数计算二进制中包含1的数目。

空间复杂度：O(1)

备注

1、问题转载：
LeetCode
https://leetcode-cn.com/problems/counting-bits

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！