Đề bài
Hình thoi là một kim tự tháp cân ghép với bản lộn ngược của chính nó ở bên dưới, hai phần dùng chung hàng rộng nhất. Với n cho trước, hình thoi 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, sau đó là 2m − 1 dấu sao.
Hãy viết diamond_pattern(n).
Đầu vào
n: Số hàng của nửa trên, tính cả hàng rộng nhất ở 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
Năm hàng có lần lượt 1, 3, 5, 3, 1 sao và 2, 1, 0, 1, 2 dấu cách ở đầu: [" *", " ***", "*****", " ***", " *"].
Đầu vào:
n = 2
Kết quả mong đợi:
expected = [" *", "***", " *"]
Đầu vào:
long long n = 2;
Kết quả mong đợi:
std::vector<std::string> expected = {" *", "***", " *"};
Đầu vào:
long n = 2;
Kết quả mong đợi:
string[] expected = new string[] {" *", "***", " *"};
Giải thích
Ba hàng: một sao sau một dấu cách, ba sao, rồi một sao sau một dấu cách: [" *", "***", " *"].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Vẽ nửa trên trước; đó chính là kim tự tháp cân mà có thể bạn đã biết.
Gợi ý 2
Nửa dưới là nửa trên bỏ đi hàng cuối, viết theo thứ tự ngược lại.
Gợi ý 3
Một cách khác là dùng |n − k| để biết hàng k cách hàng giữa bao xa.
Độ 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.