Đề bài
Hàng đầu tiên là [1]. Mỗi hàng tiếp theo bắt đầu và kết thúc bằng 1. Mỗi phần tử bên trong là tổng của hai phần tử ngay phía trên nó. Trả về rows hàng đầu tiên, bắt đầu với số 1 duy nhất.
Cài đặt hàm pascals_triangle(rows).
Đầu vào
rows: Số lượng hàng cần sinh ra.
Đầu ra
Trả về một danh sách các hàng, bắt đầu từ trên xuống; mỗi hàng là một danh sách các số nguyên.
Ràng buộc
0 ≤ rows ≤ 60. Mỗi phần tử đều nằm trong phạm vi số nguyên có dấu 64-bit. Nếu rows bằng 0 thì trả về danh sách rỗng.
Ví dụ
Đầu vào:
rows = 4
Kết quả mong đợi:
expected = [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1]
]Đầu vào:
long long rows = 4;
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {
{1},
{1, 1},
{1, 2, 1},
{1, 3, 3, 1}
};Đầu vào:
long rows = 4;
Kết quả mong đợi:
long[][] expected = new long[][] {
new long[] {1},
new long[] {1, 1},
new long[] {1, 2, 1},
new long[] {1, 3, 3, 1}
};Giải thích
Số 2 ở hàng thứ 3 là 1 + 1. Hai số 3 ở giữa hàng thứ 4 là 1 + 2 và 2 + 1.
Đầu vào:
rows = 0
Kết quả mong đợi:
expected = []Đầu vào:
long long rows = 0;
Kết quả mong đợi:
std::vector<std::vector<long long>> expected = {};Đầu vào:
long rows = 0;
Kết quả mong đợi:
long[][] expected = new long[][] {};Giải thích
Không yêu cầu hàng nào, nên trả về danh sách rỗng.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Mỗi hàng bắt đầu và kết thúc bằng 1, còn các giá trị bên trong lấy từ hai số phía trên.
Gợi ý 2
Xây từng hàng dựa trên hàng trước thay vì tính lại từ đầu.
Gợi ý 3
Xử lý trường hợp hàng 0 bằng cách trả về danh sách rỗng ngay lập tức.
Độ phức tạp mong đợi
thời gian O(rows^2), bộ nhớ phụ O(rows^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.