118. 楊輝三角
本文將會(huì)寫(xiě)如下幾個(gè)部分：
- 何謂“楊輝三角”
- LeetCode第118題題目部分
- 思路分析
- 題解
1. 何謂楊輝三角
觀察下圖：
我們可以直觀地觀察到幾條規(guī)律：
- 每一行的數(shù)字個(gè)數(shù)與其行號(hào)相等诡渴。例如诸老，第一行就一個(gè)數(shù)字懂昂，第五行有五個(gè)數(shù)字剂公。
- 從第二行起，每個(gè)數(shù)是它左上方和右上方數(shù)字之和。
- 每一行拿出來(lái)都是回文串琳骡，即，每一行都是沿中間對(duì)稱(chēng)的讼溺。整個(gè)三角形也是沿中間對(duì)稱(chēng)的楣号。
2. LeetCode第118題題目部分
給定一個(gè)非負(fù)整數(shù) numRows，生成楊輝三角的前 numRows 行怒坯。
在楊輝三角中炫狱，每個(gè)數(shù)是它左上方和右上方的數(shù)的和。
示例:
輸入: 5
輸出:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/pascals-triangle
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有剔猿。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)视译，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
3. 思路分析
以輸出n階楊輝三角為例归敬。
思路1--直觀地使用觀察出來(lái)的規(guī)律
只要認(rèn)清“從第二行起酷含，每個(gè)數(shù)是它左上方和右上方數(shù)字之和”鄙早，然后照著這條規(guī)律寫(xiě)代碼即可。具體操作是：
- 建立一個(gè)
的二維數(shù)組椅亚；
- 用一個(gè)二維循環(huán)往里填數(shù)字限番。在每行的首個(gè)元素和最后一個(gè)元素填上1，然后除首尾以外的元素用上面提到的規(guī)律賦值呀舔。
- 此題完成弥虐。
具體解釋一下上面的第2條操作：
- 雖然為了填數(shù)字建立的二維數(shù)組每一行元素的個(gè)數(shù)都是n，但我們只需要保證不需要的元素不填充即可模擬出自己在紙上畫(huà)的楊輝三角媚赖。也就是說(shuō)霜瘪，第一行只填充一個(gè)，第二行只填充兩個(gè)惧磺，第三行只填三個(gè)粥庄。依此類(lèi)推
- 其實(shí)這是一個(gè)Brute-Force的思想。直接用編程語(yǔ)言翻譯"從第二行起豺妓，每個(gè)數(shù)是它左上方和右上方數(shù)字之和"這一條話惜互，剩下的讓計(jì)算機(jī)去跑就好了。
復(fù)雜度是琳拭，且用了
的額外空間训堆。
思路2--純數(shù)學(xué)思路
此思想來(lái)源于科普中國(guó)上的介紹。
看圖：
在介紹這種思想前白嘁，各位讀者要將思想轉(zhuǎn)變?yōu)?作為首位開(kāi)始計(jì)數(shù)的思想坑鱼，即：
- 傳統(tǒng)意義上的首行是第0行，傳統(tǒng)意義上的第二行是第1行絮缅；
- 在每一行中鲁沥，第一個(gè)數(shù)字是第0個(gè)，第二個(gè)數(shù)字是第1個(gè)耕魄；
- 依此類(lèi)推画恰。
然后從圖上可以看出，第i行中第j個(gè)數(shù)字正是的值吸奴。
所以只需要用二項(xiàng)式系數(shù)計(jì)算即可允扇。
做完此題后，我們可以發(fā)現(xiàn)楊輝三角提示了二項(xiàng)式系數(shù)計(jì)算的一個(gè)遞歸式：则奥。
思路3--針對(duì)思路1的改良
上面兩種方法其實(shí)還可以進(jìn)一步改良考润。
前面已經(jīng)說(shuō)過(guò)，楊輝三角中读处，每一行都是回文串糊治，即每一行沿中線對(duì)稱(chēng)。那么是不是有一種方法罚舱，只求前半部分井辜，然后后半部分就可以自然地求出來(lái)了揖赴？
答案是有的：只需要循環(huán)前一半即可，后半部分對(duì)稱(chēng)賦值抑胎。舉例說(shuō)明：第5行（以0開(kāi)始計(jì)就是第4行）有5個(gè)元素燥滑，那么我們只需要對(duì)前三個(gè)元素進(jìn)行計(jì)算，后兩個(gè)直接利用回文串性質(zhì)賦值即可阿逃。
4. 題解
題解的順序?qū)?yīng)上面的思路順序铭拧。
思路1 (Java實(shí)現(xiàn))
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>(); // res用于返回結(jié)果
int[][] ans = new int[numRows][numRows];
for(int i = 0; i < numRows; ++i){
List<Integer> ls = new ArrayList<>();
for(int j = 0; j <= i; ++j){
if(j == i || j == 0){ ans[i][j] = 1; }
else{
ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];
}
ls.add(ans[i][j]);
}
res.add(ls);
}
return res;
}
}
思路2 (Python實(shí)現(xiàn))
import math # 直接引入python中的math庫(kù)，用于計(jì)算階乘
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = list()
for i in range(numRows):
tmp = list()
for j in range(i + 1):
posi = math.factorial(i) // (math.factorial(j) * math.factorial(abs(i - j))) # 這里必須用雙斜線除號(hào)恃锉，否則posi會(huì)被自動(dòng)轉(zhuǎn)換為浮點(diǎn)數(shù)類(lèi)型
tmp.append(posi)
res.append(tmp)
return res
思路3 (分別用Java和Python實(shí)現(xiàn))
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < numRows; ++i){
Integer[] tmp = new Integer[i + 1];
for(int h = 0; h < i + 1; ++h){ tmp[h] = 1; }
List<Integer> ls = new ArrayList<>(Arrays.asList(tmp));
if(i > 0){
for(int j = 1; j < (i / 2) + 1; ++j){
int pos = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j); // 唯一需要注意的點(diǎn)是：
ls.set(j, pos); // Java的ArrayList類(lèi)型不能像C++和Python那樣用中括號(hào)([ ])訪問(wèn)元素搀菩，
ls.set(i - j, pos); // 只能用get和set方法來(lái)做，所以有點(diǎn)不舒服
} // 所以這種方法不是很推薦用Java去寫(xiě)
}
res.add(ls);
}
return res;
}
}
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
res = list()
for i in range(numRows):
ls = [1 for _ in range(i + 1)]
if i > 0:
for j in range(1, i // 2 + 1): # Python需要注意的是要用//（雙斜線）來(lái)表示整除
ls[j] = res[i - 1][j - 1] + res[i - 1][j]
ls[i - j] = ls[j]
res.append(ls)
return res
