#118

Pascals Triangle ↗

Easy草稿★★★★★⭐ O(numRows^2) 時間 · O(numRows^2) 空間
ArrayDynamic Programming
尚未複習過

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

118Pascals TriangleArrays & HashingEasyArrays & Hashing

給定非負整數 numRows，生成帕斯卡三角形的前 numRows 行。在帕斯卡三角形中，每個數字是其正上方兩個數字之和。

Example:

Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Intuition

TIP

核心思路：逐行生成，每行的首尾為 1，中間元素等於上一行對應位置兩個元素之和。

Approaches

1. Row-by-Row (from Previous Row) — O(numRows^2) / O(numRows^2)
  • Idea: 維護上一行的結果，逐行計算新行
  • Time: O(numRows^2) - 總元素數為 1+2+…+numRows
  • Space: O(numRows^2) - 儲存所有行
class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = MutableList(i + 1) { 1 }
            for (j in 1 until i) {
                row[j] = result[i - 1][j - 1] + result[i - 1][j]
            }
            result.add(row)
        }
        return result
    }
}
⭐ 2. Row-by-Row (Concise) — O(numRows^2) / O(numRows^2)
  • Idea: 同樣逐行生成，但利用 Kotlin 的函式風格使程式碼更簡潔
  • Time: O(numRows^2)
  • Space: O(numRows^2)
class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = MutableList(i + 1) { 1 }
            for (j in 1 until i) {
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            }
            triangle.add(row)
        }
        return triangle
    }
}
Note: Math Formula (Combinations)

第 i 行第 j 個元素等於組合數 C(i, j)，可以用乘法遞推計算，不需要參考上一行。

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = mutableListOf<Int>()
            var value = 1L
            for (j in 0..i) {
                row.add(value.toInt())
                value = value * (i - j) / (j + 1)
            }
            result.add(row)
        }
        return result
    }
}

🔑 Takeaways