Baseball Game

Q: Beyzbol Oyunu O(1) ek alan kullanılarak çözülebilir mi?

Genel olarak hayır. Bir sayı dizisinin ardından gelen bir "C" girdileri dizisi, sayıları ters sırayla iptal eder; bu nedenle iptal edilip edilmeyeceklerini öğrenene kadar her sayıyı hatırlaman gerekir. Bu, en kötü durumda O(n) bellek gerektirir. Toplamı sürekli güncel tutmak son geçişi ortadan kaldırır, yığını değil.

Q: Baseball Game'de bir sayıyı bir işlemden nasıl ayırt edersin?

Önce girdiyi "+" , "D" ve "C" üç sembolüyle karşılaştır; diğer her şeyi bir tam sayı olarak değerlendir. Dilin ayrıştırıcısıyla dönüştürmek başında eksi işareti olmasını da işler, bu nedenle "-30000" , -30000 olur.

KolayYığın

+10

Alışılmadık bir oyunda puan tutuyorsun. operations listesi soldan sağa okunur ve her girdi puan kaydını değiştirir. "7" veya "-2" gibi bir tam sayı, bu puanı kayda ekler. "+", son iki puanın toplamına eşit bir puan ekler; "D", son puanın iki katına eşit bir puan ekler; "C" ise son puanı kayıttan kalıcı olarak siler.

Son işlemden sonra kayıtta kalan puanların toplamını döndüren, calPoints adlı bir fonksiyon yaz. Boş bir kaydın toplamı 0 olur.

Fonksiyon

calPoints(operations: string-array) → integer

operationsstring-array: işlemler sırasıyla: metin olarak tam sayılar veya "+", "D", "C"
Döndürürinteger: sonunda kayıtta hâlâ bulunan puanların toplamı

Kısıtlar

1 ≤ operations.length ≤ 5000
Her bir girdi "+", "D", "C" veya -3 × 10⁴ ≤ value ≤ 3 × 10⁴ koşulunu sağlayan ondalık biçimde yazılmış bir tam sayıdır.
Her işlem geçerlidir: "+" yalnızca kayıtta en az iki puan olduğunda, "D" ve "C" ise yalnızca en az bir puan olduğunda gelir.
Kayıttaki her puan ve son toplam, 32 bitlik işaretli bir tamsayıya sığar.

Örnekler

Girdi: operations = ["4", "-2", "D", "+", "C", "7"]
Çıktı: 5
Açıklama: Kayıt [4, -2] olacak şekilde büyür, "D" -4 ekler, "+" -2 + -4 = -6 ekler, "C" bu -6 değerini kaldırır ve 7 en son eklenir. [4, -2, -4, 7] kaydının toplamı 5 eder.

Girdi: operations = ["6", "D", "C", "C"]
Çıktı: 0
Açıklama: "D", 6'dan sonra 12 ekler, ardından iki "C" girdisi 12 ve 6'yı kaldırır. Geriye hiçbir şey kalmaz, bu nedenle cevap 0'dır.

Girdi: operations = ["1", "2", "+", "+", "D"]
Çıktı: 21
Açıklama: İki "+" girdisi 1 + 2 = 3 ve ardından 2 + 3 = 5 değerlerini ekler; "D" ise 10 ekler. Kayıt [1, 2, 3, 5, 10] toplamda 21 eder.

Gönderirken +13 gizli test

Ek soru

Sonundaki kaydı toplama eklemeden toplamı döndürebilir misin, böylece iptal işlemi de dahil olmak üzere her işlem O(1) zaman alsın?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Her işlem en son puanlara bakar ve "C" puanları teker teker kaldırabildiği için iptal edilen bir puandan önceki puanlar yeniden en son puanlar olur. Son giren ilk çıkar düzeni tam olarak bir yığındır. Her yeni puanı yığına ekle, "C" için yığından çıkar ve "D" ile "+" için en üstteki bir veya iki girdiyi oku.

Kaydı bir yığın üzerinde oluşturun, sonunda toplayın

Sezgi

Kaydı, en yeni puanın listenin sonunda yer aldığı bir liste olarak tut. Böylece her işlem listenin yalnızca sonundaki öğeyi etkiler: bir tam sayı eklenir, "D" son öğenin iki katını ekler, "+" son iki öğenin toplamını ekler ve "C" son öğeyi çıkarır.

Yığının neden yeterli olduğu: "C" işleminden sonra, en yeni ikinci puan en yeni puan olur ve ardından gelen "D" veya "+" işleminin okuması gereken puan da budur. Öğeyi çıkarmak bunu zahmetsizce sağlar. İlk örnekte "C", -6 değerini çıkarır ve [4, -2, -4] değerlerini bırakır; dolayısıyla daha sonra gelecek herhangi bir "+" işlemi -2 + -4 toplamını yeniden hesaplar.

İşlemler sona erdiğinde liste, hesaba katılan puanları tam olarak içerir. Bunları topla. Her işlem O(1), son toplam ise O(n) olduğundan, yığın için O(n) alan kullanımıyla tüm işlem O(n) zamanda tamamlanır.

Algoritma

Boş bir record yığınıyla başlayın.
"+" için en üstteki iki girdinin toplamını yığına ekleyin. "D" için en üstteki girdinin iki katını yığına ekleyin.
"C" için en üstteki girdiyi yığından çıkarın.
Aksi hâlde girdi bir sayıdır: metni bir tam sayıya dönüştürün ve yığına ekleyin.
Yığında kalan her şeyin toplamını döndürün.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    for op in operations:
        if op == "+":
            record.append(record[-1] + record[-2])
        elif op == "D":
            record.append(2 * record[-1])
        elif op == "C":
            record.pop()
        else:
            record.append(int(op))
    return sum(record)

Çalışan toplamlı yığın

Sezgi

Yığının üzerinden yapılan son döngü, kaçınabileceğin fazladan bir iştir. Yığının toplamına her zaman eşit olan bir total değişkeni tut. Her ekleme yeni puanı total'a ekler ve her "C", çıkardığı puanı total'dan çıkarır.

Yığın hâlâ gerekli. İptal işlemi, toplamdan hangi puanı geri çıkaracağını bilmelidir; "+" ve "D" de herhangi bir iptal işleminden sonra en son puanları bilmelidir. İlk örnekte toplam 4, 2, -2, -8 değerlerini alır; ardından iptal işlemi -6'yı geri çıkararak toplamı -2 yapar ve son 7 toplamı 5'e getirir.

Tek geçişte zaman karmaşıklığı O(n)'dir ve yanıt, işlemlerin herhangi bir önekinin ardından hazır olur; puanlar canlı olarak geldiğinde bu önemlidir. Alan karmaşıklığı O(n)'dir: n işlemin tümü kayıtta kalan sayılar olabilir.

Algoritma

Boş bir record yığını ve total = 0 ile başlayın.
"C" için en üstteki puanı çıkarın ve total değerinden çıkarın.
Aksi hâlde yeni puanı hesaplayın: "+" için en üstteki iki puanın toplamını, "D" için en üstteki puanın iki katını veya sayının kendisini kullanın.
Yeni puanı yığına ekleyin ve total değerine ekleyin.
total değerini döndürün.

def calPoints(operations):
    record = []  # the scores that still count, newest last
    total = 0    # always the sum of record
    for op in operations:
        if op == "C":
            total -= record.pop()  # the cancelled score leaves the total too
            continue
        if op == "+":
            score = record[-1] + record[-2]
        elif op == "D":
            score = 2 * record[-1]
        else:
            score = int(op)
        record.append(score)
        total += score
    return total

Tuzaklar ve uç durumlar

Kurallar kısa olduğundan, hataların çoğu yanlış puanı okumaktan veya metni ayrıştırmaktan kaynaklanır.

Yalnızca toplamı ve son iki puanı tutmak. "C" işleminden sonra bu iki puandan önceki puana ihtiyaç duyarsın; bu yüzden bir iptal işleminin ardından gelen "+" eski değerleri okur. Yığının tamamını tut.
İptal edilen puanların toplamdan çıkarıldığını unutmak. Toplamı sürekli güncelliyorsan, "C" çıkarılan puanı yok saymamalı, toplamdan düşmelidir.
Negatif puanları elle ayrıştırırken işareti atlamak. Dilin tamsayı ayrıştırıcısını kullan; bu ayrıştırıcı "-2" ifadesini -2 olarak okur.
Bir girdinin sayı olup olmadığına karar vermek için rakam olup olmadığını kontrol etmek. "-5" eksi işaretiyle başlar; üç sembolü kontrol et ve diğer her şeyi sayı olarak ele al.
Cevabın pozitif olduğunu varsaymak. Negatif puanlar ve iptaller toplamı negatif bırakabilir ya da tüm puanlar iptal edildiyse sonuç 0 olabilir.

Sıkça sorulan sorular4

Beyzbol Oyunu'nun zaman karmaşıklığı nedir?

Her işlem, yığının en üstünde sabit miktarda iş yapar; bu nedenle n işlemi işlemek O(n) zaman alır. Yığındaki değerleri en sonda toplamak en fazla bir O(n) daha gerektirir; çalışan bir toplam kullanmak bu gereksinimi bile ortadan kaldırır. İşlemlerin çoğu puan ekliyorsa yığın O(n) alan kullanır.

Baseball Game için yığın neden doğru veri yapısıdır?

Her kural en son puanları okur veya kaldırır ve bir iptal, önceki puanı ortaya çıkarır. Bu, son giren ilk çıkar sırasıdır; yığın da sana O(1) ekleme, çıkarma ve tepeyi görme işlemlerini bu sırayla sunar. Yalnızca sonundan kullanılan sıradan bir dizi veya liste, her dilde yığın işlevi görür.

Beyzbol Oyunu O(1) ek alan kullanılarak çözülebilir mi?

Genel olarak hayır. Bir sayı dizisinin ardından gelen bir "C" girdileri dizisi, sayıları ters sırayla iptal eder; bu nedenle iptal edilip edilmeyeceklerini öğrenene kadar her sayıyı hatırlaman gerekir. Bu, en kötü durumda O(n) bellek gerektirir. Toplamı sürekli güncel tutmak son geçişi ortadan kaldırır, yığını değil.

Baseball Game'de bir sayıyı bir işlemden nasıl ayırt edersin?

Önce girdiyi "+", "D" ve "C" üç sembolüyle karşılaştır; diğer her şeyi bir tam sayı olarak değerlendir. Dilin ayrıştırıcısıyla dönüştürmek başında eksi işareti olmasını da işler, bu nedenle "-30000", -30000 olur.

Python

def calPoints(operations):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

operations = ["4", "-2", "D", "+", "C", "7"]

Beklenen