โจทย์
แต่ละแถวของพีระมิดนี้อ่านจากซ้ายไปขวาหรือขวาไปซ้ายก็ได้ผลเหมือนกัน แถวที่ i (นับจาก 1) มีช่องว่างนำหน้า n − i ช่อง ตามด้วยเลขโดด 1, 2, …, i แล้วต่อด้วย i − 1, …, 2, 1 โดยเขียนติดกันทั้งหมดไม่มีช่องว่างคั่น ดังนั้นแถวที่ 3 คือ 12321 และแถวที่ 1 คือ 1
จงเขียน palindromic_number_pyramid(n)
อินพุต
n: จำนวนแถว (ไม่เกิน 9 ทุกจำนวนจึงเป็นเลขหลักเดียว)
เอาต์พุต
คืนค่าแถวทั้งหมดเรียงจากบนลงล่าง โดยไม่มีช่องว่างต่อท้าย
เงื่อนไข
0 ≤ n ≤ 9
ตัวอย่าง
อินพุต:
n = 3
ผลลัพธ์ที่คาดหวัง:
expected = [" 1", " 121", "12321"]
อินพุต:
long long n = 3;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {" 1", " 121", "12321"};
อินพุต:
long n = 3;
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {" 1", " 121", "12321"};
คำอธิบาย
แถวที่ 1 คือช่องว่าง 2 ช่องกับ 1 แถวที่ 2 คือช่องว่าง 1 ช่องกับ 121 แถวที่ 3 คือ 12321: [" 1", " 121", "12321"]
อินพุต:
n = 1
ผลลัพธ์ที่คาดหวัง:
expected = ["1"]
อินพุต:
long long n = 1;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"1"};
อินพุต:
long n = 1;
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"1"};
คำอธิบาย
มีแถวเดียวซึ่งเป็นเลข 1: ["1"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
แบ่งแต่ละแถวเป็นส่วนขาขึ้น 1..i และส่วนขาลง i − 1..1
คำใบ้ 2
ส่วนขาลงคือส่วนขาขึ้นที่กลับลำดับแล้วตัดเลขตัวสุดท้ายออก
คำใบ้ 3
ช่องว่างนำหน้าใช้กฎเดียวกับพีระมิดดาว
ความซับซ้อนที่คาดหวัง
เวลา O(n^2), หน่วยความจำเพิ่ม O(n^2)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน