Đề bài
Đồng hồ cát thu hẹp dần từ 2n − 1 sao xuống chỉ còn một sao ở hàng giữa, rồi lại nở rộng ra. Hình có 2n − 1 hàng. Đánh số các hàng k = 1 đến 2n − 1 và đặt d = |n − k| (khi đó d lần lượt là n − 1, …, 1, 0, 1, …, n − 1). Hàng k gồm n − 1 − d dấu cách ở đầu, sau đó là 2d + 1 dấu sao.
Hãy viết hourglass_pattern(n).
Đầu vào
n: Số hàng của nửa trên, tính cả hàng giữa.
Đầ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 ≤ 100
Ví dụ
Đầu vào:
n = 3
Kết quả mong đợi:
expected = ["*****", " ***", " *", " ***", "*****"]
Đầu vào:
long long n = 3;
Kết quả mong đợi:
std::vector<std::string> expected = {"*****", " ***", " *", " ***", "*****"};
Đầu vào:
long n = 3;
Kết quả mong đợi:
string[] expected = new string[] {"*****", " ***", " *", " ***", "*****"};
Giải thích
Số sao là 5, 3, 1, 3, 5 và số dấu cách ở đầu là 0, 1, 2, 1, 0: ["*****", " ***", " *", " ***", "*****"].
Đầu vào:
n = 1
Kết quả mong đợi:
expected = ["*"]
Đầu vào:
long long n = 1;
Kết quả mong đợi:
std::vector<std::string> expected = {"*"};
Đầu vào:
long n = 1;
Kết quả mong đợi:
string[] expected = new string[] {"*"};
Giải thích
Chỉ còn phần eo: ["*"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Hàng giữa có một dấu sao và n − 1 dấu cách ở đầu.
Gợi ý 2
Hàng càng xa hàng giữa thì càng nhiều sao và càng ít dấu cách.
Gợi ý 3
Hãy đếm số hàng: có 2n − 1 hàng chứ không phải 2n.
Độ 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.