计数位的描述如下:
给定一个整数 n,返回一个数组 ans 长度 n 1 这样对于每个 i (0
例如:
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; }
时间和空间复杂度
对设置的位进行计数有css“> 登录 时间复杂度(在最坏的情况下,当所有位都已设置时,循环将运行 binarynumber 中的位数 — 数字的二进制表示形式的位数 n 是 登录 ).
然而我们也这样做 n 次,所以总的来说,时间复杂度为 o(n log n) .
空间复杂度为 o(n) 随着结果数组对空间的需求增加 n 增加。
接下来,我们将看看反向位。在那之前,祝您编码愉快。