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