「每日LeetCode」2021年6月8日
本文最后更新于:2023年3月19日 晚上
- 比特位计数
338. 比特位计数
给定一个非负整数 num。对于 0 ≤ i ≤ num **范围中的每个数字 **i **,计算其二进制数中的 1 的数目并将它们作为数组返回。
**示例 1:
1 |
|
示例 2:
1 |
|
进阶:
- 给出时间复杂度为O(n*sizeof(integer))**的解答非常容易。但你可以在线性时间O(n)**内用一趟扫描做到吗?
- 要求算法的空间复杂度为**O(n)**。
- 你能进一步完善解法吗?要求在 C++或任何其他语言中不使用任何内置函数(如 C++ 中的 __builtin_popcount)来执行此操作。
思路
一种暴力转二进制字符串然后对 1 计数解。
另外一种找规律:如果 i 为偶数,说明只是上一个偶数向左移动了一位,1 的个数不变;如果 i 为奇数,则相当于上一个偶数加上一个 1。
解答
1 |
|
1 |
|
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!