โจทย์ทั้งหมด
ปานกลาง 0 ข้อที่แก้แล้ว อัตราผ่าน 0%

ถอดรหัสแพทเทิร์น

หากฎของตระกูลสี่เหลี่ยมตัวอักษรจากสมาชิกสองสามตัวแรก แล้วสร้างสมาชิกลำดับที่ n ใด ๆ

สิ่งที่คุณจะได้เรียนรู้

  • อธิบายภาพด้วยกฎที่ใช้หมายเลขแถวและคอลัมน์
  • วัดหมายเลขวงจากค่ามากที่สุดของระยะห่างสองค่า
  • แปลงตัวเลขเป็นตัวอักษร

โจทย์

หนังสือปริศนาเล่มหนึ่งแสดงสมาชิกสามตัวแรกของตระกูลแพทเทิร์น แล้วให้ผู้อ่านหาตัวที่เหลือเอง:

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

ตัวอย่าง

ตัวอย่างที่ 1
อินพุต:
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"]

ตัวอย่างที่ 2
อินพุต:
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 กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน

คำตอบที่ผ่านดีที่สุดของแต่ละคน คำตอบที่เร็วกว่า ใช้หน่วยความจำน้อยกว่า และได้คะแนนดีกว่าจะอยู่ด้านบน

ยังไม่มีคำตอบที่ผ่าน แก้โจทย์นี้แล้วคว้าอันดับหนึ่งไปเลย

เรียนรู้จากคนอื่น

แนวทางจากชุมชน

ยังไม่มีวิธีทำที่เผยแพร่ ลองแก้โจทย์นี้เพื่อแชร์วิธีแรก