โจทย์
ลองนึกถึงกริดที่มี height แถวและ width คอลัมน์ ทั้งสองอย่างนับเริ่มจาก 0 เส้นดาวเริ่มที่ช่องมุมซ้ายบน และเลื่อนไปทางขวาหนึ่งคอลัมน์ทุกครั้ง โดยเลื่อนลงทีละแถวจนถึงแถวล่างสุด แล้วเลื่อนขึ้นทีละแถวจนถึงแถวบนสุด วนซ้ำไปเรื่อย ๆ เขียนให้ชัดเจนได้ดังนี้ ให้ P = 2(height − 1) และ p = c mod P คอลัมน์ c มีดาวเพียงดวงเดียวที่แถว p เมื่อ p < height และที่แถว P − p ในกรณีอื่น ช่องที่เหลือทั้งหมดเป็นช่องว่าง
จงเขียน zigzag_wave_pattern(width, height)
อินพุต
width: จำนวนคอลัมน์
height: จำนวนแถว
เอาต์พุต
คืนค่าสตริงจำนวน height ตัวเรียงจากบนลงล่าง โดยตัดช่องว่างต่อท้ายออก แถวที่ไม่มีดาวเลยให้เป็นสตริงว่าง
เงื่อนไข
1 ≤ width ≤ 80, 2 ≤ height ≤ 20
ตัวอย่าง
อินพุต:
width = 9
height = 3
ผลลัพธ์ที่คาดหวัง:
expected = ["* * *", " * * * *", " * *"]
อินพุต:
long long width = 9;
long long height = 3;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"* * *", " * * * *", " * *"};
อินพุต:
long width = 9;
long height = 3;
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"* * *", " * * * *", " * *"};
คำอธิบาย
P = 4 ดังนั้นคอลัมน์ 0 ถึง 8 ใช้แถว 0, 1, 2, 1, 0, 1, 2, 1, 0: ["* * *", " * * * *", " * *"]
อินพุต:
width = 5
height = 2
ผลลัพธ์ที่คาดหวัง:
expected = ["* * *", " * *"]
อินพุต:
long long width = 5;
long long height = 2;
ผลลัพธ์ที่คาดหวัง:
std::vector<std::string> expected = {"* * *", " * *"};
อินพุต:
long width = 5;
long height = 2;
ผลลัพธ์ที่คาดหวัง:
string[] expected = new string[] {"* * *", " * *"};
คำอธิบาย
เมื่อมีสองแถว ดาวจะสลับอยู่บนกับล่าง: ["* * *", " * *"]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
การเคลื่อนที่จะซ้ำเป็นรอบทุก 2(height − 1) คอลัมน์
คำใบ้ 2
ภายในหนึ่งรอบ แถวจะลงจาก 0 ไปถึง height − 1 แล้วขึ้นกลับมา
คำใบ้ 3
อาจง่ายกว่าถ้าสร้างกริดสองมิติที่เต็มไปด้วยช่องว่างก่อน แล้วค่อยแปลงแต่ละแถวเป็นสตริง
ความซับซ้อนที่คาดหวัง
เวลา O(width * height), หน่วยความจำเพิ่ม O(width * height)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน