這就是問題。給定一個整數 n，回傳一個長度為 n 1 的陣列 ans，使得對于每個 i (0 <= i <= n)，ans[i] 是 i 的二進制表示中 1 的數量。
https://leetcode.com/problems/counting-bits/
這是我下面的解決方案。如果輸入為 2，則預期輸出應為 [0,1,1]，但我不斷得到 [0,2,2]。這是為什么？？？
var countBits = function(n) {
//n=3. [0,1,2,3]
var arr=[0];
for (var i=1; i<=n; i ){
var sum = 0;
var value = i;
while(value != 0){
sum = value%2;
value /= 2;
}
arr.push(sum);
}
return arr;
};
console.log(countBits(3));uj5u.com熱心網友回復：
你做的作業太多了。
假設b是 2 的最大冪，對應于 中的第一位i。顯然，i它1的二進制表示形式比i - b. 1但是由于您是按順序生成計數，因此您已經計算出s 中有多少個s i - b。
唯一的訣竅是如何弄清楚是什么b。為此，我們使用了另一種迭代技術：當您列出數字時，b恰好在i變為 之前值兩倍的那一刻發生變化b：
const countBits = function(n) {
let arr = [0], bit = 1;
for (let i = 1; i <= n; i ){
if (i == bit bit) bit = bit;
arr.push(arr[i - bit] 1);
}
return arr;
};
console.log(countBits(20));這種技術通常被稱為“動態編程”。本質上，它采用遞回定義并自下而上計算它：它不是從所需的引數開始并遞回到基本情況，而是從基本情況開始，然后計算每個中間值，直到達到目標為止. 在這種情況下，需要所有中間值，從而使我們不必考慮如何僅計算所需的最小中間值數量。
uj5u.com熱心網友回復：
使用地板（）：
sum = Math.floor(value%2);
value = Math.floor(value/2);
我猜你的演算法適用于某些型別的語言，其中整數除法導致整數
uj5u.com熱心網友回復：
可以這樣想：如果您知道一個數字中有多少個X，那么您立即知道X*2（相同的）和X*2 1（多一個）中有多少個。由于您正在按順序處理數字，因此您可以將兩個派生計數推送到結果并跳到下一個數字：
let b = [0, 1]
for (let i = 1; i <= N / 2; i ) {
b.push(b[i])
b.push(b[i] 1)
}
由于我們一次推送兩個數字，結果將是偶數 N 的一次，您必須在之后彈出最后一個數字。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/495250.html
標籤：javascript 算法 二进制