Last Stone Weight

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

W przypadku kopca maksymalnego maksymalnie n-1 rund, z których każda obejmuje dwa zdjęcia i jedno wstawienie, wymaga O(n log n) czasu i O(n) pamięci. Sortowanie całego stosu w każdej rundzie wymaga O(n² log n) .

ŁatweKopiec

+10

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

Napisz lastStoneWeight, które rozgrywa rundy, aż pozostanie co najwyżej jeden kamień, i zwraca jego wagę albo 0, jeśli nie został żaden kamień.

Funkcja

lastStoneWeight(stones: integer-array) → integer

stonesinteger-array: wagi kamieni na stosie
Zwracainteger: masa ostatniego kamienia albo 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, następnie 3 i 2 pozostawiają kolejne 1. Dwa kamienie o wadze 1 niszczą się nawzajem, więc odpowiedź to 0.

Wejście: stones = [10, 4, 1]
Wyjście: 5
Wyjaśnienie: 10 i 4 dają 6, a 6 i 1 dają 5. Pozostaje 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ą.

Pytanie dodatkowe

Masy wynoszą najwyżej 1000. Czy możesz wykorzystać to ograniczenie, aby uzyskać złożoność czasową O(n + W), gdzie W jest największą masą, bez użycia kopca?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Nie ma wzoru, który pozwoliłby pominąć kolejne rundy: rozgrywasz każdą z nich. W każdej rundzie potrzebujesz dwóch najcięższych kamieni ze stosu, który ciągle się zmienia, ponieważ rozbity kamień może wrócić jako lżejszy. Kopiec maksymalny udostępnia najcięższy kamień i przyjmuje nowy w czasie 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, zdejmij z końca dwa najcięższe kamienie i odłóż ich różnicę, jeśli nie wynosi zero. Sortuj ponownie w każdej rundzie, ponieważ różnica może trafić w dowolne miejsce. W pierwszym przykładzie po 9 i 6 zostaje 3, które należy umieścić poniżej 4.

W każdej rundzie usuwany jest co najmniej jeden kamień, więc odbywa się maksymalnie n-1 rund, a w każdej z nich sortowanych jest maksymalnie n kamieni: O(n² log n). Dla n = 10^4 oznacza to około 10^4 sortowań maksymalnie 10^4 liczb.

Algorytm

Skopiuj kamienie do listy o nazwie pile.
Gdy na stosie znajduje się więcej niż jeden kamień, posortuj go rosnąco.
Usuń dwa ostatnie kamienie: heaviest i second.
Jeśli się różnią, 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

Kopiec maksymalny przechowuje największą wartość na szczycie, a usunięcie elementu ze szczytu lub dodanie wartości wymaga O(log n). Umieść w nim każdy kamień. W każdej rundzie zdejmij dwa kamienie o największej wadze i wstaw z powrotem różnicę, jeśli nie jest równa zero; kopiec umieści ją we właściwym miejscu. Dla [10, 4, 1] zdejmujesz 10 i 4, a następnie wstawiasz 6, po czym zdejmujesz 6 i 1 i wstawiasz 5.

Wykonuje się najwyżej n-1 rund, z których każda obejmuje dwa zdjęcia i jedno wstawienie, więc złożoność czasowa wynosi O(n log n), a złożoność pamięciowa O(n). W językach bez wbudowanego kopca rozwiązanie przechowuje go w tablicy, gdzie rodzicem elementu o indeksie i jest element o indeksie (i-1)/2.

Algorytm

Umieść każdy kamień w kopcu maksymalnym.
Gdy kopiec zawiera więcej niż jeden kamień, zdejmij z niego najcięższy kamień, a następnie drugi najcięższy.
Jeśli się różnią, wstaw heaviest - second.
Zwróć element ze szczytu kopca lub 0, jeśli 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

Zwracanie elementu ze szczytu pustego stosu. Gdy dwie ostatnie kamienie mają tę samą wagę, jak w pierwszym przykładzie, nic nie zostaje, a wynikiem jest 0.
Przypadkowe użycie kopca minimum. Pythonowy heapq i domyślna klasa PriorityQueue w Javie zwracają najmniejszą wartość; zaneguj wagi albo przekaż komparator odwracający kolejność.
Zapominanie o znaku przy zanegowanych wagach. Obie pobrane wartości są ujemne, więc wartość do dodania to -(heaviest - second).
Jednorazowe sortowanie na początku i przechodzenie po liście. Różnica może być mniejsza od wagi kamieni, których jeszcze nie ruszono, więc kolejność przestaje być aktualna już po pierwszej rundzie.

Najczęstsze pytania3

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

W przypadku kopca maksymalnego maksymalnie n-1 rund, z których każda obejmuje dwa zdjęcia i jedno wstawienie, wymaga O(n log n) czasu i O(n) pamięci. Sortowanie całego stosu w każdej rundzie wymaga O(n² log n).

Dlaczego do Last Stone Weight używać kopca zamiast posortowanej listy?

Posortowana lista od razu wskazuje dwa najcięższe kamienie, ale ponowne uporządkowanie różnicy przesuwa do n elementów, co daje O(n²) łącznie we wszystkich rundach. Kopiec odpowiada tylko na pytanie „która wartość jest największa” i przyjmuje nową wartość — oba działania w czasie O(log n), co w zupełności wystarcza do przeprowadzenia symulacji.

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

Nie. Gdy kilka kamieni ma największą wagę, dwa wybrane przez ciebie ważą tyle samo niezależnie od tego, które wybierzesz, więc stos po rundzie zawiera te same wagi. Odpowiedź zależy tylko od wag.

def lastStoneWeight(stones):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik