Đề bài
Trong tam giác này, hàng thứ i (đếm từ 1) có i chữ số. Đánh số các vị trí trong hàng j = 1 đến i; chữ số ở hàng i, vị trí j là 1 khi i + j chẵn và là 0 khi i + j lẻ. Như vậy hàng 1 là 1, hàng 2 là 0 1, hàng 3 là 1 0 1, và các chữ số xen kẽ nhau theo mọi hàng lẫn mọi cột.
Hãy viết binary_triangle(n).
Đầu vào
n: Số hàng.
Đầu ra
Trả về các hàng theo thứ tự từ trên xuống. Trong mỗi hàng, các chữ số cách nhau đúng một dấu cách, không có dấu cách ở đầu hay cuối hàng.
Ràng buộc
0 ≤ n ≤ 100
Ví dụ
Đầu vào:
n = 4
Kết quả mong đợi:
expected = ["1", "0 1", "1 0 1", "0 1 0 1"]
Đầu vào:
long long n = 4;
Kết quả mong đợi:
std::vector<std::string> expected = {"1", "0 1", "1 0 1", "0 1 0 1"};
Đầu vào:
long n = 4;
Kết quả mong đợi:
string[] expected = new string[] {"1", "0 1", "1 0 1", "0 1 0 1"};
Giải thích
Hàng 4 bắt đầu với 4 + 1 = 5 (lẻ), nên là 0: ["1", "0 1", "1 0 1", "0 1 0 1"].
Đầu vào:
n = 2
Kết quả mong đợi:
expected = ["1", "0 1"]
Đầu vào:
long long n = 2;
Kết quả mong đợi:
std::vector<std::string> expected = {"1", "0 1"};
Đầu vào:
long n = 2;
Kết quả mong đợi:
string[] expected = new string[] {"1", "0 1"};
Giải thích
Ở hàng 2, vị trí 1 cho tổng 3 (lẻ) còn vị trí 2 cho tổng 4 (chẵn): ["1", "0 1"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Xem i + j chẵn hay lẻ ở vài ô đầu tiên.
Gợi ý 2
Hai vị trí kề nhau luôn có chữ số ngược nhau.
Gợi ý 3
Nối các chữ số bằng một dấu cách để cuối hàng không bị thừa gì.
Độ phức tạp mong đợi
thời gian O(n^2), bộ nhớ phụ O(n^2)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.