Last Stone Weight

+10

Masz stos kamieni, a stones[i] to waga kamienia i. W każdej rundzie wybierz dwa najcięższe kamienie i rozbij je o siebie. Jeśli ważą tyle samo, oba zostają zniszczone. W przeciwnym razie lżejszy zostaje zniszczony, a cięższy zmniejsza swoją wagę o różnicę między ich wagami.

Napisz funkcję o nazwie lastStoneWeight, która rozgrywa rundy, dopóki nie zostanie co najwyżej jeden kamień, i zwraca wagę tego kamienia lub 0, jeśli nie został żaden kamień.

Funkcja

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: wagi kamieni w stosie
Zwracainteger: waga ostatniego kamienia lub 0, jeśli żaden nie pozostał

Ograniczenia

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

Przykłady

Wejście: stones = [3, 9, 4, 6, 2]
Wyjście: 0
Wyjaśnienie: 9 i 6 pozostawiają 3, następnie 4 i 3 pozostawiają 1, potem 3 i 2 pozostawiają kolejną 1. Dwa kamienie o wadze 1 niszczą się nawzajem, więc nic nie zostaje, a odpowiedź to 0.

Wejście: stones = [10, 4, 1]
Wyjście: 5
Wyjaśnienie: 10 i 4 pozostawiają 6, a 6 i 1 pozostawiają 5. Zostaje jeden kamień o wadze 5.

Wejście: stones = [8]
Wyjście: 8
Wyjaśnienie: Pojedynczego kamienia nie ma o co rozbić, więc jego waga 8 jest odpowiedzią.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Masy ciężarków wynoszą co najwyżej 1000. Czy możesz wykorzystać to ograniczenie, aby uzyskać złożoność czasową O(n + W), gdzie W to największa masa, bez użycia kopca?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Zasady wymagają symulacji: nie ma wzoru, który pozwoliłby pominąć rundy, więc rozgrywasz każdą z nich. W każdej rundzie potrzebne są dwa najcięższe kamienie ze stosu, który ciągle się zmienia, ponieważ rozbity kamień może wrócić jako lżejszy. Ponowne sortowanie w każdej rundzie pozwala je znaleźć, ale kosztuje O(n log n) na rundę. Kopiec maksymalny pozwala pobrać najcięższy kamień i wstawić nowy w O(log n).

Sortuj stos w każdej rundzie

Poprawne, ale nie kończy się na największych testach

Intuicja

Dosłownie przestrzegaj zasad. Posortuj stos tak, aby dwa najcięższe kamienie znalazły się na końcu, zdejmij je, a jeśli ich wagi się różnią, odłóż z powrotem kamień o wadze równej różnicy. Powtarzaj, aż na stosie zostanie jeden kamień lub nie zostanie żaden.

Kamień o wadze równej różnicy może trafić w dowolne miejsce w kolejności. W pierwszym przykładzie po połączeniu 9 i 6 zostaje kamień o wadze 3, który powinien znaleźć się przed 4, więc przed następną rundą sortujesz stos ponownie, aby znaleźć dwa nowe najcięższe kamienie.

Każda runda usuwa co najmniej jeden kamień, więc może być ich maksymalnie n-1, a w każdej sortujesz maksymalnie n kamieni: O(n² log n). Dla n = 10^4 oznacza to około 10^4 sortowań maksymalnie 10^4 liczb — co najmniej 5 × 10^7 kroków, nawet jeśli sortowanie rozpozna, że lista jest prawie posortowana, a gdy tego nie zrobi — kilka razy więcej. To zbyt wolne dla największych testów, podczas gdy kopiec poniżej wymaga tylko kilkuset tysięcy kroków.

Algorytm

Skopiuj kamienie do listy o nazwie pile.
Dopóki na stosie jest więcej niż jeden kamień, sortuj go rosnąco.
Usuń dwa ostatnie kamienie: heaviest i second.
Jeśli są różne, dodaj heaviest - second z powrotem na stos.
Zwróć pozostały kamień lub 0, jeśli stos jest pusty.

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

Kopiec maksymalny

Intuicja

W każdej rundzie potrzebujesz tylko największych kamieni, nigdy ich pełnej kolejności. Do tego służy kopiec maksymalny: przechowuje największą wartość na szczycie, a usunięcie elementu ze szczytu lub dodanie wartości kosztuje O(log n).

Umieść każdy kamień w kopcu. W każdej rundzie zdejmij dwa elementy, aby uzyskać dwa najcięższe kamienie. Jeśli się różnią, wstaw z powrotem różnicę; kopiec sam umieści ją we właściwym miejscu. Dla [10, 4, 1] zdejmujesz 10 i 4 i wstawiasz 6, a następnie zdejmujesz 6 i 1 i wstawiasz 5, a w kopcu pozostaje tylko 5.

Odbywa się co najwyżej n-1 rund, a każda obejmuje dwa zdjęcia elementów i co najwyżej jedno wstawienie, więc złożoność czasowa wynosi O(n log n), a kopiec zajmuje O(n) pamięci. Niektóre języki mają wbudowany kopiec: heapq w Pythonie jest kopcem minimalnym, więc przechowuje zanegowane wagi; Java ma PriorityQueue, C++ — priority_queue, Go — container/heap, Rust — BinaryHeap, a PHP — SplMaxHeap. W pozostałych językach rozwiązanie samodzielnie implementuje kopiec w tablicy: rodzic elementu o indeksie i znajduje się pod indeksem (i-1)/2, a nowa wartość przesuwa się w górę, dopóki jest większa od swojego rodzica.

Algorytm

Umieść każdy kamień w kopcu maksymalnym.
Gdy w kopcu znajduje się więcej niż jeden kamień, zdejmij najcięższy, a następnie drugi najcięższy.
Jeśli się różnią, dodaj heaviest - second.
Zwróć element ze szczytu kopca lub 0, jeśli kopiec jest pusty.

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

Pułapki i przypadki brzegowe

Symulacja jest krótka, więc błędy kryją się na końcach i w samym kopcu.

Zwracanie elementu ze szczytu pustego stosu. Gdy dwie ostatnie kamienie ważą tyle samo, nic nie zostaje, a odpowiedź to 0.
Przypadkowe użycie kopca minimalnego. Pythonowe heapq i domyślna Java PriorityQueue zwracają najmniejszą wartość; zaneguj wagi albo przekaż komparator odwrotny.
Zapominanie o ponownym zanegowaniu. W przypadku heapq obie pobrane wartości są ujemne, więc różnica, którą wstawiasz, to -(heaviest - second).
Posortowanie listy tylko na początku i przechodzenie po niej. Różnica mas dwóch kamieni może być mniejsza niż masa kamieni, których jeszcze nie ruszono, więc ustalona kolejność przestaje być aktualna po pierwszej rundzie.

Najczęstsze pytania4

Jaka jest złożoność czasowa Last Stone Weight?

Przy użyciu kopca maksymalnego zbudowanie kopca i rozegranie najwyżej n-1 rund obejmujących dwa pobrania i jedno wstawienie zajmuje O(n log n) czasu i O(n) miejsca. Sortowanie całego stosu w każdej rundzie zajmuje natomiast O(n² log n).

Dlaczego używać kopca w zadaniu Last Stone Weight?

W każdej rundzie trzeba znaleźć dwie największe wartości w kolekcji, która zmienia się po każdej rundzie. Kopiec odpowiada na pytanie „jaka wartość jest największa” i pozwala dodać nową wartość w czasie O(log n), bez utrzymywania całej kolekcji w posortowanej kolejności. Właśnie to zadanie powtarza symulacja.

Czy problem Last Stone Weight można rozwiązać bez kopca?

Tak, ponieważ wagi są małe. Policz, ile kamieni ma każdą wagę od 1 do 1000, a następnie przechodź w dół, zaczynając od największej wagi. Kamienie o jednakowej wadze znoszą się parami, a nowy kamień jest zawsze lżejszy od najcięższego kamienia użytego do jego utworzenia, więc przechodzenie odbywa się tylko w dół. Zajmuje to O(n + W) czasu dla największej wagi W.

Czy kolejność rozbijania kamieni o jednakowej wadze zmienia wynik?

Nie. Gdy kilka kamieni ma największą wagę, te dwa, które wybierzesz, ważą tyle samo niezależnie od wyboru, więc po rundzie w stosie pozostają te same wagi. Odpowiedź zależy tylko od wag, dlatego każde poprawne rozwiązanie zwraca tę samą liczbę.

Python

def lastStoneWeight(stones):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane