Đề bài
Hình thoi này có 2n − 1 hàng. Đánh số các hàng k = 1 đến 2n − 1 và đặt m = n − |n − k|, khi đó m lần lượt là 1, 2, …, n, …, 2, 1. Hàng k gồm n − m dấu cách ở đầu, rồi các chữ số 1, 2, …, m, rồi m − 1, …, 1, viết liền nhau không có dấu cách. Hàng giữa là hàng dài nhất, chẳng hạn 12321 khi n = 3.
Hãy viết number_diamond(n).
Đầu vào
n: Số hàng của nửa trên, tính cả hàng giữa (tối đa 9, nên mọi số đều có một chữ số).
Đầu ra
Trả về 2n − 1 hàng theo thứ tự từ trên xuống, không có dấu cách thừa ở cuối hàng. Khi n bằng 0, trả về danh sách rỗng.
Ràng buộc
0 ≤ n ≤ 9
Ví dụ
Đầu vào:
n = 3
Kết quả mong đợi:
expected = [" 1", " 121", "12321", " 121", " 1"]
Đầu vào:
long long n = 3;
Kết quả mong đợi:
std::vector<std::string> expected = {" 1", " 121", "12321", " 121", " 1"};
Đầu vào:
long n = 3;
Kết quả mong đợi:
string[] expected = new string[] {" 1", " 121", "12321", " 121", " 1"};
Giải thích
m lần lượt là 1, 2, 3, 2, 1: [" 1", " 121", "12321", " 121", " 1"].
Đầu vào:
n = 2
Kết quả mong đợi:
expected = [" 1", "121", " 1"]
Đầu vào:
long long n = 2;
Kết quả mong đợi:
std::vector<std::string> expected = {" 1", "121", " 1"};
Đầu vào:
long n = 2;
Kết quả mong đợi:
string[] expected = new string[] {" 1", "121", " 1"};
Giải thích
Ba hàng ứng với m = 1, 2, 1: [" 1", "121", " 1"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Trước tiên hãy tìm giá trị đỉnh m của mỗi hàng: 1, 2, ..., n, ..., 2, 1.
Gợi ý 2
Hàng có đỉnh m đếm từ 1 lên m rồi lùi về 1.
Gợi ý 3
Số dấu cách ở đầu hàng chỉ phụ thuộc vào m.
Độ 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.