Remove K Digits

Q: K Basamağı Silme işleminin zaman karmaşıklığı nedir?

Monotonik bir yığınla, n basamak için O(n) zamanda çalışır: her basamak bir kez yığına eklenir ve her çıkarma, k silme işleminden birini tüketir. Yığın en fazla n basamak tutar; dolayısıyla ek alan O(n) olur. Her silme işleminde soldan yeniden tarama yapmak O(n·k) maliyetlidir.

OrtaMonoton yığın Açgözlü

+10

Basamak dizisi olarak yazılmış, negatif olmayan bir sayı olan num ve bir tam sayı k verilir. Tam olarak k basamağı silin ve kalan basamakları özgün sıralarında koruyun; böylece geriye kalan sayı mümkün olduğunca küçük olsun.

Sayıyı başında sıfırlar olmadan bir dize olarak döndürün. Hiçbir şey kalmazsa veya yalnızca sıfırlar kalırsa "0" döndürün.

Fonksiyon

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

numstring: rakam dizisi olarak yazılan sayı
kinteger: kaç basamak silinecek
Döndürürstring: baştaki sıfırlar olmadan, dize olarak bırakabileceğin en küçük sayı

Kısıtlar

1 ≤ num.length ≤ 4 × 10⁴
0 ≤ k ≤ num.length
num yalnızca 0 ile 9 arasındaki rakamları içerir.
num başında sıfır içermez; tek istisna, sayının kendisinin sıfır olduğu durumdur: "0".

Örnekler

Girdi: num = "4325043"k = 3
Çıktı: "2043"
Açıklama: 4'ü ve ilk 3'ü çıkarmak 2'yi başa getirir. 0 başta olamaz: önünde dört basamak vardır ve üç çıkarma hakkın var. Son çıkarma, daha küçük bir 0'ın önünde bulunan 5'i alır.

Girdi: num = "30200"k = 1
Çıktı: "200"
Açıklama: 3'ü çıkarmak 0200 sayısını bırakır ve başındaki sıfır olmadan bu 200 olur. Başka herhangi bir rakamı çıkarmak 3'ü başta bırakır ve 3000 gibi dört basamaklı bir sayı oluşturur.

Girdi: num = "52"k = 2
Çıktı: "0"
Açıklama: Her iki basamak da kaldırılır, böylece geriye hiçbir şey kalmaz ve yanıt "0" olur.

Ek soru

En büyük sayıyı elde etmek için k basamağı kaldıracak şekilde çözümü nasıl değiştirirdin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

En soldaki rakamlar daha ağır basar, bu nedenle sağ komşusundan büyük olan ilk rakam silinmelidir. Sakladığın rakamlardan oluşan bir yığın, bu kuralı tüm dizgeye tek geçişte uygular. Sona kalan silme işlemleri sondan yapılır ve baştaki sıfırlar en son kaldırılır.

Her seferinde bir rakamı sil

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Her seferinde bir rakamı sil: num[i] > num[i+1] koşulunu sağlayan ilk i konumunu bul ve num[i] değerini sil; rakamlar hiç azalmıyorsa son rakamı sil. k kez tekrarla.

Her yanıt n-k rakam içerir; bu yüzden iki yanıtın farklı olduğu ilk konum, hangisinin daha küçük olduğunu belirler. i konumuna kadar rakamlar hiç azalmadığından, daha önceki bir rakamı silmek yerine en az onun kadar büyük bir rakam gelir; daha sonraki bir rakamı silmek ise büyük num[i] değerini yerinde bırakır. num[i] değerini silmek, küçültülebilecek en erken konumu küçültür.

Her silme işleminde soldan başlayarak yeniden tarama yapılır ve sonrasındaki rakamlar kaydırılır; bu nedenle işlem miktarı O(n·k) olur. k = 25,000 iken 40,000 tane 1 üzerinde yapılan taramalar yaklaşık 6.9 × 10^8 rakam okur.

Algoritma

Rakamları, içinden silebileceğin bir listeye kopyala.
k kez tekrarla: soldan başlayıp bir sonraki rakamdan büyük olan ilk rakama ya da son rakama kadar ilerle ve onu sil.
Baştaki sıfırları kaldır ve geriye hiçbir şey kalmazsa "0" döndür.

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"

Korunan rakamların monotonik yığını

Sezgi

Yavaş sürüm num[i] öğesini sildikten sonra, i konumundan önceki rakamlar yine de azalmadığından, bir sonraki silme yalnızca boşluğun önündeki rakamdan başlayabilir. Bir yığın bu öneki tutar: alttan üste doğru azalmayan, korunan rakamları. Yeni bir rakam tepeden küçükse, tepedeki rakam sağ komşusundan, yani yavaş sürümün sileceği rakamdan büyüktür. Onu yığından çıkar, bir silme hakkı kullan ve yeni tepedeki rakam hâlâ büyük olduğu sürece çıkarmaya devam et.

k = 3 için 4325043 üzerinde, 3 rakamı 4'ü, 2 rakamı 3'ü ve 0 rakamı 5'i yığından çıkarır. 4 ve 3 geldikçe yığına eklenir ve sonuç 2043 olur.

Her rakam yığına bir kez eklenir ve her çıkarma k silme hakkından birini kullanır; bu nedenle geçiş O(n) sürer.

Algoritma

Boş bir rakam yığını oluştur.
num içindeki her rakam için: Kalan silme hakkı varsa ve yığının en üstündeki rakam bu rakamdan büyükse, en üsttekini çıkar ve bir silme hakkı kullan. Ardından rakamı yığına ekle.
Döngüden sonra silme hakkı kaldıysa, yığının en üstünden bu sayıda rakamı sil.
Yığını alttan üste doğru oku, baştaki sıfırları atla ve geri kalanını döndür; hiçbir şey kalmadıysa "0" döndür.

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"

Tuzaklar ve uç durumlar

Üstteki rakam yeni rakama eşit olduğunda eleman çıkarmak. k = 1 iken 112 için bu işlem 12 sonucunu verir; doğru cevap 11 olur.
Döngüden sonra kalan çıkarmaları unutmak veya bunları baştan yapmak. Yığın hiç küçülmediğinden, sondaki rakamlar çıkarılır: k = 3 iken 123456789 girdisi 123456 sonucunu verir.
Baştan silinen sıfırları çıkarma olarak saymak. k = 1 iken 100200 için çıkarılan tek rakam 1'dir; baştaki sıfırlar ücretsiz silinir ve cevap 200 olur.
Boş bir dize döndürmek. k = 1 iken 10 girdisinden geriye yalnızca bir sıfır kalır; bu nedenle cevap "0" olur.
num değerini bir tam sayıya dönüştürmek. 4 × 10^4 basamağa sahip olabilir; bu, herhangi bir tam sayı türünün sınırını çok aşar. Bu yüzden basamakları karakter olarak karşılaştırın.

Sıkça sorulan sorular3

K Basamağı Silme işleminin zaman karmaşıklığı nedir?

Monotonik bir yığınla, n basamak için O(n) zamanda çalışır: her basamak bir kez yığına eklenir ve her çıkarma, k silme işleminden birini tüketir. Yığın en fazla n basamak tutar; dolayısıyla ek alan O(n) olur. Her silme işleminde soldan yeniden tarama yapmak O(n·k) maliyetlidir.

Remove K Digits'te baştaki sıfırları nasıl ele alırsınız?

Önce rakamları silin ve sıfırları yalnızca en sonda kaldırın. Baştaki bir sıfır değeri değiştirmez, dolayısıyla silme maliyeti yoktur: k = 1 iken 10200, 0200 olur ve ardından 200 olur. Sıfırları kaldırma işlemi hiçbir şey bırakmazsa "0" döndürün.

Can Remove K Digits, O(1) ek alan kullanarak çözülebilir mi?

Evet, girdiyi değiştirebiliyorsan. Yığın, okuduğun basamak sayısından daha fazla basamak içermez; bu nedenle, tepesini gösteren bir indeksle doğrudan basamak dizisinin başında tutulabilir. Değişmez dizelere sahip dillerde yine de basamakların bir kopyası gerekir; bu da O(n) olur.

def removeKdigits(num, k):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

num = "4325043"
k = 3

Beklenen Çıktı

"2043"