Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Lưới thưa

Lưu một lưới gần như trống dưới dạng các ô khác 0 và xử lý các thao tác lấy giá trị, đếm, tính tổng hàng và xóa cột.

Bạn sẽ học được gì

  • Chỉ lưu các ô khác 0
  • Cập nhật các khóa đã lưu khi cột bị dịch
  • Trả lời truy vấn mà không cần dựng toàn bộ lưới

Đề bài

Xem bản gốc (English)

Sơ đồ chỗ ngồi của một sân vận động khổng lồ hầu như trống, nên lưu từng ô một thì rất phí bộ nhớ. SparseGrid chỉ lưu những ô có giá trị khác 0; mọi ô khác đều coi là 0. Ban đầu lưới có rows hàng, cols cột và chưa lưu ô nào. Hãy xử lý lần lượt các thao tác sau:

  • set r c v: ô (r, c) nhận giá trị v. Gán 0 nghĩa là xóa ô đó khỏi bộ nhớ lưu trữ.
  • get r c: cho kết quả là giá trị của ô (r, c).
  • count: cho kết quả là số ô khác 0.
  • row_sum r: cho kết quả là tổng các giá trị trong hàng r.
  • width: cho kết quả là số cột hiện tại.
  • remove_col c: xóa cột c. Các ô của cột đó biến mất, mọi ô bên phải dịch sang trái một cột, và lưới bớt đi một cột.

Hàng và cột được đánh số từ 0, và mọi chỉ số đều nằm trong lưới tại thời điểm thực hiện thao tác.

Hãy viết sparse_grid(rows, cols, operations).

Đầu vào

rows: Số hàng.

cols: Số cột ban đầu.

operations: Các thao tác, xử lý theo thứ tự.

Đầu ra

Trả về kết quả của get, count, row_sum và width theo thứ tự chúng xảy ra.

Ràng buộc

1 ≤ rows ≤ 1,000,000

1 ≤ cols ≤ 1,000,000

0 ≤ số thao tác ≤ 1,000

−1,000,000 ≤ v ≤ 1,000,000

Ví dụ

Ví dụ 1
Đầu vào:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]

Kết quả mong đợi:
expected = [7, 3, 0]
Đầu vào:
long long rows = 3;
long long cols = 4;
std::vector<std::string> operations = {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

Kết quả mong đợi:
std::vector<long long> expected = {7, 3, 0};
Đầu vào:
long rows = 3;
long cols = 4;
string[] operations = new string[] {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

Kết quả mong đợi:
long[] expected = new long[] {7, 3, 0};

Giải thích

Hàng 0 chứa 5 và 2 nên tổng là 7; có ba ô được lưu; ô (1, 1) chưa từng được gán nên bằng 0.

Ví dụ 2
Đầu vào:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]

Kết quả mong đợi:
expected = [9, 2, 1]
Đầu vào:
long long rows = 2;
long long cols = 3;
std::vector<std::string> operations = {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

Kết quả mong đợi:
std::vector<long long> expected = {9, 2, 1};
Đầu vào:
long rows = 2;
long cols = 3;
string[] operations = new string[] {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

Kết quả mong đợi:
long[] expected = new long[] {9, 2, 1};

Giải thích

Xóa cột 0 làm mất số 4 và đẩy số 9 từ cột 2 sang cột 1, nên get 1 1 cho 9, độ rộng là 2 và chỉ còn một ô.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Một map từ (hàng, cột) sang giá trị là lựa chọn tốt; khóa không tồn tại nghĩa là 0.

Gợi ý 2

Gán 0 cho một ô thì nên xóa ô đó để `count` luôn đúng.

Gợi ý 3

Khi xóa một cột, hãy dựng lại map: bỏ các ô của cột đó và giảm số cột của các ô ở bên phải đi một.

Độ phức tạp mong đợi

thời gian O(q × s), bộ nhớ phụ O(s), với s là số ô được lưu

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.