Remove K Digits

Q: Jaka jest złożoność czasowa algorytmu Remove K Digits?

Przy użyciu stosu monotonicznego algorytm działa w czasie O(n) dla n cyfr: każda cyfra jest umieszczana na stosie raz, a każde usunięcie ze stosu zużywa jedno z k usunięć. Stos przechowuje do n cyfr, więc dodatkowa pamięć wynosi O(n) . Ponowne skanowanie od lewej strony przy każdym usunięciu kosztuje O(n·k) .

ŚrednieStos monotoniczny Algorytmy zachłanne

+10

Otrzymujesz nieujemną liczbę zapisaną jako ciąg cyfr num oraz liczbę całkowitą k. Usuń dokładnie k cyfr i zachowaj pozostałe w ich pierwotnej kolejności, tak aby otrzymana liczba była jak najmniejsza.

Zwróć ją jako ciąg znaków bez zer wiodących. Jeśli nic nie zostało albo zostały same zera, zwróć "0".

Funkcja

removeKdigits(num: string, k: integer) → string

numstring: liczba zapisana jako ciąg cyfr
kinteger: ile cyfr usunąć
Zwracastring: najmniejsza liczba, jaką możesz pozostawić, jako ciąg znaków bez zer wiodących

Ograniczenia

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num przechowuje wyłącznie cyfry od 0 do 9.
num nie ma zer wiodących, chyba że jest to sama liczba zero: "0".

Przykłady

Wejście: num = "4325043"k = 3
Wyjście: "2043"
Wyjaśnienie: Usunięcie 4 i pierwszej 3 stawia 2 na początku. 0 nie może być pierwsze: przed nim stoją cztery cyfry, a masz trzy usunięcia. Ostatnie usunięcie obejmuje 5, które stoi przed mniejszym 0.

Wejście: num = "30200"k = 1
Wyjście: "200"
Wyjaśnienie: Usunięcie 3 pozostawia 0200, a bez początkowego zera jest to 200. Każde inne usunięcie pozostawia 3 z przodu i daje liczbę czterocyfrową, taką jak 3000.

Wejście: num = "52"k = 2
Wyjście: "0"
Wyjaśnienie: Obie cyfry zostają usunięte, więc nic nie zostaje, a odpowiedź to "0".

Pytanie dodatkowe

Jak zmienić rozwiązanie, aby usunąć k cyfr i zamiast tego pozostawić największą liczbę?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Najbardziej ważą cyfry po lewej stronie, więc należy usunąć pierwszą cyfrę, która jest większa od swojej prawej sąsiadki. Stos cyfr, które zachowujesz, pozwala zastosować tę zasadę do całego ciągu znaków w jednym przebiegu. Pozostałe na końcu usunięcia wykonuje się od tyłu, a zera wiodące usuwa się na samym końcu.

Usuwaj po jednej cyfrze

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

Intuicja

Usuwaj po jednej cyfrze naraz: znajdź pierwszą pozycję i, dla której num[i] > num[i+1], i usuń num[i] albo usuń ostatnią cyfrę, jeśli cyfry nigdy nie maleją. Powtórz k razy.

Każda odpowiedź ma n-k cyfr, więc o tym, która jest mniejsza, decyduje pierwsza pozycja, na której dwie odpowiedzi się różnią. Do pozycji i cyfry nigdy nie maleją, więc usunięcie wcześniejszej cyfry przesuwa na jej miejsce cyfrę co najmniej tak dużą; usunięcie późniejszej pozostawia na miejscu dużą cyfrę num[i]. Usunięcie num[i] zmniejsza najwcześniejszą pozycję, której wartość można zmniejszyć.

Każde usunięcie wymaga ponownego skanowania od lewej strony i przesunięcia cyfr, które znajdują się za usuniętą cyfrą, więc złożoność wynosi O(n·k). W przypadku 40,000 jedynek i k = 25,000 skanowanie odczytuje około 6.9 × 10^8 cyfr.

Algorytm

Skopiuj cyfry do listy, z której możesz usuwać elementy.
Powtórz k razy: idź od lewej strony do pierwszej cyfry większej od następnej albo do ostatniej cyfry i usuń ją.
Usuń zera wiodące i zwróć "0", jeśli nic nie zostanie.

def removeKdigits(num, k):
    digits = list(num)
    for _ in range(k):
        # Find the first digit that is bigger than the digit after it.
        # If the digits never go down, i stops on the last digit.
        i = 0
        while i + 1 < len(digits) and digits[i] <= digits[i + 1]:
            i += 1
        del digits[i]
    result = "".join(digits).lstrip("0")
    return result if result else "0"

Monotoniczny stos zachowanych cyfr

Intuicja

Po usunięciu przez wolniejszą wersję num[i] cyfry przed i nadal nigdy nie maleją, więc następne usuwanie może zacząć się tylko od cyfry przed luką. Stos przechowuje ten prefiks: zachowane cyfry, które nie maleją od dołu do góry. Gdy nowa cyfra jest mniejsza od wierzchołka, wierzchołek jest większy od swojego prawego sąsiada, czyli cyfry, którą usunęłaby wolniejsza wersja. Zdejmij ją ze stosu, wykorzystaj jedno usunięcie i zdejmuj kolejne cyfry, dopóki nowy wierzchołek nadal jest większy.

Dla 4325043 przy k = 3 cyfra 3 zdejmuje 4, cyfra 2 zdejmuje 3, a cyfra 0 zdejmuje 5. Cyfry 4 i 3 są odkładane na stos w miarę ich napływania, dając 2043.

Każda cyfra jest odkładana na stos raz, a każde zdjęcie ze stosu wykorzystuje jedno z k usunięć, więc przebieg ma złożoność O(n).

Algorytm

Utwórz pusty stos cyfr.
Dla każdej cyfry w num: dopóki pozostały usunięcia i cyfra na szczycie stosu jest większa od tej cyfry, zdejmij element ze szczytu i wykorzystaj jedno usunięcie. Następnie dodaj cyfrę na stos.
Jeśli po pętli pozostały usunięcia, usuń ze szczytu stosu tyle cyfr, ile ich pozostało.
Odczytaj stos od dołu do góry, pomiń początkowe zera i zwróć resztę albo "0", jeśli nic nie pozostało.

def removeKdigits(num, k):
    stack = []  # kept digits, never decreasing from bottom to top
    for digit in num:
        # A bigger digit right before a smaller one: dropping it makes the number smaller.
        while k > 0 and stack and stack[-1] > digit:
            stack.pop()
            k -= 1
        stack.append(digit)
    # The kept digits never decrease, so any removals left come off the end.
    stack = stack[:len(stack) - k]
    result = "".join(stack).lstrip("0")
    return result if result else "0"

Pułapki i przypadki brzegowe

Usuwanie elementu ze stosu, gdy jego ostatnia cyfra jest równa nowej cyfrze. W 112 przy k = 1 zostaje 12; poprawna odpowiedź to 11.
Zapominanie o usunięciach pozostałych po pętli albo usuwanie cyfr z początku. Stos nigdy się nie zmniejsza, więc jego ostatnie cyfry to: 123456789 przy k = 3 daje 123456.
Liczenie usuniętych zer jako usunięć. W 100200 przy k = 1 jedynka jest jedynym usuniętym elementem; początkowe zera znikają za darmo, a odpowiedź to 200.
Zwracanie pustego ciągu znaków. 10 przy k = 1 pozostawia samo zero, więc odpowiedź to "0".
Konwertowanie num na liczbę całkowitą. Może mieć 4 × 10^4 cyfr, znacznie więcej, niż obsługuje dowolny typ całkowitoliczbowy, więc porównuj cyfry jako znaki.

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu Remove K Digits?

Przy użyciu stosu monotonicznego algorytm działa w czasie O(n) dla n cyfr: każda cyfra jest umieszczana na stosie raz, a każde usunięcie ze stosu zużywa jedno z k usunięć. Stos przechowuje do n cyfr, więc dodatkowa pamięć wynosi O(n). Ponowne skanowanie od lewej strony przy każdym usunięciu kosztuje O(n·k).

Jak obsługiwać zera wiodące w zadaniu „Remove K Digits”?

Najpierw usuń cyfry, a zera usuń dopiero na końcu. Zero z przodu nie zmienia wartości, więc jego usunięcie nic nie kosztuje: 10200 przy k = 1 staje się 0200, a następnie 200. Jeśli po usunięciu zer nic nie zostanie, zwróć "0".

Czy problem usuwania K cyfr można rozwiązać przy użyciu O(1) dodatkowej pamięci?

Tak, jeśli możesz zmieniać dane wejściowe. Stos nigdy nie zawiera więcej cyfr, niż zostało odczytanych, więc może znajdować się na początku samej tablicy cyfr, z jednym indeksem wskazującym jego wierzchołek. Języki z niemodyfikowalnymi ciągami znaków nadal wymagają jednej kopii cyfr, co daje O(n).

def removeKdigits(num, k):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

num = "4325043"
k = 3

Oczekiwany wynik

"2043"