LeetCode 338. 比特位计数

Stella981
• 阅读 708

原文链接: LeetCode 338. 比特位计数

https://leetcode-cn.com/problems/counting-bits/

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ,计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]
示例 2:

输入: 5
输出: [0,1,1,2,1,2]
进阶:

给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗?
要求算法的空间复杂度为 O(n)。
你能进一步完善解法吗?要求在 C++ 或任何其他语言中不使用任何内置函数(如 C++ 中的 __builtin_popcount)来执行此操作。

使用两种dp实现

方法一:

分为技术和偶数两种情况,

初始化dp[0] = 0

奇数时末尾为1, dp[i] = dp[i-1] + 1

偶数时末尾为0, dp[i[ = dp[i>>1]

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
  let dp = Array(num + 1).fill(0)
  for (let i = 1; i <= num; i++)
    (i & 1) ? dp[i] = dp[i - 1] + 1 : dp[i] = dp[i >> 1]
  return dp
};

方法二:

通过构造数字的形式, 按照最高位1的位置来进行dp

初始化dp[0] = 0

对于最高位第 i 位的数字为1时, 对于 j (0<=j<i) 来说 dp[ j + (1<<i) ] = dp[j] + 1 

注意i从0开始, 表示第0位为1即是数字1

j每次从0开始直到 (1<<i - 1)结束, 并且需要判断 j + (1<<i) 是否已经超出范围

j + (1<<i) 的取值范围 为 [1000.... , min(111111..., num)] 的双闭区间

/**
 * @param {number} num
 * @return {number[]}
 */
var countBits = function(num) {
  let dp = Array(num + 1).fill(0)
  for (let i = 0; (1 << i) <= num; i++) {
    for (let j = 0; j < (1 << i) && j + (1 << i) <= num; j++) {
      dp[ j + (1 << i)] = dp[j] + 1
    }
  }

  return dp
};
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
5个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Stella981 Stella981
3年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Stella981 Stella981
3年前
LeetCode 1009. 十进制整数的反码
原文链接: LeetCode1009.十进制整数的反码(https://my.oschina.net/ahaoboy/blog/3118044)https://leetcodecn.com/problems/complementofbase10integer/(https://www.oschina.net/action/GoToL
Stella981 Stella981
3年前
LeetCode 169. 求众数
原文链接: LeetCode169.求众数(https://my.oschina.net/ahaoboy/blog/3118038)https://leetcodecn.com/problems/majorityelement/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F
Stella981 Stella981
3年前
LeetCode 72. 编辑距离
原文链接: LeetCode72.编辑距离(https://my.oschina.net/ahaoboy/blog/3113850)https://leetcodecn.com/problems/editdistance/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2F
Stella981 Stella981
3年前
LeetCode 生命游戏,不用新数组的方式
原文链接: LeetCode生命游戏,不用新数组的方式(https://my.oschina.net/ahaoboy/blog/4958278)https://leetcodecn.com/problems/gameoflife/(https://www.oschina.net/action/GoToLink?urlhttps%3A%2
Stella981 Stella981
3年前
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法
Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法参考文章:(1)Google地球出现“无法连接到登录服务器(错误代码:c00a0194)”解决方法(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.codeprj.com%2Fblo
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这