給定一個(gè)非負(fù)整數(shù) numRows，生成楊輝三角(在楊輝三角中，每個(gè)數(shù)是它左上方和右上方的數(shù)的和葵擎。)的前 numRows 行德挣。
PascalTriangleAnimated2.gif
示例:
輸入: 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)注明出處。
解題思路：
如果能夠知道一行楊輝三角，我們就可以根據(jù)每對(duì)相鄰的值輕松地計(jì)算出它的下一行嘶是。
所以要計(jì)算第n列的元素，需要從頭開始
如下：
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> resultlist=new ArrayList<>();
if (numRows == 0){//如果等于0直接返回
return resultlist;
}
resultlist.add(new ArrayList<>());
resultlist.get(0).add(1);//添加根元素
for (int i = 1; i <numRows ; i++) {//先獲取每一行的list蛛碌，然后塞進(jìn)總list里
List<Integer> nowList=new ArrayList<>();
List<Integer> pre=resultlist.get(i-1);
nowList.add(1);//默認(rèn)在每一列第一位為1
for (int j = 1; j <pre.size() ; j++)
nowList.add(pre.get(j-1)+pre.get(j));
}
nowList.add(1);//默認(rèn)在每一列最后一位為1
resultlist.add(nowList);
}
return resultlist;
}
}
楊輝三角II
給定一個(gè)非負(fù)索引 k聂喇，其中 k ≤ 33，返回楊輝三角(在楊輝三角中蔚携，每個(gè)數(shù)是它左上方和右上方的數(shù)的和希太。)的第 k 行。
示例:
輸入: 3
輸出: [1,3,3,1];
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/pascals-triangle-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有酝蜒。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)誊辉，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
解題思路：既然上面的可以把所有的元素都拿到秕硝，這次只拿他要求的k行就可以了芥映，如下：
//第K行的元素
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> resultlist=new ArrayList<>();
resultlist.add(new ArrayList<>());
resultlist.get(0).add(1);
if (rowIndex==0){
return resultlist.get(0);
}
for (int i = 1; i <=rowIndex ; i++) {//先獲取每一行的list，然后塞進(jìn)總list里
List<Integer> nowList=new ArrayList<>();
List<Integer> pre=resultlist.get(i-1);
nowList.add(1);
for (int j = 1; j <pre.size() ; j++) {
nowList.add(pre.get(j-1)+pre.get(j));
}
nowList.add(1);
resultlist.add(nowList);
}
return resultlist.get(resultlist.size()-1);//只返回目標(biāo)列
}
}
會(huì)發(fā)現(xiàn)這中效率不高远豺，看題解中有用數(shù)學(xué)方式解決的：
首先我們應(yīng)該了解楊輝三角正好是二次項(xiàng)的展開式,(1+x)的n次冪的系數(shù),有通項(xiàng)公式C(n-1,m-1)=(n-1)!/[(m-1)!(n-m)!] 而研究每一項(xiàng)后,發(fā)現(xiàn)他們的規(guī)律,如 C(4,1)=C(4,0)4/1,C(4,2)=C(4,1)3/2,
C(4,3)=C(4,2)2/3,C(4,4)=C(4,3)1/4:
找到規(guī)律,所以0ms的大神代碼才寫成如下這樣子:
作者：a-lan-ruo-2
鏈接：https://leetcode-cn.com/problems/two-sum/solution/yang-hui-san-jiao-de-tong-xiang-gong-shi-by-a-lan-/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有奈偏。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處躯护。
//第K行的元素
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> res = new ArrayList<Integer>(rowIndex+1);
long nk = 1;
for(int i = 0; i <= rowIndex; i++){
res.add((int)nk);
nk = nk * (rowIndex - i) / (i + 1);
}
return res;
}
}
每天一算法惊来，成功有方法，堅(jiān)持棺滞！
原文鏈接：
楊輝三角：https://leetcode-cn.com/problems/pascals-triangle/
楊輝三角II：https://leetcode-cn.com/problems/pascals-triangle-ii/
