El Estilo de Vida de Kaue
Enfrentarse a problemas de nivel difícil (Hard) en LeetCode a menudo puede sentirse como chocar contra un muro. Sin embargo, descomponerlos en patrones digeribles —como programación dinámica, backtracking y teoría de grafos— los hace mucho más accesibles.
En esta publicación comparto 7 de los problemas Hard de LeetCode más interesantes que he resuelto en Go. Para que esta guía sea lo más útil posible, he sintetizado las explicaciones centrándome especialmente en la intuición fundamental y la complejidad, facilitando así el salto desde el enunciado del problema hasta el código funcional.
Dados y , devuelve la -ésima secuencia de permutación de los números del al .
Por ejemplo, si , las permutaciones son: "123", "132", "213", "231", "312", "321". Si , la respuesta es "213".
En lugar de generar todas las permutaciones (lo cual sería demasiado lento), podemos usar un enfoque matemático aprovechando los factoriales.
Para dígitos, existen permutaciones en total. Si fijamos el primer dígito, quedan permutaciones de los dígitos restantes. Podemos determinar el primer dígito calculando en qué bloque de permutaciones cae la -ésima permutación. El índice de nuestro siguiente dígito en una lista ordenada de dígitos disponibles será simplemente . Después de elegir un dígito, actualizamos al resto y aplicamos recursión.
import "fmt"
func getPermutation(n int, k int) string {
factorial := 1
digits := []int{}
// Calcular factoriales y poblar el slice de dígitos
for i := 1; i <= n; i++ {
factorial *= i
digits = append(digits, i)
}
return solvePermutation(n-1, k-1, factorial/n, digits)
}
func solvePermutation(n, k, factorial int, digits []int) string {
// Encontrar en qué bloque de permutaciones cae 'k'
index := k / factorial
res := fmt.Sprintf("%d", digits[index])
if n <= 0 {
return res
}
// Actualizar k para el siguiente nivel: k % factorial
// Actualizar factorial para el siguiente nivel: factorial / n
// Eliminar el dígito seleccionado del slice
nextK := k % factorial
nextFactorial := factorial / n
remainingDigits := append(digits[:index], digits[index+1:]...)
res += solvePermutation(n-1, nextK, nextFactorial, remainingDigits)
return res
}
Implementa la coincidencia de expresiones regulares con . (coincide con cualquier carácter individual) y * (coincide con cero o más repeticiones del elemento anterior). La coincidencia debe cubrir toda la cadena de entrada.
Este es un problema clásico de programación dinámica. Podemos usar memoización para evitar cálculos redundantes.
En cualquier combinación dada de caracteres de la cadena s y el patrón p, si el siguiente carácter en el patrón es *, tenemos dos opciones:
s pero permanecer en el * de p para coincidir potencialmente con más caracteres.func isMatch(s string, p string) bool {
sn, pn := len(s), len(p)
memo := make([][]int, sn+1)
for i := range memo {
memo[i] = make([]int, pn+1)
}
return solveRegex(s, p, sn, pn, 0, 0, memo)
}
func solveRegex(s, p string, sn, pn, si, pi int, memo [][]int) bool {
if memo[si][pi] == 1 { return false }
if memo[si][pi] == 2 { return true }
res := false
if si == sn && pi == pn {
res = true
} else if pi+1 < pn && p[pi+1] == '*' {
// Opción A: Cero apariciones
if solveRegex(s, p, sn, pn, si, pi+2, memo) {
res = true
// Opción B: Una o más apariciones (si el carácter actual coincide)
} else if si < sn && (p[pi] == '.' || p[pi] == s[si]) && solveRegex(s, p, sn, pn, si+1, pi, memo) {
res = true
}
} else if si < sn && pi < pn && (p[pi] == '.' || p[pi] == s[si]) {
// Coincidencia normal de caracteres
res = solveRegex(s, p, sn, pn, si+1, pi+1, memo)
}
if res {
memo[si][pi] = 2
} else {
memo[si][pi] = 1
}
return res
}
Dado un árbol binario no vacío, encuentra la suma máxima de un camino. Un camino puede subir o bajar por las conexiones padre-hijo, pero no necesita pasar por la raíz.
Utilizamos búsqueda en profundidad (DFS). En cada nodo, evaluamos dos tipos de caminos:
fromRoot): El camino máximo que comienza en el nodo actual y desciende por una de sus ramas. Un nodo padre puede utilizar este camino.other): El camino máximo contenido íntegramente dentro del subárbol actual (por ejemplo, subiendo desde el hijo izquierdo hasta el nodo actual y bajando hacia el hijo derecho). Este camino está «cerrado» y no puede extenderse hacia arriba hacia un padre.Nuestro máximo global será el mayor de todos los caminos «no extensibles» que encontremos, o bien el camino extensible de la raíz.
import "math"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func maxPathSum(root *TreeNode) int {
fromRoot, other := solveTree(root)
if fromRoot > other {
return fromRoot
}
return other
}
func solveTree(root *TreeNode) (int, int) {
if root == nil {
return math.MinInt, math.MinInt
}
left, otherLeft := solveTree(root.Left)
right, otherRight := solveTree(root.Right)
// Camino extensible (solo puede elegir una rama o detenerse en el nodo)
currentFromRoot := max([]int{
root.Val,
sum([]int{root.Val, left}),
sum([]int{root.Val, right}),
})
// Camino cerrado (puede arquearse sobre el nodo actual o estar completamente dentro de un hijo)
currentOther := max([]int{
left, right, otherLeft, otherRight,
sum([]int{root.Val, left, right}),
})
return currentFromRoot, currentOther
}
func max(s []int) int {
res := math.MinInt
for _, v := range s {
if v > res { res = v }
}
return res
}
func sum(s []int) int {
res := 0
for _, v := range s {
if v == math.MinInt { return math.MinInt }
res += v
}
return res
}
Escribe un programa para resolver un rompecabezas de Sudoku de 9x9. Debes cumplir las reglas estándar del Sudoku (filas, columnas y subcuadrículas de 3x3).
Esto requiere un algoritmo de backtracking (vuelta atrás). Para hacerlo eficiente y evitar errores de tiempo límite excedido (TLE) en LeetCode, optimizamos la búsqueda mediante una heurística: intentar rellenar siempre primero la celda vacía que tenga la menor cantidad de números válidos posibles. Usamos arreglos booleanos para comprobar al instante si un número está disponible en una fila, columna o subcuadrícula de 3x3.
func solveSudoku(board [][]byte) {
var rows, cols [9][9]bool
var boxes [3][3][9]bool
// Poblar el estado inicial
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
idx := board[i][j] - '1'
rows[i][idx], cols[j][idx], boxes[i/3][j/3][idx] = true, true, true
}
}
}
backtrackSudoku(board, &rows, &cols, &boxes)
}
func backtrackSudoku(board [][]byte, rows, cols *[9][9]bool, boxes *[3][3][9]bool) bool {
bestI, bestJ := -1, -1
minOptions := 10 // Empezar por encima del máximo de opciones posibles (9)
// Heurística: encontrar la celda con menos opciones válidas
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] == '.' {
options := 0
for val := 0; val < 9; val++ {
if !rows[i][val] && !cols[j][val] && !boxes[i/3][j/3][val] {
options++
}
}
if options < minOptions {
minOptions = options
bestI, bestJ = i, j
}
}
}
}
// Caso base: no quedan celdas vacías
if bestI == -1 { return true }
// Intentar colocar números válidos en la celda óptima elegida
for val := 0; val < 9; val++ {
if !rows[bestI][val] && !cols[bestJ][val] && !boxes[bestI/3][bestJ/3][val] {
board[bestI][bestJ] = byte(val + '1')
rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = true, true, true
if backtrackSudoku(board, rows, cols, boxes) {
return true
}
// Vuelta atrás (Backtrack)
board[bestI][bestJ] = '.'
rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = false, false, false
}
}
return false
}
Se te da un número entero , que indica que hay cursos etiquetados del al . También se te da un arreglo relations donde relations[i] = [prevCourse, nextCourse] representa una relación de prerrequisito. En un semestre, puedes cursar como máximo asignaturas. Devuelve el número mínimo de semestres necesarios para completar todos los cursos.
Dado que es pequeño (), podemos utilizar búsqueda en anchura (BFS) combinada con máscaras de bits (bitmasks).
Una máscara de bits representa el estado de los cursos que hemos completado. En cada semestre, identificamos todos los cursos disponibles (aquellos cuyos prerrequisitos se cumplen por completo). Si los cursos disponibles superan , debemos iterar a través de todas las combinaciones posibles de tamaño utilizando enumeración de submáscaras. Usamos un mapa added de visitados para evitar volver a visitar las mismas combinaciones.
func minNumberOfSemesters(n int, relations [][]int, k int) int {
// prerequisites[i] es una máscara de bits de los cursos que deben tomarse antes del curso i
prerequisites := make([]int, n)
for _, relation := range relations {
prevCourse := relation[0] - 1
nextCourse := relation[1] - 1
prerequisites[nextCourse] |= 1 << prevCourse
}
// states y costs actúan como una cola BFS
states := []int{0}
costs := []int{0}
added := map[int]bool{0: true}
for cur := 0; ; cur++ {
state := states[cur]
cost := costs[cur]
// Caso base: se han completado todos los cursos
if state == (1<<n)-1 {
return cost
}
// Encontrar todos los cursos disponibles para cursar este semestre
courses := []int{}
next := state
for course := 0; course < n; course++ {
bit := 1 << course
if (state&bit) == 0 && (prerequisites[course]|state) == state {
courses = append(courses, course)
next |= bit
}
}
add := func(next int) {
if added[next] {
return
}
added[next] = true
states = append(states, next)
costs = append(costs, cost+1)
}
// Si podemos tomar todos los cursos disponibles en un semestre, hacerlo
if len(courses) <= k {
add(next)
continue
}
// De lo contrario, explorar todas las combinaciones de tamaño k
var addStates func(next, k, from int)
addStates = func(next, k, from int) {
if k == 0 {
add(next)
return
}
for i := from; i < len(courses); i++ {
addStates(next|(1<<courses[i]), k-1, i+1)
}
}
addStates(state, k, 0)
}
}
Dada una matriz de y un entero , devuelve la suma máxima de un rectángulo en la matriz tal que su suma no sea mayor que .
Podemos comprimir la matriz 2D en un arreglo 1D fijando los límites de las columnas izquierda y derecha. Una vez que tenemos un arreglo 1D que representa las sumas de las filas entre esas columnas, el problema se reduce a encontrar la suma de un subarreglo . Manteniendo una lista ordenada de sumas de prefijos (usando un árbol de búsqueda binaria o una simple inserción en un arreglo ordenado), podemos consultar eficientemente la suma de prefijos más pequeña que satisfaga current_prefix - past_prefix <= k, o bien precalcular una tabla de sumas de prefijos 2D para consultar cualquier subrectángulo en tiempo .
import "math"
func maxSumSubmatrix(matrix [][]int, k int) int {
n := len(matrix)
m := len(matrix[0])
res := math.MinInt
sums := make([][]int, n)
for i := 0; i < n; i++ {
sums[i] = make([]int, m)
}
// Precalcular sumas de prefijos 2D
sums[0][0] = matrix[0][0]
for i := 1; i < n; i++ {
sums[i][0] = matrix[i][0] + sums[i-1][0]
}
for j := 1; j < m; j++ {
sums[0][j] = matrix[0][j] + sums[0][j-1]
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
sums[i][j] = matrix[i][j] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
}
}
// Evaluar todos los subrectángulos posibles mediante inclusión-exclusión
for starti := 0; starti < n; starti++ {
for startj := 0; startj < m; startj++ {
for endi := starti; endi < n; endi++ {
for endj := startj; endj < m; endj++ {
sum := sums[endi][endj]
if starti > 0 {
sum -= sums[starti-1][endj]
}
if startj > 0 {
sum -= sums[endi][startj-1]
}
if starti > 0 && startj > 0 {
sum += sums[starti-1][startj-1]
}
if sum <= k && sum > res {
res = sum
}
}
}
}
}
return res
}
En un grafo dirigido, cada nodo tiene exactamente un padre, excepto el nodo raíz, que no tiene padres. Se añade una arista dirigida adicional. Encuentra la arista que puede eliminarse para que el grafo resultante sea un árbol con raíz válido. Si hay múltiples respuestas, devuelve la última que aparezca en la entrada.
Como se trata de un grafo dirigido, la arista añadida genera uno de estos dos problemas (o ambos):
Primero escaneamos para ver si algún nodo tiene dos padres. Si es así, la arista redundante debe ser una de las dos aristas que apuntan a ese nodo. De lo contrario, la arista adicional forma un ciclo dirigido. Podemos probar las aristas candidatas en orden inverso de entrada y verificar mediante DFS (o Union-Find) si al eliminar la arista candidata queda un árbol con raíz válido en el que los nodos sean alcanzables desde la raíz sin ciclos.
func findRedundantDirectedConnection(edges [][]int) []int {
n := len(edges)
parents := map[int][]int{}
outs := map[int][]int{}
for _, edge := range edges {
src := edge[0] - 1
dst := edge[1] - 1
parents[dst] = append(parents[dst], src)
outs[src] = append(outs[src], dst)
}
roots := map[int]bool{}
bad := -1
for i := 0; i < n; i++ {
if len(parents[i]) == 0 {
roots[i] = true
}
if len(parents[i]) > 1 {
bad = i
}
}
if len(roots) == 0 {
for i := 0; i < n; i++ {
if check(n, outs, i, -1, -1, map[int]bool{}) {
roots[i] = true
}
}
}
if len(roots) > 1 {
for i := len(edges) - 1; i >= 0; i-- {
edge := edges[i]
src := edge[0] - 1
dst := edge[1] - 1
if roots[dst] {
return []int{src + 1, dst + 1}
}
}
}
for root := range roots {
if len(parents[root]) > 0 {
return []int{parents[root][0] + 1, root + 1}
}
for from := len(parents[bad]) - 1; from >= 0; from-- {
if check(n, outs, root, parents[bad][from], bad, map[int]bool{}) {
return []int{parents[bad][from] + 1, bad + 1}
}
}
}
return []int{-1, -1}
}
func check(n int, outs map[int][]int, from, badfrom, badto int, visited map[int]bool) bool {
if visited[from] {
return false
}
visited[from] = true
if len(visited) == n {
return true
}
for _, to := range outs[from] {
if from == badfrom && to == badto {
continue
}
if check(n, outs, to, badfrom, badto, visited) {
return true
}
}
return false
}
¿Te ha gustado este análisis? Los problemas difíciles de LeetCode requieren paciencia, pero estudiar los patrones subyacentes hace que el proceso sea repetible. ¡Sigue construyendo, sigue practicando y mucha suerte en tus entrevistas!
Obtén la edición sin conexión de El Estilo de Vida de Kaue—una guía práctica para optimizar 🍏 Salud, 💰 Riqueza, ❤️ Amor y 🧘 Sentido.
Recibe notificaciones cuando publique nuevos ensayos, resúmenes de libros y guías prácticas sobre cómo vivir bien. Sin spam—cancela cuando quieras.
¿Tienes alguna pregunta, perspectiva o sugerencia? Comparte tus ideas abajo. Los comentarios funcionan con GitHub Discussions (sin anuncios y sin spam)—haz clic en Iniciar sesión con GitHub abajo para comentar o reaccionar (crear una cuenta gratuita en GitHub toma menos de un minuto).
Actualizado el 11 oct 2026.
AVISO LEGAL: El contenido de este sitio tiene fines exclusivamente informativos y educativos y no constituye asesoramiento médico, psicológico, financiero, de inversión, fiscal ni legal. Las ideas, la selección y las opiniones aquí presentadas son exclusivamente mías y no representan las de mi empleador. Los resúmenes de libros, conferencias y artículos son comentarios educativos independientes y siguen siendo propiedad intelectual de sus respectivos autores. Se pueden utilizar herramientas de IA para ayudar en la edición, el formato y la síntesis; aunque se hace todo lo posible por garantizar la precisión, pueden producirse errores. PRIVACIDAD: Este sitio utiliza servicios de terceros para la suscripción opcional al boletín (follow.it), los comentarios (giscus / GitHub Discussions) y el contenido multimedia incrustado (YouTube), que pueden procesar las direcciones IP y las cookies de los visitantes de acuerdo con sus respectivas políticas de privacidad.