Pascal's Triangle

Q: Độ phức tạp thời gian của việc tạo tam giác Pascal là bao nhiêu?

O(n²) cho n hàng: tam giác có khoảng n²/2 phần tử và mỗi phần tử cần một phép cộng. Đây là mức tối ưu, vì bạn phải ghi mọi phần tử của đầu ra. Bộ nhớ bổ sung ngoài đầu ra là O(1) .

Q: Tam giác Pascal liên quan như thế nào đến các hệ số nhị thức?

Phần tử thứ k của hàng r , tính từ 0, là C(r, k) , số cách chọn k phần tử trong r phần tử. Quy tắc tính tổng là đẳng thức C(r, k) = C(r-1, k-1) + C(r-1, k) , và tổng các phần tử ở hàng r bằng 2^r , số tập con của r phần tử.

Q: Bạn có thể tính một hàng mà không cần tạo các hàng phía trên nó không?

Có. Bắt đầu với 1 rồi tính mỗi phần tử tiếp theo từ phần tử trước đó: C(r, k) = C(r, k-1) × (r-k+1) / k . Hãy nhân trước khi chia để phép chia cho kết quả chính xác, đồng thời dùng số nguyên 64 bit cho tích. Khi đó, hàng r cần thời gian O(r) .

DễQuy hoạch động

+10

Trong tam giác Pascal, hàng đầu tiên là [1]. Mỗi hàng tiếp theo dài hơn hàng trước một phần tử, bắt đầu và kết thúc bằng 1, còn mỗi phần tử ở giữa bằng tổng của hai phần tử ngay phía trên nó. Bạn nhận được một số nguyên numRows. Hãy trả về numRows hàng đầu tiên của tam giác, theo thứ tự từ hàng trên cùng, mỗi hàng là một mảng số nguyên.

Hàm

generate(numRows: integer) → integer-2d-array

numRowsinteger: cần dựng bao nhiêu hàng của tam giác
Trả vềinteger-2d-array: numRows hàng đầu tiên, bắt đầu từ hàng trên cùng

Ràng buộc

1 ≤ numRows ≤ 30
Mỗi giá trị trong 30 hàng đầu tiên đều vừa với số nguyên có dấu 32 bit. Giá trị lớn nhất là 77558760, nằm giữa hàng 30.

Ví dụ

Đầu vào: numRows = 5
Đầu ra: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Giải thích: Mỗi mục bên trong bằng tổng của hai mục phía trên. Hàng thứ tư: 3 = 1 + 2 và 3 = 2 + 1. Hàng thứ năm: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Đầu vào: numRows = 1
Đầu ra: [[1]]
Giải thích: Với một hàng, tam giác chỉ có phần trên cùng là [1].

Câu hỏi mở rộng

Bạn có thể chỉ giữ lại một mảng và cập nhật mảng đó tại chỗ, lần lượt theo từng hàng không? Vòng lặp bên trong phải chạy theo hướng nào, và tại sao?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi phần tử bằng tổng của hai phần tử ở hàng phía trên. Tính lại quy tắc đó từ đầu cho từng phần tử sẽ khiến bạn tính lại cùng một giá trị, và khối lượng công việc tăng gấp đôi sau mỗi hàng. Các hàng bạn trả về là lời giải đã lưu cho những bài toán nhỏ hơn, vì vậy hãy xây dựng tam giác từ trên xuống, mỗi hàng dựa trên hàng trước đó.

Tính đệ quy từng mục

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Đánh số hàng và vị trí bắt đầu từ 0. Định nghĩa này trở thành một hàm: entry(row, col) có giá trị 1 ở các cạnh, khi col là 0 hoặc bằng row, còn lại thì bằng entry(row-1, col-1) + entry(row-1, col). Cách này đúng vì đó chính là định nghĩa.

Đệ quy chỉ dừng ở các cạnh, nơi giá trị trả về là 1, vì vậy một phần tử có giá trị v cần khoảng 2v lần gọi. Hàng r có tổng tối đa là 2^r, nên 30 hàng cần khoảng 2^31 lần gọi, tức là hơn hai tỷ.

Thuật toán

Viết entry(row, col): trả về 1 nếu col bằng 0 hoặc col bằng row.
Nếu không, trả về entry(row-1, col-1) + entry(row-1, col).
Với mỗi row từ 0 đến numRows-1, thu thập entry(row, col) cho mọi col từ 0 đến row.
Trả về danh sách các hàng.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Tạo từng hàng từ hàng phía trên

Ý tưởng

Đệ quy liên tục yêu cầu các phần tử ở những hàng trước, và dù sao bạn cũng xây dựng các hàng đó. Vì vậy, hãy tính các hàng từ trên xuống dưới. Khi điền hàng r, hãy đọc hàng r-1, vốn đã hoàn thành. Mỗi phần tử cần một phép cộng: bảng chứa các kết quả nhỏ hơn chính là đầu ra.

Bắt đầu mỗi hàng với r + 1 số 1 sẽ tạo cả hai cạnh, vì vậy hàng 0 và hàng 1, không có vị trí bên trong, không cần xử lý riêng. Tam giác có 1 + 2 + ... + n phần tử, khoảng n²/2, nên độ phức tạp là O(n²) và không cần thêm bộ nhớ ngoài đầu ra: 465 phần tử cho 30 hàng thay vì hai tỷ lần gọi.

Thuật toán

Bắt đầu với một danh sách hàng rỗng.
Với mỗi row từ 0 đến numRows-1, tạo row + 1 số 1.
Với mỗi col từ 1 đến row-1, đặt giá trị của nó bằng tổng các phần tử ở vị trí col-1 và col của hàng trước đó.
Thêm hàng vào danh sách rồi tiếp tục. Trả về danh sách.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Lỗi thường gặp và trường hợp biên

Trả về numRows + 1 hàng. Đánh số từ 0, hàng cuối bạn cần là numRows-1.
Chạy vòng lặp bên trong qua các cạnh. Vị trí 0 không có phần tử cha bên trái, còn vị trí row không có phần tử cha bên phải, nên đọc các vị trí đó sẽ vượt ngoài phạm vi.
Dùng một phạm vi bị lỗi với các hàng nhỏ. Trong Swift, 1..<row gây lỗi khi row bằng 0, còn trong R, 2:(row-1) đếm ngược đến 1 khi row bằng 2.
Tính các phần tử bằng giai thừa. C(29, 14) nằm trong phạm vi của kiểu int, nhưng 29! gây tràn số ngay cả với số nguyên 64 bit.
Thêm cùng một mảng cho mỗi hàng rồi thay đổi mảng đó. Mọi hàng trong kết quả đều trở thành hàng cuối cùng.

Câu hỏi thường gặp3

Độ phức tạp thời gian của việc tạo tam giác Pascal là bao nhiêu?

O(n²) cho n hàng: tam giác có khoảng n²/2 phần tử và mỗi phần tử cần một phép cộng. Đây là mức tối ưu, vì bạn phải ghi mọi phần tử của đầu ra. Bộ nhớ bổ sung ngoài đầu ra là O(1).

Tam giác Pascal liên quan như thế nào đến các hệ số nhị thức?

Phần tử thứ k của hàng r, tính từ 0, là C(r, k), số cách chọn k phần tử trong r phần tử. Quy tắc tính tổng là đẳng thức C(r, k) = C(r-1, k-1) + C(r-1, k), và tổng các phần tử ở hàng r bằng 2^r, số tập con của r phần tử.

Bạn có thể tính một hàng mà không cần tạo các hàng phía trên nó không?

Có. Bắt đầu với 1 rồi tính mỗi phần tử tiếp theo từ phần tử trước đó: C(r, k) = C(r, k-1) × (r-k+1) / k. Hãy nhân trước khi chia để phép chia cho kết quả chính xác, đồng thời dùng số nguyên 64 bit cho tích. Khi đó, hàng r cần thời gian O(r).

def generate(numRows):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

numRows = 5

Đầu ra mong đợi

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]