Baseball Game

Q: Baseball Game 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. En kötü durumda bu, O(n) bellek gerektirir.

KolayYığın

+10

Sıradışı bir oyunda puan tutuyorsun. operations listesini soldan sağa oku; her girdi bir puan kaydını değiştirir. "7" veya "-2" gibi bir tam sayı, o puanı ekler. "+" son iki puanın toplamını, "D" son puanın iki katını ekler ve "C" son puanı 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ırayla: 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 ondalık biçimde yazılmış, -3 × 10⁴ ≤ value ≤ 3 × 10⁴ koşulunu sağlayan bir tam sayıdır.
Her işlem geçerlidir: kayıt en az iki puan içerdiğinde yalnızca "+" gelir; en az bir puan içerdiğinde ise yalnızca "D" ve "C" gelir.
Kaydın içindeki her puan ve 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 son olarak 7 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. Hiçbir şey kalmaz, bu yüzden cevap 0'dır.

Girdi: operations = ["1", "2", "+", "+", "D"]
Çıktı: 21
Açıklama: İki "+" girişi 1 + 2 = 3 ve ardından 2 + 3 = 5 işlemlerini yapar, "D" ise 10 ekler. [1, 2, 3, 5, 10] kaydının toplamı 21 eder.

Ek soru

En son "C" işlemini geri alıp iptal edilen puanı geri koyan bir işlemi O(1) zamanda nasıl eklersin?

İ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 puanları okur ve "C" bunları teker teker kaldırabilir; böylece daha eski puanlar yeniden en son puanlar olur. Bu, son giren ilk çıkar ilkesidir: her yeni puanı yığına ekle, "C" geldiğinde en üsttekini çıkar ve "D" ile "+" için en üstteki bir veya iki puanı oku.

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

Sezgi

Kaydı, en yeni puan sonda olacak şekilde bir liste olarak tut; böylece her işlem yalnızca listenin sonunu etkiler. "C" işleminden sonra en yeni ikinci puan yeni en güncel puan olur ve daha sonra gelen "D" veya "+" işlemi bu puanı okumalıdır; listeden son elemanı çıkarmak onu görünür kılar. İlk örnekte "C", -6 değerini çıkarır ve geriye [4, -2, -4] kalır.

İşlemler bittiğinde listede tam olarak hesaba katılacak puanlar bulunur; bu yüzden bunları topla: O(n) zaman ve O(n) alan.

Algoritma

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

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

total değerini yığının toplamına eşit tut: her ekleme yeni puanı ekler ve her "C", yığından çıkardığı puanı çıkarır. Yığın kalmalı, çünkü iptal işleminin hangi puanı kaldıracağını bilmesi gerekir. İlk örnekte toplam 4, 2, -2, -8 şeklinde ilerler; iptal işlemi -6 değerini geri çıkararak toplamı -2 yapar ve 7 toplamı 5'e getirir.

Bu, O(n) zamanda tek geçişte yapılır ve işlemlerin herhangi bir önekinden sonra yanıt hazırdır. Her işlem kalıcı olan bir sayı olabileceğinden, alan kullanımı O(n)'dir.

Algoritma

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

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

Yalnızca toplamı ve son iki skoru tutmak. ["1", "2", "3", "C", "+"] içinde "+" için 1 ve 2 gerekir; iki skorlu bir pencerede ise 1 kaybolmuştur.
İptal edilen bir skoru toplamdan çıkarmamak. İkinci örnekte bu, toplamın 0 yerine 18 olmasına yol açar.
Bir girdinin sayı olduğuna, bir rakam içerip içermediğini kontrol ederek karar vermek. "-2" eksi işaretiyle başlar; üç sembolle karşılaştır ve geri kalan her şeyi dilin tamsayı ayrıştırıcısıyla ayrıştır.
Yanıtın pozitif olduğunu varsaymak. ["-3", "D"] toplamı -9 eder.

Sıkça sorulan sorular3

Baseball Game'in zaman karmaşıklığı nedir?

Her işlem yığının tepesinde sabit miktarda iş yapar, bu nedenle n işlem O(n) zaman alır. İşlemlerin çoğu puan eklediğinde yığın O(n) alan kullanır.

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

Her kural en son puanları okur veya kaldırır ve iptal işlemi, onun öncesindeki puanı ortaya çıkarır. Bu, son giren ilk çıkar düzenidir; bir yığın bunu O(1) push, pop ve peek işlemleriyle sağlar. Yalnızca sonundan yararlanılan bir dizi, yığın olarak iş görür.

Baseball Game 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. En kötü durumda bu, O(n) bellek gerektirir.

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

Test #1

Test #2

Test #3

Argüman

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

Beklenen Çıktı