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