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