Lo Stile di Vita di Kaue
Affrontare i problemi Hard di LeetCode può spesso dare la sensazione di sbattere contro un muro. Tuttavia, scomporli in schemi assimilabili — come la Programmazione Dinamica, il Backtracking e la Teoria dei Grafi — li rende molto più accessibili.
In questo articolo condivido 7 dei problemi Hard di LeetCode più interessanti che ho risolto in Go. Per rendere questa guida il più utile possibile, ho sintetizzato le spiegazioni concentrandomi fortemente sull’intuizione di base e sulla complessità, rendendo più facile comprendere il passaggio dal testo del problema al codice funzionante.
Dati e , restituisci la sequenza di permutazione dei numeri da a .
Ad esempio, se , le permutazioni sono: "123", "132", "213", "231", "312", "321". Se , la risposta è "213".
Invece di generare tutte le permutazioni (il che sarebbe troppo lento), possiamo usare un approccio matematico sfruttando i fattoriali.
Per cifre, ci sono in totale permutazioni. Se fissiamo la prima cifra, ci sono permutazioni delle cifre rimanenti. Possiamo determinare la prima cifra calcolando in quale blocco di permutazioni ricade la permutazione. L’indice della nostra prossima cifra in una lista ordinata di cifre disponibili sarà semplicemente . Dopo aver scelto una cifra, aggiorniamo con il resto e procediamo ricorsivamente.
import "fmt"
func getPermutation(n int, k int) string {
factorial := 1
digits := []int{}
// Calcola i fattoriali e popola lo slice delle cifre
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 {
// Trova in quale blocco di permutazioni ricade 'k'
index := k / factorial
res := fmt.Sprintf("%d", digits[index])
if n <= 0 {
return res
}
// Aggiorna k per il livello successivo: k % factorial
// Aggiorna factorial per il livello successivo: factorial / n
// Rimuove la cifra selezionata dallo slice
nextK := k % factorial
nextFactorial := factorial / n
remainingDigits := append(digits[:index], digits[index+1:]...)
res += solvePermutation(n-1, nextK, nextFactorial, remainingDigits)
return res
}
Implementa il matching di espressioni regolari con . (corrisponde a qualsiasi singolo carattere) e * (corrisponde a zero o più occorrenze dell’elemento precedente). Il matching deve coprire l’intera stringa di input.
Questo è un classico problema di Programmazione Dinamica. Possiamo usare la memoizzazione per evitare calcoli ridondanti.
Per ogni data combinazione di caratteri della stringa s e del pattern p, se il carattere successivo nel pattern è *, abbiamo due scelte:
s ma rimanere su * in p per fare potenzialmente corrispondere altri caratteri.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] == '*' {
// Opzione A: Zero occorrenze
if solveRegex(s, p, sn, pn, si, pi+2, memo) {
res = true
// Opzione B: Una o più occorrenze (se il carattere corrente corrisponde)
} 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]) {
// Corrispondenza normale di un carattere
res = solveRegex(s, p, sn, pn, si+1, pi+1, memo)
}
if res {
memo[si][pi] = 2
} else {
memo[si][pi] = 1
}
return res
}
Dato un albero binario non vuoto, trova la somma massima di un percorso. Un percorso può salire o scendere lungo le connessioni genitore-figlio, ma non deve necessariamente passare per la radice.
Usiamo la ricerca in profondità (DFS). In ogni nodo valutiamo due tipi di percorsi:
fromRoot): Il percorso massimo che parte dal nodo corrente e scende lungo uno dei suoi rami. Un nodo genitore può utilizzare questo percorso.other): Il percorso massimo interamente contenuto nel sottoalbero corrente (ad esempio, che sale dal figlio sinistro fino al nodo corrente e riscende verso il figlio destro). Questo percorso è “chiuso” e non può essere esteso verso l’alto fino a un genitore.Il nostro massimo globale sarà il valore più alto tra tutti i percorsi “non estendibili” trovati, oppure il percorso estendibile della radice.
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)
// Percorso estendibile (può scegliere solo un ramo o fermarsi al nodo)
currentFromRoot := max([]int{
root.Val,
sum([]int{root.Val, left}),
sum([]int{root.Val, right}),
})
// Percorso chiuso (può formare un arco sul nodo corrente o essere completamente dentro un figlio)
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
}
Scrivi un programma per risolvere un puzzle Sudoku 9x9. Devi soddisfare le regole standard del Sudoku (righe, colonne e sotto-riquadri 3x3).
Questo problema richiede un algoritmo di backtracking. Per renderlo efficiente ed evitare errori di Time Limit Exceeded (TLE) su LeetCode, ottimizziamo la ricerca usando un’euristica: prova sempre a riempire per prima la cella vuota con il minor numero di cifre valide possibili. Usiamo array booleani per verificare istantaneamente se un numero è disponibile in una riga, colonna o riquadro 3x3.
func solveSudoku(board [][]byte) {
var rows, cols [9][9]bool
var boxes [3][3][9]bool
// Popola lo stato iniziale
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 // Inizia con un valore superiore al massimo di opzioni possibili (9)
// Euristica: trova la cella con il minor numero di opzioni valide
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: nessuna cella vuota rimasta
if bestI == -1 { return true }
// Prova a inserire numeri validi nella cella ottimale scelta
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
}
// Backtrack
board[bestI][bestJ] = '.'
rows[bestI][val], cols[bestJ][val], boxes[bestI/3][bestJ/3][val] = false, false, false
}
}
return false
}
Ti viene dato un intero , che indica che ci sono corsi numerati da a . Ti viene inoltre dato un array relations dove relations[i] = [prevCourse, nextCourse], che rappresenta una relazione di propedeuticità. In un semestre puoi seguire al massimo corsi. Restituisci il numero minimo di semestri necessari per completare tutti i corsi.
Poiché è piccolo (), possiamo usare la ricerca in ampiezza (BFS) combinata con le Bitmask. Una bitmask rappresenta lo stato dei corsi che abbiamo completato. In ogni semestre identifichiamo tutti i corsi disponibili (i cui prerequisiti sono pienamente soddisfatti). Se i corsi disponibili superano , dobbiamo iterare su tutte le possibili combinazioni di dimensione usando l’enumerazione delle sottomaschere. Usiamo una mappa di stati visitati per evitare di rivisitare le stesse combinazioni.
func minNumberOfSemesters(n int, relations [][]int, k int) int {
// prerequisites[i] è una bitmask dei corsi che devono essere seguiti prima del corso i
prerequisites := make([]int, n)
for _, relation := range relations {
prevCourse := relation[0] - 1
nextCourse := relation[1] - 1
prerequisites[nextCourse] |= 1 << prevCourse
}
// states e costs fungono da coda 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: tutti i corsi sono stati completati
if state == (1<<n)-1 {
return cost
}
// Trova tutti i corsi disponibili da seguire in questo 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)
}
// Se possiamo seguire tutti i corsi disponibili in un solo semestre, facciamolo
if len(courses) <= k {
add(next)
continue
}
// Altrimenti, esplora tutte le combinazioni di dimensione 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)
}
}
Data una matrice e un intero , restituisci la somma massima di un rettangolo nella matrice tale che la sua somma non sia maggiore di .
Possiamo comprimere la matrice 2D in un array 1D fissando i confini delle colonne sinistra e destra. Una volta ottenuto un array 1D che rappresenta le somme delle righe tra quelle colonne, il problema si riduce a trovare la somma di un sottoarray . Mantenendo una lista ordinata di somme prefisse (usando un albero binario di ricerca o un semplice inserimento in un array ordinato), possiamo cercare in modo efficiente la più piccola somma prefissa che soddisfa current_prefix - past_prefix <= k, oppure precalcolare una tabella di somme prefisse 2D per interrogare qualsiasi sottorettangolo in tempo .
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)
}
// Precalcola le somme prefisse 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]
}
}
// Valuta tutti i possibili sottorettangoli usando il principio di inclusione-esclusione
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
}
In un grafo orientato, ogni nodo ha esattamente un genitore tranne il nodo radice, che non ha genitori. Viene aggiunto un arco orientato extra. Trova l’arco che può essere rimosso in modo che il grafo risultante sia un albero radicato valido. Se ci sono più risposte, restituisci quella che compare per ultima nell’input.
Poiché si tratta di un grafo orientato, l’arco aggiunto crea uno di questi due problemi (o entrambi):
Per prima cosa controlliamo se qualche nodo ha due genitori. In tal caso, l’arco ridondante deve essere uno dei due archi che puntano a quel nodo. Altrimenti, l’arco extra forma un ciclo orientato. Possiamo testare gli archi candidati in ordine inverso rispetto all’input e verificare tramite DFS (o Union-Find) se la rimozione dell’arco candidato lascia un albero radicato valido in cui tutti gli nodi sono raggiungibili dalla radice senza cicli.
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
}
Ti è piaciuta questa analisi? I problemi Hard di LeetCode richiedono pazienza, ma studiare gli schemi sottostanti rende il processo ripetibile. Continua a costruire, continua a esercitarti e in bocca al lupo per i tuoi colloqui!
Scarica l'edizione offline di Lo Stile di Vita di Kaue—una guida pratica per ottimizzare 🍏 Salute, 💰 Ricchezza, ❤️ Amore e 🧘 Significato.
Ricevi una notifica quando pubblico nuovi saggi, riassunti di libri e guide pratiche per vivere bene. Niente spam—annulla l'iscrizione in qualsiasi momento.
Hai una domanda, una prospettiva o un suggerimento? Condividi i tuoi pensieri qui sotto. I commenti utilizzano GitHub Discussions (senza pubblicità e senza spam)—clicca su Accedi con GitHub qui sotto per commentare o reagire (creare un account GitHub gratuito richiede meno di un minuto).
Aggiornato il 11 ott 2026.
AVVERTENZA LEGALE: Il contenuto di questo sito ha scopo esclusivamente informativo ed educativo e non costituisce consulenza medica, psicologica, finanziaria, di investimento, fiscale o legale. Le idee, la selezione e le opinioni qui presentate sono esclusivamente mie e non rappresentano quelle del mio datore di lavoro. I riassunti di libri, conferenze e articoli sono commenti educativi indipendenti e rimangono proprietà intellettuale dei rispettivi autori. Strumenti di IA possono essere utilizzati per assistere nella revisione, formattazione e sintesi; sebbene venga compiuto ogni sforzo per garantire l'accuratezza, possono verificarsi errori. PRIVACY: Questo sito utilizza servizi di terze parti per l'iscrizione facoltativa alla newsletter (follow.it), i commenti (giscus / GitHub Discussions) e i contenuti multimediali incorporati (YouTube), che possono trattare gli indirizzi IP e i cookie dei visitatori in conformità con le rispettive informative sulla privacy.