โจทย์
A seating chart for a huge stadium is mostly empty, so storing every cell wastes memory. A SparseGrid stores only the cells that hold a non-zero value; every other cell is 0. The grid starts with rows rows, cols columns and no stored cells. Process these operations in order:
set r c v: cell (r, c) becomesv. Setting 0 removes the cell from storage.get r c: output the value of cell (r, c).count: output how many cells are non-zero.row_sum r: output the sum of the values in rowr.width: output the current number of columns.remove_col c: delete columnc. Its cells disappear, every cell to its right moves one column left, and the grid has one column fewer.
Rows and columns are numbered from 0, and every index is inside the grid at the time of the operation.
Implement sparse_grid(rows, cols, operations).
Input
rows: The number of rows.
cols: The starting number of columns.
operations: The operations, processed in order.
Output
Return the outputs of get, count, row_sum and width in the order they happen.
เงื่อนไข
1 ≤ rows ≤ 1,000,000
1 ≤ cols ≤ 1,000,000
0 ≤ number of operations ≤ 1,000
−1,000,000 ≤ v ≤ 1,000,000
ตัวอย่าง
อินพุต:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]
ผลลัพธ์ที่คาดหวัง:
expected = [7, 3, 0]
อินพุต:
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"};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {7, 3, 0};
อินพุต:
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"};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {7, 3, 0};
คำอธิบาย
Row 0 holds 5 and 2, so its sum is 7; three cells are stored; (1, 1) was never set, so it is 0.
อินพุต:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]
ผลลัพธ์ที่คาดหวัง:
expected = [9, 2, 1]
อินพุต:
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"};
ผลลัพธ์ที่คาดหวัง:
std::vector<long long> expected = {9, 2, 1};
อินพุต:
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"};
ผลลัพธ์ที่คาดหวัง:
long[] expected = new long[] {9, 2, 1};
คำอธิบาย
Removing column 0 deletes the 4 and slides the 9 from column 2 to column 1, so get 1 1 is 9, the width is 2 and one cell is left.
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
A map from (row, column) to value works well; a missing key means 0.
คำใบ้ 2
Setting a cell to 0 should delete it so `count` stays right.
คำใบ้ 3
When a column is removed, rebuild the map: drop that column and shift larger column numbers down by one.
ความซับซ้อนที่คาดหวัง
O(q × s) time, O(s) extra space, s = stored cells
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน