338. 比特位计数-阿里云开发者社区

338. 比特位计数

2022-04-30 72

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

一、题目描述：

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

示例 1：

输入：2

输出：[0,1,1]

示例 2：

输入：5

输出：[0,1,1,2,1,2]

二、思路分析：

思路一：

先考虑将一个数转成二进制数，可以使用m % 2来计算。再考虑将这个数中包含出现1的次数记录下来。完成一个数记录1次数后，再使用一个循环从0开始到输入的数，在循环中记录每个数值出现的次数。

网络异常，图片无法展示

思路二：

emmm，想不出来其他方法。看了官网的没看明白。

三、AC 代码：

方法一：

function countBits(num: number): number[] {
  let arr = [];
  let j;
  for (let i = 0; i <= num; i++) {
    j = 0;
    let m = i;
    while (m > 0) { // 一个数记录1出现的次数
      if (m % 2 === 1) j++;
      m = Math.floor(m / 2);
    }
    arr.push(j);
  }
  return arr;
}

方法二：

function countBits(num: number): number[] {
  let bits = new Array(num + 1).fill(0);
  let highBit = 1;
  for (let i = 1; i <= num; i++) {
    if (highBit * 2 === i) highBit = i;
    bits[i] = bits[i - highBit] + 1;
  }
  return bits;
}

四、总结：

此题主要考察二进制统计。

题目来源：leetcode。

作者：ClyingDeng

链接：https://juejin.cn/post/6935320936451145736

来源：稀土掘金

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。