Đề bài
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àngr.width: cho kết quả là số cột hiện tại.remove_col c: xóa cộtc. 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ụ
Đầ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.
Đầ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.