Last Stone Weight

Q: Qual è la complessità temporale di Last Stone Weight?

Con un max-heap, costruire l'heap e giocare al massimo n-1 round di due estrazioni e un inserimento richiede O(n log n) di tempo e O(n) di spazio. Ordinare l'intera pila a ogni round richiede invece O(n² log n) .

FacileHeap

+10

Hai un mucchio di pietre e stones[i] è il peso della pietra i. A ogni turno, prendi le due pietre più pesanti e sbattile l'una contro l'altra. Se hanno lo stesso peso, vengono distrutte entrambe. Altrimenti, quella più leggera viene distrutta e quella più pesante si riduce della differenza tra i due pesi.

Scrivi una funzione chiamata lastStoneWeight che esegua i turni finché non rimane al massimo una pietra e restituisca il peso di quella pietra, oppure 0 se non rimane nessuna pietra.

Funzione

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: i pesi delle pietre nel mucchio
Restituisceinteger: il peso dell'ultima pietra, oppure 0 se non ne rimane nessuna

Vincoli

1 ≤ stones.length ≤ 10⁴
1 ≤ stones[i] ≤ 1000

Esempi

Input: stones = [3, 9, 4, 6, 2]
Output: 0
Spiegazione: 9 e 6 lasciano un 3, poi 4 e 3 lasciano un 1, poi 3 e 2 lasciano un altro 1. Le due pietre di peso 1 si distruggono a vicenda, quindi non rimane nulla e la risposta è 0.

Input: stones = [10, 4, 1]
Output: 5
Spiegazione: 10 e 4 lasciano un 6, e 6 e 1 lasciano un 5. Rimane una pietra, del peso di 5.

Input: stones = [8]
Output: 8
Spiegazione: Una singola pietra non ha nulla contro cui essere frantumata, quindi il suo peso 8 è la risposta.

+13 test nascosti all’invio

Per approfondire

I pesi sono al massimo 1000. Riesci a sfruttare questo limite per completare il tutto in tempo O(n + W), dove W è il peso massimo, senza usare un heap?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Le regole descrivono una simulazione: non esiste una formula per saltare avanti, quindi giochi ogni round. Ogni round richiede le due pietre più pesanti di un mucchio che cambia continuamente, perché una pietra frantumata può tornare più leggera. Ordinare di nuovo a ogni round permette di trovarle, ma costa O(n log n) per round. Un heap massimo restituisce la pietra più pesante e ne reinserisce una nuova in O(log n).

Ordina la pila a ogni turno

Corretto, ma non termina sui test più grandi

Intuizione

Segui le regole alla lettera. Ordina il mucchio in modo che le due pietre più pesanti siano alla fine, rimuovile e, se i loro pesi differiscono, rimetti la differenza. Ripeti finché nel mucchio rimane una sola pietra o nessuna.

La differenza può finire in qualsiasi punto dell'ordine. Nel primo esempio, 9 e 6 lasciano un 3, che va sotto il 4, quindi ordini di nuovo prima del turno successivo per trovare le due nuove pietre più pesanti.

Ogni turno rimuove almeno una pietra, quindi ci sono fino a n-1 turni, ciascuno con un ordinamento di fino a n pietre: O(n² log n). Con n = 10^4 si tratta di circa 10^4 ordinamenti di fino a 10^4 numeri, almeno 5 × 10^7 passaggi anche quando l'ordinamento rileva che la lista è quasi ordinata, e diverse volte tanto quando non lo rileva. È troppo lento per i test più grandi, mentre l'heap qui sotto richiede solo qualche centinaio di migliaia di passaggi.

Algoritmo

Copia le pietre in un elenco chiamato pile.
Finché l’elenco contiene più di una pietra, ordinalo in ordine crescente.
Rimuovi le ultime due pietre, heaviest e second.
Se sono diverse, aggiungi heaviest - second all’elenco.
Restituisci la pietra rimanente, oppure 0 quando l’elenco è vuoto.

def lastStoneWeight(stones):
    pile = list(stones)
    while len(pile) > 1:
        pile.sort()  # the two heaviest stones move to the end
        heaviest = pile.pop()
        second = pile.pop()
        if heaviest != second:
            pile.append(heaviest - second)
    return pile[0] if pile else 0

Heap massimo

Intuizione

In ogni round ti servono solo le pietre più grandi, mai l'ordine completo. Per questo si usa un max-heap: mantiene il valore più grande in cima e rimuovere il valore in cima o aggiungere un valore costa O(log n).

Inserisci ogni pietra nell'heap. A ogni round, estrai due volte per ottenere le due pietre più pesanti. Se sono diverse, inserisci di nuovo la differenza; l'heap la sposta da solo nella posizione corretta. Con [10, 4, 1] estrai 10 e 4 e inserisci 6, poi estrai 6 e 1 e inserisci 5, e nell'heap rimane solo 5.

Ci sono al massimo n-1 round, ciascuno con due estrazioni e al massimo un inserimento, quindi la complessità temporale è O(n log n) e l'heap usa O(n) spazio. Alcuni linguaggi includono un heap: heapq di Python è un min-heap, quindi memorizza i pesi negati; Java ha PriorityQueue, C++ priority_queue, Go container/heap, Rust BinaryHeap e PHP SplMaxHeap. Negli altri linguaggi, la soluzione implementa il proprio heap in un array: il genitore dell'indice i si trova in (i-1)/2 e un nuovo valore risale finché è maggiore del suo genitore.

Algoritmo

Metti ogni pietra in un max-heap.
Mentre l'heap contiene più di una pietra, estrai la più pesante e poi la seconda più pesante.
Se sono diverse, inserisci heaviest - second.
Restituisci il valore in cima all'heap oppure 0 se è vuoto.

import heapq


def lastStoneWeight(stones):
    # heapq is a min-heap, so store negated weights: the smallest entry is the heaviest stone.
    heap = [-w for w in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        heaviest = -heapq.heappop(heap)
        second = -heapq.heappop(heap)
        if heaviest != second:
            heapq.heappush(heap, -(heaviest - second))
    return -heap[0] if heap else 0

Trappole e casi limite

La simulazione è breve, quindi i bug si nascondono agli estremi e nell'heap stesso.

Restituire il valore in cima a una pila vuota. Quando le ultime due pietre hanno lo stesso peso, non rimane nulla e la risposta è 0.
Usare per errore un min-heap. heapq di Python e il PriorityQueue predefinito di Java restituiscono il valore più piccolo; nega i pesi oppure passa un comparatore inverso.
Dimenticare di annullare la negazione. Con heapq, entrambi i valori estratti sono negativi, quindi la differenza da inserire è -(heaviest - second).
Ordinare una volta all'inizio e scorrere l'elenco. La differenza tra due pietre può essere più leggera delle pietre che non hai ancora toccato, quindi un ordine fisso diventa obsoleto dopo il primo turno.

Domande frequenti4

Qual è la complessità temporale di Last Stone Weight?

Con un max-heap, costruire l'heap e giocare al massimo n-1 round di due estrazioni e un inserimento richiede O(n log n) di tempo e O(n) di spazio. Ordinare l'intera pila a ogni round richiede invece O(n² log n).

Perché usare un heap per Last Stone Weight?

Ogni round richiede i due valori più grandi di una raccolta che cambia dopo ogni round. Un heap risponde alla domanda «qual è il valore più grande» e accetta un nuovo valore in O(log n), senza mantenere ordinata l'intera raccolta. È esattamente il lavoro che la simulazione ripete.

È possibile risolvere Last Stone Weight senza un heap?

Sì, perché i pesi sono piccoli. Conta quante pietre hanno ciascun peso da 1 a 1000 e procedi dal peso più alto verso il basso. Le pietre dello stesso peso si annullano a coppie e una nuova pietra è sempre più leggera della più pesante tra quelle usate per crearla, quindi si procede solo verso il basso. L'operazione richiede un tempo O(n + W) per il peso massimo W.

L'ordine in cui si frantumano pesi uguali cambia la risposta?

No. Quando più pietre hanno lo stesso peso massimo, le due che scegli hanno lo stesso peso in entrambi i casi, quindi dopo il turno il mucchio contiene gli stessi pesi. La risposta dipende solo dai pesi, ed è per questo che ogni soluzione corretta restituisce lo stesso numero.

Python

def lastStoneWeight(stones):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

stones = [3, 9, 4, 6, 2]

Atteso