楊輝三角II
題目
給定一個非負索引 k，其中 k ≤ 33，返回楊輝三角的第 k 行酷宵。
在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和躬窜。
示例:
輸入: 3
輸出: [1,3,3,1]
進階：
你可以優(yōu)化你的算法到 O(k) 空間復(fù)雜度嗎浇垦？
思路
- 簡單版本可以構(gòu)建楊輝三角,之后取前一行進行相加得到索引一行
- 數(shù)學(xué)公式版本
代碼
- 簡單版本
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<>();
result.add(1);
List<Integer> preList = new ArrayList<>();
if(rowIndex == 0){
return result;
}
preList.add(1);
for(int i = 1;i < rowIndex;i++){
List<Integer> temp = new ArrayList<>();
temp.add(1);
for(int j = 1;j < i;j++){
temp.add(preList.get(j) + preList.get(j-1));
}
temp.add(1);
preList = temp;
}
for(int i = 1;i < preList.size();i++){
result.add(preList.get(i) + preList.get(i-1));
}
result.add(1);
return result;
}
- 數(shù)學(xué)公式版本
public static List<Integer> tGetRow(int rowIndex)
{
rowIndex++; //從0開始
List<Integer> res = new ArrayList<Integer>();
res.add(1);
long tem = 1;
for (int i = 1; i < rowIndex; i++)
{
tem = tem * (rowIndex - i) / i;
res.add((int)tem);
}
return res;
}
