Esta es la pregunta. Dado un entero n, devuelve una matriz ans de longitud n + 1 tal que para cada i (0 <= i <= n), ans[i] es el número de 1 en la representación binaria de i.
https://leetcode.com/problems/counting-bits/
Y esta es mi solución a continuación. Si la entrada es 2, la salida esperada debería ser [0,1,1] pero sigo obteniendo [0,2,2]. ¿¿¿Porqué es eso???
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));Estás haciendo demasiado trabajo.
Supongamos que b es la mayor potencia de 2 correspondiente al primer bit en i . Evidentemente, i tiene exactamente un 1 más en su representación binaria que i - b . Pero como está generando los recuentos en orden, ya ha calculado cuántos 1 hay en i - b .
El único truco es cómo averiguar qué es b . Y para hacer eso, usamos otra técnica iterativa: a medida que enumera números, b cambia exactamente en el momento en que i se convierte en el doble del valor anterior de 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));Esta técnica suele denominarse "programación dinámica". En esencia, toma una definición recursiva y la calcula de abajo hacia arriba: en lugar de comenzar en el argumento deseado y volver al caso base, comienza en la base y luego calcula cada valor intermedio que se necesitará hasta que alcance el objetivo. . En este caso, se necesitan todos los valores intermedios, lo que nos evita tener que pensar en cómo calcular solo el número mínimo de valores intermedios necesarios.
usar piso():
sum += Math.floor(value%2); value = Math.floor(value/2);Supongo que su algoritmo funciona para algún lenguaje escrito donde la división de enteros da como resultado números enteros
Piénsalo de esta manera: si sabes cuántos unidades hay en un número X , inmediatamente sabrás cuántas unidades hay en X*2 (el mismo) y X*2+1 (uno más). Dado que está procesando números en orden, puede empujar ambos recuentos derivados al resultado y pasar al siguiente número:
let b = [0, 1] for (let i = 1; i <= N / 2; i++) { b.push(b[i]) b.push(b[i] + 1) }Dado que empujamos dos números a la vez, el resultado será único incluso para N, luego debe sacar el último número.