Baseball Game

+10

Kamu mencatat skor untuk sebuah permainan yang tidak biasa. Baca operations dari kiri ke kanan; setiap entri mengubah catatan skor. Bilangan bulat seperti "7" atau "-2" menambahkan skor tersebut. "+" menambahkan jumlah dua skor terakhir, "D" menambahkan dua kali skor terakhir, dan "C" menghapus skor terakhir secara permanen.

Tulis fungsi bernama calPoints yang mengembalikan jumlah skor yang tersisa pada catatan setelah operasi terakhir. Catatan kosong memiliki jumlah 0.

Fungsi

calPoints(operations: string-array) → integer

operationsstring-array: operasi secara berurutan: bilangan bulat sebagai teks, atau "+", "D", "C"
Mengembalikaninteger: jumlah skor yang masih tercatat pada akhir

Batasan

1 ≤ operations.length ≤ 5000
Setiap entri berupa "+", "D", "C", atau bilangan bulat yang ditulis dalam desimal dengan -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Setiap operasi valid: "+" hanya muncul saat catatan memiliki setidaknya dua skor, "D" dan "C" hanya saat catatan memiliki setidaknya satu skor.
Setiap skor pada catatan dan jumlah akhir muat dalam bilangan bulat bertanda 32-bit.

Contoh

Input: operations = ["4", "-2", "D", "+", "C", "7"]
Output: 5
Penjelasan: Catatan bertambah menjadi [4, -2], "D" menambahkan -4, "+" menambahkan -2 + -4 = -6, "C" menghapus -6 tersebut, dan 7 ditambahkan terakhir. Jumlah catatan [4, -2, -4, 7] adalah 5.

Input: operations = ["6", "D", "C", "C"]
Output: 0
Penjelasan: "D" menambahkan 12 setelah 6, lalu dua entri "C" menghapus 12 dan 6. Tidak ada yang tersisa, jadi jawabannya adalah 0.

Input: operations = ["1", "2", "+", "+", "D"]
Output: 21
Penjelasan: Dua entri "+" menjumlahkan 1 + 2 = 3 lalu 2 + 3 = 5, dan "D" menambahkan 10. Catatan [1, 2, 3, 5, 10] berjumlah 21.

Pertanyaan lanjutan

Bagaimana cara menambahkan operasi yang membatalkan "C" terbaru dan mengembalikan skor yang dibatalkan, dalam waktu O(1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap operasi membaca skor terbaru, dan "C" dapat menghapusnya satu per satu, sehingga skor yang lebih lama kembali menjadi skor terbaru. Urutannya adalah yang terakhir masuk, yang pertama keluar: push setiap skor baru, pop saat "C", dan baca satu atau dua skor teratas untuk "D" dan "+".

Susun catatan di atas stack, jumlahkan semuanya di akhir

Intuisi

Simpan catatan sebagai list dengan skor terbaru di bagian akhir, sehingga setiap operasi hanya menyentuh bagian akhir. Setelah "C", skor terbaru kedua menjadi skor terbaru, dan "D" atau "+" berikutnya harus membacanya; menghapus elemen teratas akan menampilkannya. Pada contoh pertama, "C" menghapus -6 dan menyisakan [4, -2, -4].

Saat operasi habis, list berisi tepat skor yang dihitung, jadi jumlahkan semuanya: waktu O(n) dan ruang O(n).

Algoritma

Mulai dengan stack kosong record.
Untuk "+", masukkan jumlah dua entri teratas. Untuk "D", masukkan dua kali nilai entri teratas.
Untuk "C", keluarkan entri teratas.
Jika tidak, entri tersebut adalah angka: ubah teks menjadi bilangan bulat dan masukkan.
Kembalikan jumlah semua nilai yang tersisa di stack.

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)

Stack dengan total berjalan

Intuisi

Jaga total agar tetap sama dengan jumlah nilai dalam stack: setiap push menambahkan skor baru dan setiap "C" mengurangi skor yang dikeluarkan. Stack harus tetap ada, karena operasi pembatalan perlu mengetahui skor mana yang harus dikeluarkan. Dalam contoh pertama, total berubah menjadi 4, 2, -2, -8, operasi pembatalan mengeluarkan kembali -6 sehingga total menjadi -2, lalu 7 membuatnya menjadi 5.

Ini hanya satu kali penelusuran dengan waktu O(n), dan jawabannya siap setelah setiap prefiks operasi. Penggunaan ruangnya O(n), karena setiap operasi bisa berupa angka yang tetap tersimpan.

Algoritma

Mulai dengan stack kosong record dan total = 0.
Untuk "C", keluarkan skor teratas dan kurangi total dengan skor tersebut.
Jika tidak, hitung skor baru: jumlah dua skor teratas untuk "+", dua kali skor teratas untuk "D", atau bilangan bulat itu sendiri.
Masukkan skor baru ke stack dan tambahkan ke total.
Kembalikan total.

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

Jebakan dan kasus tepi

Hanya menyimpan jumlah berjalan dan dua skor terakhir. Dalam ["1", "2", "3", "C", "+"], "+" membutuhkan 1 dan 2, tetapi jendela dua skor sudah tidak menyimpan 1.
Tidak mengurangi skor yang dibatalkan dari jumlah berjalan. Dalam contoh kedua, hasilnya menjadi 18, bukan 0.
Menentukan bahwa sebuah entri adalah angka dengan memeriksa apakah entri itu berisi digit. "-2" diawali tanda minus. Bandingkan dengan tiga simbol tersebut, lalu uraikan yang lainnya menggunakan parser integer bahasa tersebut.
Menganggap jawabannya positif. ["-3", "D"] menghasilkan jumlah -9.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Baseball Game?

Setiap operasi melakukan pekerjaan konstan di bagian atas stack, sehingga n operasi membutuhkan waktu O(n). Stack membutuhkan ruang O(n) saat sebagian besar operasi menambahkan skor.

Mengapa stack menjadi struktur data yang tepat untuk Baseball Game?

Setiap aturan membaca atau menghapus skor terbaru, dan pembatalan menampilkan skor sebelumnya. Prinsipnya adalah yang terakhir masuk, pertama keluar, dan stack menerapkannya dengan operasi push, pop, dan peek berkompleksitas O(1). array yang hanya digunakan pada bagian akhirnya berfungsi sebagai stack.

Apakah Baseball Game dapat diselesaikan dengan ruang ekstra O(1)?

Tidak secara umum. Deretan angka yang diikuti deretan entri "C" membatalkan angka-angka tersebut dalam urutan terbalik, jadi kamu harus mengingat setiap angka sampai kamu tahu apakah angka itu akan dibatalkan. Dalam kasus terburuk, hal itu membutuhkan memori O(n).

def calPoints(operations):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan