前言說明
算法學(xué)習(xí)笋粟，日常刷題記錄震檩。
題目連接
題目內(nèi)容
給定一個非負(fù)索引k，其中k ≤ 33懂诗，返回楊輝三角的第k行蜂嗽。
楊輝三角.gif
在楊輝三角中，每個數(shù)是它左上方和右上方的數(shù)的和殃恒。
示例:
輸入: 3
輸出: [1,3,3,1]
進(jìn)階：
你可以優(yōu)化你的算法到O(k)空間復(fù)雜度嗎植旧？
分析過程
前面已經(jīng)寫了另一道楊輝三角的解答方法，請看文章：楊輝三角
前面一道的楊輝三角是返回楊輝三角的前numRows行离唐，而這一道是返回楊輝三角的第k行病附。
注意：這里的k是索引k，輸入3亥鬓，輸出的是[1,3,3,1]胖喳，從圖中可以看出這是第4行，所以這里的k是從0開始的贮竟，而不是從1開始丽焊。
那我們先直接復(fù)用前面那道題的代碼，取第k行的元素咕别，代碼如下：
class Solution {
public List<Integer> getRow(int rowIndex) {
// 定義楊輝三角列表
List<List<Integer>> dataList = new ArrayList<>();
// 構(gòu)造楊輝三角技健，每次構(gòu)造一行，這里的rowIndex要加1惰拱，因為從0開始算的
for (int i = 0; i < rowIndex + 1; ++i) {
// 定義楊輝三角單行列表
List<Integer> list = new ArrayList<>();
// 第一列
list.add(1);
if (i > 0) {
// 第一行之后
// 獲取上一行的結(jié)果
List<Integer> listTemp = dataList.get(i - 1);
// 遍歷上一行的結(jié)果雌贱，從第二列到最后一列
for (int j = 1; j < listTemp.size(); ++j) {
// 若不是第一列和最后一列，第n行第m列等于上一行第m-1列+第m列
list.add(listTemp.get(j - 1) + listTemp.get(j));
}
// 最后一列
list.add(1);
dataList.add(list);
} else {
// 第一行
dataList.add(list);
}
}
// 取第rowIndex行的元素返回
return dataList.get(rowIndex);
}
}
執(zhí)行用時3ms偿短，時間擊敗43.74%的用戶欣孤，內(nèi)存消耗36.4MB，空間擊敗15.27%的用戶昔逗。
運行結(jié)果
運行時間和空間不是很理想降传，因為定義了List<List<Integer>>，但是返回的卻是List<Integer>勾怒，這里生成的前k行占用了多余的空間婆排。
其實只申請一個List<Integer>就可以解決声旺，使用動態(tài)規(guī)劃，用上一次的結(jié)果計算下一次的結(jié)果段只，因為楊輝三角的第k行是由第k - 1行計算得出的腮猖，第k行第m列 = 第k-1行第m-1列 + 第k-1行第m列。
解答代碼
通過上述分析赞枕，采用動態(tài)規(guī)劃的代碼如下：
class Solution {
public List<Integer> getRow(int rowIndex) {
// 動態(tài)規(guī)劃澈缺，用上一次的結(jié)果計算下一次的結(jié)果
List<Integer> list = new ArrayList<>();
// 第一列
list.add(1);
if (rowIndex == 0) {
return list;
}
// 獲取上一次的結(jié)果
List<Integer> listTemp = getRow(rowIndex - 1);
// 遍歷上一次的結(jié)果，從第二列到最后一列
for (int i = 1; i < listTemp.size(); ++i) {
// 若不是第一列和最后一列炕婶，第n行第m列等于上一行第m-1列+第m列
list.add(listTemp.get(i - 1) + listTemp.get(i));
}
// 最后一列
list.add(1);
return list;
}
}
提交結(jié)果
執(zhí)行用時1ms谍椅，時間擊敗84.08%的用戶，內(nèi)存消耗36.1MB古话，空間擊敗72.11%的用戶。
運行結(jié)果
原文鏈接
原文鏈接：楊輝三角II
