您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

LeetCode 118 杨辉三角：Java 數學組合法與迭代法完美解法

編輯：Java 相關知識

題目回顧

給定非負整數 numRows，生成楊輝三角的前 numRows 行。

輸入: 5
輸出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

核心思路對比

方法一：迭代構造（最直觀，O(n²) 時間，O(1) 額外空間）

利用楊輝三角性質：每行首尾為 1，中間元素 = 上一行同索引 + 上一行前一索引。

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> triangle = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        List<Integer> row = new ArrayList<>(i + 1);
        row.add(1); // 首元素
        for (int j = 1; j < i; j++) {
            // 從上一行獲取兩個父元素
            row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
        }
        if (i > 0) row.add(1); // 尾元素（第一行只有 1 個元素）
        triangle.add(row);
    }
    return triangle;
}

方法二：數學組合公式（單行直接計算，O(n²) 時間，無需存儲上一行）

第 n 行（0-indexed）第 k 個元素 = C(n, k) = n! / (k! (n-k)!)。利用遞推關係 C(n, k) = C(n, k-1) * (n - k + 1) / k 避免階乘溢出與重複計算。

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<>(numRows);
    for (int n = 0; n < numRows; n++) {
        List<Integer> row = new ArrayList<>(n + 1);
        long val = 1; // 使用 long 防止中間乘法溢出 int
        for (int k = 0; k <= n; k++) {
            row.add((int) val);
            // 計算下一個組合數：C(n, k+1) = C(n, k) * (n - k) / (k + 1)
            val = val * (n - k) / (k + 1);
        }
        result.add(row);
    }
    return result;
}

方法三：原地更新單行數組（空間優化至 O(k)，LeetCode 119 杨辉三角 II 專用）

若只需第 rowIndex 行，可用長度 rowIndex+1 的數組，從右向左更新：row[j] += row[j-1]。

public List<Integer> getRow(int rowIndex) {
    Integer[] row = new Integer[rowIndex + 1];
    Arrays.fill(row, 0);
    row[0] = 1;
    for (int i = 1; i <= rowIndex; i++) {
        for (int j = i; j > 0; j--) {
            row[j] += row[j - 1];
        }
    }
    return Arrays.asList(row);
}

複雜度分析

方法	時間複雜度	空間複雜度（不含輸出）	優點
迭代構造	O(n²)	O(1)	邏輯清晰，易理解，無溢出風險
組合公式	O(n²)	O(1)	單行獨立計算，適合流式輸出，無需歷史行
原地更新	O(k²)	O(k)	單行問題空間最優

避坑指南

整數溢出：組合公式中間乘積 val * (n - k) 可能超過 Integer.MAX_VALUE（n=34 時 C(34,17) ≈ 2.3e9 > 2^31-1），**必須用 long 過渡**再轉 int。
除法順序：val = val * (n - k) / (k + 1) 必須先乘後除，保證整除無餘數；若先除會導致精度丟失。
邊界條件：numRows = 0 返回空列表；numRows = 1 返回 [[1]]。
Arrays.asList 陷阱：返回固定長度列表，不可添加元素，構建結果集時請用 new ArrayList<>()。

測試用例

@Test
public void testGenerate() {
    Solution s = new Solution();
    assertEquals(List.of(), s.generate(0));
    assertEquals(List.of(List.of(1)), s.generate(1));
    assertEquals(List.of(List.of(1), List.of(1,1)), s.generate(2));
    assertEquals(List.of(
        List.of(1),
        List.of(1,1),
        List.of(1,2,1),
        List.of(1,3,3,1),
        List.of(1,4,6,4,1)
    ), s.generate(5));
    
    // 驗證第 30 行首尾為 1，中間對稱
    List<Integer> row30 = s.generate(30).get(29);
    assertEquals(1, (int) row30.get(0));
    assertEquals(1, (int) row30.get(29));
    for (int i = 0; i < 15; i++) {
        assertEquals(row30.get(i), row30.get(29 - i));
    }
}