当前位置：首页 > 文章列表 > 文章 > 前端 > LeetCode 冥想：计算位数

LeetCode 冥想：计算位数

来源：dev.to 2024-12-28 11:10:02 0浏览收藏

学习知识要善于思考，思考，再思考！今天golang学习网小编就给大家带来《LeetCode 冥想：计算位数》，以下内容主要包含等知识点，如果你正在学习或准备学习文章，就都不要错过本文啦~让我们一起来看看吧，能帮助到你就更好了！

计数位的描述如下：

给定一个整数 n，返回一个数组 ans 长度 n 1 这样对于每个 i (0 <= i <= n), ans[i] 是数字 1 的在的二进制表示中 i.

例如：

input: n = 2
output: [0, 1, 1]

explanation:
0 --> 0
1 --> 1
2 --> 10

或者：

input: n = 5
output: [0, 1, 1, 2, 1, 2]

explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

该问题要求我们获取从 0 到 n 的每个数字的二进制表示形式中 1 的数量。

我想到的第一个解决方案是创建一个长度为 n 1 的数组，用二进制的 0 到 n 的值填充它......

const arr = array.from({ length: n + 1 }, (_, i) => i.tostring(2));

...并将每一位映射到它所具有的 1 位数：

arr.map(j => {
  let result = 0;
  let binarynumber = parseint(j, 2);
  while (binarynumber > 0) {
    binarynumber &= binarynumber - 1;
    result++;
  }
  return result;
});

请注意，在上一个问题中，我们使用了一种技术来计算 1 位的数量（或计算其 汉明权重）——它只是从数字中减去一个较小的值，直到达到0：

let numberof1bits = 0;
while (binarynumber > 0) {
  binarynumber &= binarynumber - 1;
  numberof1bits++;
}

我们可以链接这些方法，总的来说，解决方案如下所示：

function countbits(n: number): number[] {
  return array.from({ length: n + 1 }, (_, i) => i.tostring(2)).map(j => {
    let result = 0;
    let binarynumber = parseint(j, 2);
    while (binarynumber > 0) {
      binarynumber &= binarynumber - 1;
      result++;
    }
    return result;
  });
}

或者，我们可以更明确地编写它，将每个计数推送到结果数组：

function countBits(n: number): number[] {
  let result = [];
  for (let i = 0; i <= n; i++) {
    let binaryNum = parseInt(i.toString(2), 2);
    let count = 0;
    while (binaryNum > 0) {
      binaryNum &= binaryNum - 1;
      count++;
    }
    result.push(count);
  }

  return result;
}

时间和空间复杂度

对设置的位进行计数有 $l o g n 登录n$ 时间复杂度（在最坏的情况下，当所有位都已设置时，循环将运行 binarynumber 中的位数 — 数字的二进制表示形式的位数 $n n$ 是 $l o g n 登录n$ ).
然而我们也这样做 $n n$ 次，所以总的来说，时间复杂度为 $o (n l o g n ） o(n log n)$ .