Last Stone Weight

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

Con un max-heap, al massimo n-1 turni di due estrazioni e un inserimento richiedono O(n log n) di tempo e O(n) di spazio. Ordinare l'intero mucchio a ogni turno richiede O(n² log n) .

FacileHeap

+10

Hai un mucchio di pietre e stones[i] è il peso della pietra i. A ogni round, prendi le due pietre più pesanti e falle scontrare. Se hanno lo stesso peso, entrambe vengono distrutte. Altrimenti, quella più leggera viene distrutta e quella più pesante si riduce alla differenza tra i due pesi.

Scrivi lastStoneWeight, che esegue i round finché non rimane al massimo una pietra e ne restituisce il peso, 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 una 3, poi 4 e 3 lasciano una 1, poi 3 e 2 lasciano un'altra 1. Le due pietre da 1 si distruggono a vicenda, quindi 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, che pesa 5.

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

Per approfondire

I pesi sono al massimo 1000. Puoi usare questo limite per completare in tempo O(n + W), dove W è il peso più grande, senza un heap?

Suggerimenti

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

0 di 3 aperti

Soluzione

Non esiste una formula per saltare avanti: giochi ogni turno. Per ogni turno servono le due pietre più pesanti di un mucchio che continua a cambiare, perché una pietra frantumata può tornare più leggera. Un max-heap restituisce la pietra più pesante e ne inserisce una nuova in O(log n).

Ordina la pila a ogni round

Corretto, ma non termina sui test più grandi

Intuizione

Segui letteralmente le regole: ordina il mucchio, prendi le due pietre più pesanti dalla fine e rimetti la loro differenza se non è zero. Ordina di nuovo a ogni turno, perché la differenza può finire ovunque. Nel primo esempio 9 e 6 lasciano un 3, che va sotto il 4.

Ogni turno rimuove almeno una pietra, quindi ci sono fino a n-1 turni, ciascuno con l'ordinamento di un massimo di n pietre: O(n² log n). Per n = 10^4 si tratta di circa 10^4 ordinamenti di un massimo di 10^4 numeri.

Algoritmo

Copia le pietre in una lista chiamata pile.
Finché la pila contiene più di una pietra, ordinala in ordine crescente.
Rimuovi le ultime due pietre, heaviest e second.
Se sono diverse, aggiungi heaviest - second di nuovo alla pila.
Restituisci la pietra rimanente, oppure 0 se la pila è vuota.

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

Un max-heap mantiene il valore più grande in cima e rimuovere l'elemento in cima o aggiungere un valore ha un costo di O(log n). Inserisci tutte le pietre al suo interno. A ogni turno, estrai due volte per ottenere le due pietre più pesanti e reinserisci la differenza se non è zero; l'heap la sposta nella posizione corretta. Per [10, 4, 1] estrai 10 e 4 e inserisci 6, poi estrai 6 e 1 e inserisci 5.

Ci sono al massimo n-1 turni, ciascuno con due estrazioni e un inserimento, quindi il tempo è O(n log n) e lo spazio è O(n). Nei linguaggi senza un heap integrato, la soluzione ne mantiene uno in un array, con il genitore dell'indice i in (i-1)/2.

Algoritmo

Inserisci ogni pietra in un heap massimo.
Finché l'heap contiene più di una pietra, estrai la più pesante e poi la seconda più pesante.
Se sono diverse, inserisci heaviest - second.
Restituisci la cima dell'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

Restituire il valore in cima a un mucchio vuoto. Quando le ultime due pietre hanno lo stesso peso, come nel primo esempio, non rimane nulla e la risposta è 0.
Usare per sbaglio 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 il segno con i pesi negati. Entrambi i valori estratti sono negativi, quindi il valore da inserire è -(heaviest - second).
Ordinare una volta all'inizio e scorrere la lista. La differenza può essere inferiore al peso di pietre che non hai ancora toccato, quindi l'ordine diventa obsoleto dopo il primo turno.

Domande frequenti3

Qual è la complessità temporale di Last Stone Weight?

Con un max-heap, al massimo n-1 turni di due estrazioni e un inserimento richiedono O(n log n) di tempo e O(n) di spazio. Ordinare l'intero mucchio a ogni turno richiede O(n² log n).

Perché usare un heap per Last Stone Weight invece di una lista ordinata?

Un elenco ordinato fornisce subito le due pietre più pesanti, ma reinserire la differenza mantenendo l'ordine sposta fino a n elementi, O(n²) nel complesso di tutti i turni. Un heap risponde solo alla domanda «qual è il valore più grande» e accetta un nuovo valore, entrambe le operazioni in O(log n), ed è tutto ciò che serve per la simulazione.

L'ordine con cui si distruggono pesi uguali cambia la risposta?

No. Quando più pietre hanno lo stesso peso massimo, le due che scegli pesano uguale in ogni caso, quindi il mucchio dopo il turno contiene gli stessi pesi. La risposta dipende solo dai pesi.

def lastStoneWeight(stones):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomento

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

Output atteso