โจทย์
หนังสือปริศนาเล่มหนึ่งแสดงสมาชิกสามตัวแรกของตระกูลแพทเทิร์น แล้วให้ผู้อ่านหาตัวที่เหลือเอง:
n = 1 n = 2 n = 3
A BBB CCCCC
BAB CBBBC
BBB CBABC
CBBBC
CCCCCลองพิจารณารูปเหล่านี้ก่อนอ่านต่อ แล้วดูว่าบอกกฎได้หรือไม่ กฎที่เขียนอย่างชัดเจนคือ สมาชิกลำดับที่ n เป็นสี่เหลี่ยมจัตุรัสที่มี 2n − 1 แถว แต่ละแถวยาว 2n − 1 ตัวอักษรโดยไม่มีช่องว่าง ให้นับแถวและคอลัมน์เริ่มจาก 0 และให้จุดศูนย์กลางอยู่ที่ตำแหน่ง n − 1 ช่องที่แถว r คอลัมน์ c แสดงตัวอักษรที่อยู่ถัดจาก A ไป d ตำแหน่งในลำดับตัวอักษร โดย d = max(|r − (n − 1)|, |c − (n − 1)|) คือจำนวนวงที่ช่องนั้นอยู่ห่างจากจุดศูนย์กลาง ดังนั้นจุดศูนย์กลางคือ A วงที่ล้อมรอบคือ B และขอบนอกสุดคือตัวอักษรตัวที่ n
จงเขียน decode_the_pattern(n)
อินพุต
n: ลำดับของสมาชิกที่ต้องการสร้าง (ไม่เกิน 26 ตัวอักษรจึงไม่มีทางเลยเกิน Z)
เอาต์พุต
คืนค่าทั้ง 2n − 1 แถวเรียงจากบนลงล่าง ถ้า n เป็น 0 ให้คืนค่าลิสต์ว่าง
เงื่อนไข
0 ≤ n ≤ 26
ตัวอย่าง
อินพุต:
n = 2
ผลลัพธ์ที่คาดหวัง:
expected = ["BBB", "BAB", "BBB"]
อินพุต:
long long n = 2;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"BBB", "BAB", "BBB"};
อินพุต:
long n = 2;
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"BBB", "BAB", "BBB"};
คำอธิบาย
มีเพียงจุดศูนย์กลาง (1, 1) ที่ห่าง 0 วง ช่องอื่นทั้งหมดห่าง 1 วง: ["BBB", "BAB", "BBB"]
อินพุต:
n = 4
ผลลัพธ์ที่คาดหวัง:
expected = ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
อินพุต:
long long n = 4;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
อินพุต:
long n = 4;
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"};
คำอธิบาย
ช่องที่ขอบอยู่ห่างออกไป 3 วง (D) และแถว 3 คือแถวกลาง: ["DDDDDDD", "DCCCCCD", "DCBBBCD", "DCBABCD", "DCBBBCD", "DCCCCCD", "DDDDDDD"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
ทำเครื่องหมายจุดศูนย์กลางของสี่เหลี่ยมตัวอย่างแต่ละรูป แล้วดูว่าตัวอักษรเปลี่ยนไปอย่างไรเมื่อห่างออกมา
คำใบ้ 2
ช่องที่อยู่ในวงเดียวกันใช้ตัวอักษรเดียวกัน หมายเลขวงคือระยะห่างจากจุดศูนย์กลางในแนวแถวหรือแนวคอลัมน์ ค่าใดมากกว่าก็ใช้ค่านั้น
คำใบ้ 3
ตรวจกฎของคุณกับตัวอย่าง n = 3 ก่อนสร้างสำหรับ n ใด ๆ
ความซับซ้อนที่คาดหวัง
เวลา O(n^2), หน่วยความจำเพิ่ม O(n^2)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน