Baseball Game

+10

Bạn ghi điểm cho một trò chơi khác thường. Đọc operations từ trái sang phải; mỗi mục sẽ thay đổi bảng điểm. Một số nguyên như "7" hoặc "-2" sẽ thêm số điểm đó. "+" thêm tổng của hai điểm mới nhất, "D" thêm gấp đôi điểm mới nhất, còn "C" xóa hẳn điểm mới nhất.

Viết hàm có tên calPoints để trả về tổng điểm còn lại trên bảng sau thao tác cuối cùng. Bảng điểm trống có tổng bằng 0.

Hàm

calPoints(operations: string-array) → integer

operationsstring-array: các phép toán theo thứ tự: số nguyên dưới dạng văn bản hoặc "+", "D", "C"
Trả vềinteger: tổng điểm vẫn còn được ghi nhận vào cuối

Ràng buộc

1 ≤ operations.length ≤ 5000
Mỗi mục là "+", "D", "C" hoặc một số nguyên viết ở dạng thập phân, thỏa mãn -3 × 10⁴ ≤ value ≤ 3 × 10⁴.
Mọi phép toán đều hợp lệ: "+" chỉ xuất hiện khi bản ghi có ít nhất hai điểm, "D" và "C" chỉ xuất hiện khi bản ghi có ít nhất một điểm.
Mọi điểm số trong bản ghi và tổng cuối cùng đều nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: operations = ["4", "-2", "D", "+", "C", "7"]
Đầu ra: 5
Giải thích: Bản ghi trở thành [4, -2], "D" thêm -4, "+" thêm -2 + -4 = -6, "C" xóa -6 đó, và 7 được thêm vào cuối. Bản ghi [4, -2, -4, 7] có tổng bằng 5.

Đầu vào: operations = ["6", "D", "C", "C"]
Đầu ra: 0
Giải thích: "D" thêm 12 sau 6, rồi hai mục "C" xóa 12 và 6. Không còn gì, nên đáp án là 0.

Đầu vào: operations = ["1", "2", "+", "+", "D"]
Đầu ra: 21
Giải thích: Hai mục "+" cộng 1 + 2 = 3 rồi 2 + 3 = 5, còn "D" cộng thêm 10. Bản ghi [1, 2, 3, 5, 10] có tổng là 21.

Câu hỏi mở rộng

Bạn sẽ thêm thao tác hoàn tác lệnh "C" gần nhất như thế nào, để khôi phục điểm đã bị hủy trong thời gian O(1)?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi thao tác đọc điểm số mới nhất, và "C" có thể lấy từng điểm ra một, nên các điểm số cũ hơn lại trở thành điểm số mới nhất. Đó là vào sau, ra trước: thêm từng điểm số mới vào, lấy ra khi gặp "C", rồi đọc một hoặc hai điểm trên cùng cho "D" và "+".

Tạo bản ghi trên ngăn xếp, rồi tính tổng ở cuối

Ý tưởng

Giữ bảng điểm dưới dạng một danh sách, với điểm mới nhất ở cuối, để mỗi thao tác chỉ tác động đến phần cuối. Sau "C", điểm mới thứ hai trở thành điểm mới nhất, và thao tác "D" hoặc "+" sau đó phải đọc điểm này; thao tác lấy phần tử cuối ra sẽ làm lộ điểm đó. Trong ví dụ đầu tiên, "C" lấy -6 ra và để lại [4, -2, -4].

Khi các thao tác đã hết, danh sách chứa chính xác những điểm được tính, vì vậy hãy cộng chúng lại: thời gian O(n) và bộ nhớ O(n).

Thuật toán

Bắt đầu với một ngăn xếp record rỗng.
Với "+", đẩy tổng của hai phần tử trên cùng vào ngăn xếp. Với "D", đẩy giá trị gấp đôi phần tử trên cùng vào ngăn xếp.
Với "C", lấy phần tử trên cùng ra khỏi ngăn xếp.
Nếu không, mục đó là một số: chuyển văn bản thành số nguyên rồi đẩy vào ngăn xếp.
Trả về tổng của tất cả phần tử còn lại trên ngăn xếp.

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)

Ngăn xếp với tổng đang chạy

Ý tưởng

Giữ total bằng tổng các điểm trong ngăn xếp: mỗi lần thêm vào ngăn xếp, cộng điểm mới; mỗi lần gặp "C", trừ điểm vừa lấy ra. Ngăn xếp vẫn cần thiết, vì thao tác hủy phải biết cần trừ điểm nào. Trong ví dụ đầu tiên, tổng lần lượt là 4, 2, -2, -8; thao tác hủy lấy lại -6, đưa tổng về -2, rồi 7 nâng tổng lên 5.

Chỉ cần duyệt một lượt với thời gian O(n), và có thể tính được đáp án sau bất kỳ tiền tố nào của các thao tác. Bộ nhớ cần dùng là O(n), vì mọi thao tác đều có thể là một số được giữ lại.

Thuật toán

Bắt đầu với một ngăn xếp trống record và total = 0.
Với "C", lấy điểm trên cùng ra khỏi ngăn xếp và trừ điểm đó khỏi total.
Nếu không, hãy tính điểm mới: tổng của hai điểm trên cùng với "+", gấp đôi điểm trên cùng với "D", hoặc chính số nguyên đó.
Đẩy điểm mới vào ngăn xếp và cộng điểm đó vào total.
Trả về 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

Lỗi thường gặp và trường hợp biên

Chỉ giữ tổng đang tính và hai điểm gần nhất. Trong ["1", "2", "3", "C", "+"], "+" cần 1 và 2, nhưng cửa sổ gồm hai điểm đã mất 1.
Không trừ điểm đã hủy khỏi tổng đang tính. Trong ví dụ thứ hai, cách này khiến kết quả là 18 thay vì 0.
Cho rằng một mục là số nếu mục đó có chữ số. "-2" bắt đầu bằng dấu trừ; hãy so sánh với ba ký hiệu và phân tích mọi thứ khác bằng trình phân tích số nguyên của ngôn ngữ.
Cho rằng đáp án luôn dương. ["-3", "D"] có tổng là -9.

Câu hỏi thường gặp3

Độ phức tạp thời gian của trò chơi bóng chày là bao nhiêu?

Mỗi thao tác thực hiện một lượng công việc không đổi ở đỉnh ngăn xếp, nên n thao tác mất O(n) thời gian. Ngăn xếp cần O(n) bộ nhớ khi phần lớn thao tác thêm điểm.

Vì sao ngăn xếp là cấu trúc dữ liệu phù hợp cho trò chơi bóng chày?

Mỗi quy tắc đọc hoặc xóa điểm số mới nhất, còn thao tác hủy sẽ hiển thị điểm số trước đó. Đây là nguyên tắc vào sau, ra trước, được ngăn xếp hỗ trợ với thao tác đẩy, lấy ra và xem phần tử trên cùng có độ phức tạp O(1). Mảng chỉ dùng ở cuối sẽ hoạt động như một ngăn xếp.

Trận đấu bóng chày có thể được giải bằng bộ nhớ phụ O(1) không?

Không phải trong mọi trường hợp. Một dãy số theo sau bởi một dãy phần tử "C" sẽ hủy các số theo thứ tự ngược lại, vì vậy bạn phải ghi nhớ từng số cho đến khi biết số đó có bị hủy hay không. Trong trường hợp xấu nhất, việc này cần bộ nhớ O(n).

def calPoints(operations):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi