本文首發于公眾號「五分鐘學算法」，是圖解 LeetCode 系列文章之一。
個人網站：https://www.cxyxiaowu.com

楊輝三角應該是大家很早就接觸到的一個數學知識，它有很多有趣的性質：

• 每個數字等于上一行的左右兩個數字之和，即 C(n+1,i) = C(n,i) + C(n,i-1)
• 每行數字左右對稱，由 1 開始逐漸變大
• 第 n 行的數字有 n 項
• 第 n 行的第 m 個數和第 n - m + 1 個數相等 ，為組合數性質之一
• ( a + b )n的展開式中的各項系數依次對應楊輝三角的第 ( n + 1 ) 行中的每一項
• 。。。

楊輝三角

題目來源于 LeetCode 上第 118 號問題：楊輝三角。題目難度為 Easy，目前通過率為 61.8% 。

題目描述

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

在楊輝三角中，每個數是它左上方和右上方的數的和。

示例:

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

題目解析

這道題目在各大高校的習題中經常出現。

對于本題而言，利用性質 1 ：每一行的首個和結尾一個數字都是 1，從第三行開始，中間的每個數字都是上一行的左右兩個數字之和。

代碼實現

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> result = new ArrayList<>();if (numRows < 1) return result;for (int i = 0; i < numRows; ++i) {//擴容List<Integer> list = Arrays.asList(new Integer[i+1]);list.set(0, 1); list.set(i, 1);for (int j = 1; j < i; ++j) {//等于上一行的左右兩個數字之和list.set(j, result.get(i-1).get(j-1) + result.get(i-1).get(j));}result.add(list);}return result; } }

楊輝三角II

題目來源于 LeetCode 上第 119 號問題：楊輝三角II。題目難度為 Easy，目前通過率為 55.5% 。

題目描述

給定一個非負索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行。

在楊輝三角中，每個數是它左上方和右上方的數的和。

示例:

輸入: 3 輸出: [1,3,3,1]

進階：

你可以優化你的算法到 O(k) 空間復雜度嗎？

題目解析

這道題目的難點與思考點在于題目有額外限制條件，程序只能使用 O(k) 的額外空間，因此無法通過累加的方式將每一行都輸出打印。

這里依舊使用楊輝三角的規律，很隱藏的規律：對于楊輝三角的同一行，第 ( i + 1) 項是第 i 項的( k - i ) /( i + 1 ) 倍。

比如：

• 第 k 索引行的第 0 項：1
• 第 k 索引行的第 1 項：1 * k
• 第 k 索引行的第 2 項：1 * k * ( k - 1) / 2
• 第 k 索引行的第 3 項：[1 * k * ( k - 1) / 2 ] * ( k - 2 ) / 3

代碼實現

class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> res = new ArrayList<>(rowIndex + 1);long index = 1;for (int i = 0; i <= rowIndex; i++) {res.add((int) index);index = index * ( rowIndex - i ) / ( i + 1 );}return res; } }

一個有趣的結論

感興趣小伙伴的可以搜索一下李永樂講得抽獎概率相關的視頻，里面提及到了很多楊輝三角的神奇特點。

總結

以上是生活随笔為你收集整理的leetcode 打印_LeetCode第118号问题：杨辉三角的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。