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