Este es uno de los problemas fáciles en LeeteCode. solución Pero mi pregunta no es realmente sobre el problema, el código a continuación itera a través de una matriz 2d como esta
[ [1, 1, 0, 0, 0], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 1, 1, 1], ] El problema, no lo entiendo, es por qué j <= x mientras que i < y ¿no va j a una iteración adicional? Habría pensado que j < sería la forma correcta pero no lo es
var kWeakestRows = function(M, K) { let y = M.length, x = M[0].length, vis = new Uint8Array(y), ans = [] for (let j = 0; j <= x; j++) for (let i = 0; i < y; i++) { if (!vis[i] && !M[i][j]) ans.push(i), vis[i]++ if (ans.length === K) return ans } };Es un truco para simplificar la escritura de la condición que comprueba cuántos soldados hay en fila.
Simplifica el código (como en: la cantidad de caracteres que escribe), ciertamente no simplifica la comprensión, y probablemente debería probar cómo se ve afectado el rendimiento.
Notarás que cada fila tiene x celdas, pero el "número de soldados" de una fila puede ser cualquier valor en [0, x] , y eso es x+1 valores posibles.
Escribamos una función más simple que solo verifique qué filas tienen "como máximo j soldados":
func checkAtMost(M, j) { let y = M.length, x = M[0].length; // if you want to avoid accessing out of bound cells, you have to // compare 'j' to 'x' : for (let i = 0; i <= y; j++) if (j >= x || !M[i][j]) { console.log("row "+i+" has at most "+j+" soldiers"); } }pero las especificaciones de javascript dicen:
undefinedundefined se convierte en false cuando se usa en una expresión booleana así que en realidad, cuando j >= x se evalúa como true : M[i][j] == undefined , y !M[i][j] también se evalúa como true .
Por lo tanto, la función anterior es equivalente a:
func checkAtMost(M, j) { let y = M.length; // who cares about bounds ? we're writing javascript ! for (let i = 0; i <= y; i++) if (!M[i][j]) { console.log("row "+i+" has at most "+j+" soldiers"); } } y esa es una manera de hacer que funcione para cualquiera de j in [0,x] (valores x+1 ) aunque cada fila tenga solo x celdas.
tenga en cuenta que la solución de python sugerida tiene la comprobación de límites:
if not vis[i] and (j == x or not M[i][j]): ...Creo que lo tengo. j es el índice de un elemento a lo largo de una fila , por lo que cuando j llega a x , es decir, todos los elementos de la matriz se han iterado, se debería haber encontrado la respuesta.
Si ha seguido el algoritmo mencionado, sabe que itera sobre cada fila para cada columna, en este orden . Entonces, el algoritmo termina con la columna final e itera sobre cada índice de fila. Cuando termina esta iteración, j pasa de x-1 a x . Dado que se garantiza que K es igual o menor que y , ans.length definitivamente será K en este punto, y la declaración de retorno se ejecutará.
j alcanzará el valor de x si y solo si K es igual al número de filas en la matriz, es decir, el número máximo posible de salidas que se pueden dar para la matriz dada.
Enfoque alternativo:
Puede calcular el recuento de soldados para cada fila y luego ordenar las filas por el recuento de soldados y resolver los empates según el índice.
var kWeakestRows = function (M, K) { const soldiers = M.map((row, i) => [row.reduce((total, r) => total + r), i]); return soldiers .sort(([aCnt, aIdx], [bCnt, bIdx]) => { if (aCnt === bCnt) return aIdx - bIdx; else return aCnt - bCnt; }) .map(([, i]) => i) .slice(0, K); }; kWeakestRows( [ [1, 1, 0, 0, 0], [1, 1, 1, 1, 0], [1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 1, 1, 1, 1], ], 3 );