โจทย์
ผังที่นั่งของสนามกีฬาขนาดใหญ่มากส่วนใหญ่ว่างเปล่า การเก็บทุกช่องจึงเปลืองหน่วยความจำ SparseGrid เก็บเฉพาะช่องที่มีค่าไม่เป็นศูนย์ ส่วนช่องอื่นทั้งหมดมีค่าเป็น 0 ตารางเริ่มต้นด้วย rows แถว cols คอลัมน์ และยังไม่มีช่องใดถูกเก็บไว้ ให้ประมวลผลคำสั่งต่อไปนี้ตามลำดับ
set r c v: ช่อง (r, c) มีค่าเป็นvการตั้งค่าเป็น 0 จะลบช่องนั้นออกจากที่เก็บget r c: แสดงค่าของช่อง (r, c)count: แสดงจำนวนช่องที่ไม่เป็นศูนย์row_sum r: แสดงผลรวมของค่าในแถวrwidth: แสดงจำนวนคอลัมน์ในปัจจุบันremove_col c: ลบคอลัมน์cช่องในคอลัมน์นั้นหายไป ทุกช่องทางขวาของมันเลื่อนไปทางซ้ายหนึ่งคอลัมน์ และตารางมีคอลัมน์ลดลงหนึ่งคอลัมน์
แถวและคอลัมน์นับเริ่มจาก 0 และทุกดัชนีอยู่ภายในตาราง ณ เวลาที่ทำคำสั่งนั้น
จงเขียน sparse_grid(rows, cols, operations)
อินพุต
rows: จำนวนแถว
cols: จำนวนคอลัมน์เริ่มต้น
operations: คำสั่งต่าง ๆ ซึ่งประมวลผลตามลำดับ
เอาต์พุต
คืนค่าผลลัพธ์ของ get, count, row_sum และ width ตามลำดับที่เกิดขึ้น
เงื่อนไข
1 ≤ rows ≤ 1,000,000
1 ≤ cols ≤ 1,000,000
0 ≤ จำนวนคำสั่ง ≤ 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};
คำอธิบาย
แถว 0 มี 5 และ 2 ผลรวมจึงเป็น 7 มีช่องที่เก็บไว้สามช่อง และ (1, 1) ไม่เคยถูกตั้งค่า จึงเป็น 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};
คำอธิบาย
การลบคอลัมน์ 0 ทำให้ 4 หายไป และ 9 จากคอลัมน์ 2 เลื่อนมาอยู่คอลัมน์ 1 ดังนั้น get 1 1 ได้ 9 ความกว้างเป็น 2 และเหลือหนึ่งช่อง
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ใช้ map ที่จับคู่ (แถว, คอลัมน์) กับค่าได้ดี ถ้าไม่มีคีย์นั้นแปลว่าเป็น 0
คำใบ้ 2
การตั้งค่าช่องเป็น 0 ควรลบช่องนั้นทิ้ง เพื่อให้ `count` ถูกต้อง
คำใบ้ 3
เมื่อลบคอลัมน์ ให้สร้าง map ใหม่ โดยทิ้งคอลัมน์นั้นและลดหมายเลขคอลัมน์ที่มากกว่าลงหนึ่ง
ความซับซ้อนที่คาดหวัง
เวลา O(q × s), หน่วยความจำเพิ่ม O(s) โดย s คือจำนวนช่องที่เก็บไว้
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน