Pascal's Triangle

Q: Berapa kompleksitas waktu untuk menghasilkan segitiga Pascal?

O(n²) untuk n baris: segitiga memiliki sekitar n²/2 entri dan setiap entri membutuhkan satu penjumlahan. Ini optimal, karena kamu harus menulis setiap entri output. Ruang tambahan di luar output adalah O(1) .

Q: Bagaimana hubungan segitiga Pascal dengan koefisien binomial?

Entri k pada baris r , dihitung mulai dari 0, adalah C(r, k) , jumlah cara untuk memilih k item dari r item. Aturan penjumlahan adalah identitas C(r, k) = C(r-1, k-1) + C(r-1, k) , dan jumlah semua entri pada baris r adalah 2^r , jumlah subset dari r item.

Q: Bisakah kamu menghitung satu baris tanpa membuat baris-baris di atasnya?

Ya. Mulai dari 1 dan dapatkan setiap entri berikutnya dari entri sebelumnya: C(r, k) = C(r, k-1) × (r-k+1) / k . Kalikan sebelum membagi agar hasil pembagiannya tepat, dan gunakan integer 64-bit untuk hasil perkalian. Baris r memerlukan waktu O(r) .

MudahDynamic programming

+10

Dalam segitiga Pascal, baris pertama adalah [1]. Setiap baris berikutnya memiliki satu elemen lebih banyak, dimulai dan diakhiri dengan 1, dan setiap elemen di antaranya adalah jumlah dari dua elemen yang tepat berada di atasnya. Kamu mendapatkan bilangan bulat numRows. Kembalikan numRows baris pertama segitiga tersebut, dimulai dari baris paling atas, dengan setiap baris berupa array bilangan bulat.

Fungsi

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

numRowsinteger: berapa banyak baris segitiga yang akan dibuat
Mengembalikaninteger-2d-array: numRows baris pertama, baris teratas terlebih dahulu

Batasan

1 ≤ numRows ≤ 30
Setiap entri dari 30 baris pertama muat dalam integer bertanda 32-bit. Nilai terbesar adalah 77558760, di tengah baris ke-30.

Contoh

Input: numRows = 5
Output: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Penjelasan: Setiap entri di bagian dalam menjumlahkan dua entri di atasnya. Baris keempat: 3 = 1 + 2 dan 3 = 2 + 1. Baris kelima: 4 = 1 + 3, 6 = 3 + 3, 4 = 3 + 1.

Input: numRows = 1
Output: [[1]]
Penjelasan: Dengan satu baris, segitiga itu hanya bagian puncaknya, [1].

Pertanyaan lanjutan

Bisakah kamu menyisakan hanya satu array dan memperbaruinya secara langsung, baris demi baris? Ke arah mana perulangan bagian dalam harus berjalan, dan mengapa?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Sebuah entri adalah jumlah dua entri pada baris di atasnya. Menghitung ulang aturan itu dari awal untuk setiap entri akan menghitung kembali nilai yang sama, dan jumlah pekerjaan menjadi dua kali lipat di setiap baris. Baris yang kamu hasilkan menyimpan jawaban untuk masalah yang lebih kecil, jadi bangun segitiganya dari atas ke bawah, setiap baris berdasarkan baris sebelumnya.

Hitung setiap entri secara rekursif

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Nomori baris dan posisi mulai dari 0. Definisinya menjadi fungsi: entry(row, col) bernilai 1 di tepi, saat col bernilai 0 atau row, dan selain itu bernilai entry(row-1, col-1) + entry(row-1, col). Definisi ini benar karena memang itulah definisinya.

Rekursi hanya berhenti di tepi, yang menghasilkan 1, jadi entri dengan nilai v memerlukan sekitar 2v pemanggilan. Jumlah baris r mencapai 2^r, jadi 30 baris memerlukan sekitar 2^31 pemanggilan, lebih dari dua miliar.

Algoritma

Tulis entry(row, col): kembalikan 1 jika col adalah 0 atau col sama dengan row.
Jika tidak, kembalikan entry(row-1, col-1) + entry(row-1, col).
Untuk setiap row dari 0 hingga numRows-1, kumpulkan entry(row, col) untuk setiap col dari 0 hingga row.
Kembalikan list baris.

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

Bangun setiap baris dari baris di atas

Intuisi

Rekursi terus meminta entri dari baris sebelumnya, dan kamu tetap menyusun baris-baris itu. Jadi, hitung baris dari atas ke bawah, dan saat mengisi baris r, baca baris r-1 yang sudah selesai. Setiap entri memerlukan satu penjumlahan: tabel jawaban yang lebih kecil itu adalah outputnya.

Memulai setiap baris dengan r + 1 angka satu akan menetapkan kedua tepinya, jadi baris 0 dan 1, yang tidak memiliki posisi di bagian dalam, tidak memerlukan kasus khusus. Segitiga ini memiliki 1 + 2 + ... + n, sekitar n²/2, entri, sehingga pekerjaannya adalah O(n²) tanpa memerlukan memori selain output: 465 entri untuk 30 baris, bukan dua miliar pemanggilan.

Algoritma

Mulai dengan list baris yang kosong.
Untuk setiap row dari 0 hingga numRows-1, buat row + 1 angka satu.
Untuk setiap col dari 1 hingga row-1, atur nilainya menjadi jumlah posisi col-1 dan col pada baris sebelumnya.
Tambahkan baris tersebut, lalu lanjutkan. Kembalikan list tersebut.

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

Jebakan dan kasus tepi

Mengembalikan numRows + 1 baris. Penomoran dimulai dari 0, jadi baris terakhir yang kamu perlukan adalah numRows-1.
Menjalankan perulangan bagian dalam pada tepi. Posisi 0 tidak memiliki induk di sebelah kiri dan posisi row tidak memiliki induk di sebelah kanan, jadi membacanya akan mengakses indeks di luar batas.
Rentang yang bermasalah pada baris kecil. Swift 1..<row mengalami crash saat row bernilai 0, dan R 2:(row-1) menghitung mundur hingga 1 saat row bernilai 2.
Menghitung entri dengan faktorial. C(29, 14) muat dalam int, tetapi 29! melampaui batas bilangan bulat 64-bit sekalipun.
Menambahkan array yang sama untuk setiap baris, lalu mengubahnya. Setiap baris dalam jawaban menjadi baris terakhir.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu untuk menghasilkan segitiga Pascal?

O(n²) untuk n baris: segitiga memiliki sekitar n²/2 entri dan setiap entri membutuhkan satu penjumlahan. Ini optimal, karena kamu harus menulis setiap entri output. Ruang tambahan di luar output adalah O(1).

Bagaimana hubungan segitiga Pascal dengan koefisien binomial?

Entri k pada baris r, dihitung mulai dari 0, adalah C(r, k), jumlah cara untuk memilih k item dari r item. Aturan penjumlahan adalah identitas C(r, k) = C(r-1, k-1) + C(r-1, k), dan jumlah semua entri pada baris r adalah 2^r, jumlah subset dari r item.

Bisakah kamu menghitung satu baris tanpa membuat baris-baris di atasnya?

Ya. Mulai dari 1 dan dapatkan setiap entri berikutnya dari entri sebelumnya: C(r, k) = C(r, k-1) × (r-k+1) / k. Kalikan sebelum membagi agar hasil pembagiannya tepat, dan gunakan integer 64-bit untuk hasil perkalian. Baris r memerlukan waktu O(r).

def generate(numRows):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

numRows = 5

Output yang diharapkan

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