Estoy viendo el problema 2246 de LeetCode. Ruta más larga con diferentes caracteres adyacentes :
Se le proporciona un árbol (es decir, un gráfico conectado no dirigido que no tiene ciclos) enraizado en el nodo 0 que consta de n nodos numerados de 0 a n - 1. El árbol está representado por una matriz padre indexada en 0 de tamaño n, donde padre [i] es el padre del nodo i. Dado que el nodo 0 es la raíz, parent[0] == -1.
También recibe una cadena s de longitud n, donde s[i] es el carácter asignado al nodo i.
Devuelve la longitud de la ruta más larga del árbol de modo que ningún par de nodos adyacentes en la ruta tenga asignado el mismo carácter.
Este es mi código:
function longestPath(parent: number[], s: string): number { const childrenMap: Record<number, number[]> = {} for (let node = 0; node < parent.length; node++) { const parentNode = parent[node] childrenMap[parentNode] = childrenMap[parentNode] ?? [] childrenMap[parentNode].push(node) } let max = 0 const dfs = (node = 0, parentNode = -1): number => { if (s[node] === s[parentNode]) { max = Math.max(max, dfs(node, -1)) return 0 } const [a = 0, b = 0] = (childrenMap[node] ?? []).map((child) => dfs(child, node)) .sort((la, lb) => lb - la) max = Math.max(max, 1 + a + b) return a + 1 } dfs() return max } console.log( longestPath( [-1, 56, 10, 79, 52, 0, 37, 39, 127, 125, 116, 52, 95, 131, 105, 55, 55, 52, 87, 35, 43, 130, 87, 103, 8, 73, 8, 116, 4, 43, 60, 104, 116, 118, 78, 9, 133, 139, 7, 127, 96, 28, 52, 79, 78, 36, 102, 134, 100, 104, 47, 127, 129, 77, 121, 133, 10, 58, 104, 55, 69, 73, 107, 9, 139, 79, 52, 72, 130, 78, 112, 43, 14, 4, 120, 9, 139, 118, 52, 52, 73, 82, 79, 58, 121, 80, 139, 10, 25, 74, 10, 123, 134, 112, 40, 80, 108, 128, 5, 52, 43, 31, 10, 42, 79, 139, 86, 58, 3, 118, 117, 21, 4, 79, 45, 26, 5, 122, 102, 13, 88, 139, 108, 118, 116, 10, 58, 32, 80, 125, 121, 105, 116, 104, 82, 131, 39, 10, 126, 125], 'vodpyvpjmogqvwnibqasbulkfbfugvtlpdtsmydrbrekavkhifoypepbcnzpmasbnlrfqgdhnmvhldsrogjsntummchcftzrnycichziopmphfqwqdsihoywdpqqkyvzrhbqorwrkmns', ), )Produce 13, pero el resultado esperado es 17.
cuando reemplazo
max = Math.max(max, dfs(node, -1))con
max = Math.max(dfs(node, -1), max)la respuesta será correcta (17). No puedo notar la diferencia... ¿Qué pasa?
Su dfs cambia max en dos lugares:
max = Math.max( max, dfs(node, -1), ) ... max = Math.max(max, 1 + a + b) return a + 1 Entonces, el orden en el que llama a dfs como argumento para Math.max puede afectar las cosas:
dfs primero, cambiará max y el segundo argumento pasado a Math.max será el valor cambiado, por lo que se comparará con el valor correcto que fue cambiado por las llamadas recursivas de dfs .dfs en segundo lugar, copiará max , llamará a dfs y luego lo comparará con el antiguo max , con el valor que tenía antes de la llamada recursiva.Solución:
Lo mejor que puede hacer es no mutar el estado externo a dfs : haga que dfs devuelva lo que necesita y use ese valor devuelto, no confíe en una variable externa. Parece que ya está devolviendo algo de dfs , por lo que no debería ser demasiado difícil deshacerse de la mutación de max .
Eso puede ser complicado en algunos casos (pero no en el tuyo), en esos casos al menos no pongas la llamada recursiva como parámetro. Hazlo asi:
const dfsResult = dfs(node, -1) max = Math.max(max, dfsResult)