第一部分：題目

🏠 鏈接：119. 楊輝三角 II - 力扣（LeetCode）

? 難度：簡單

第二部分：解法①-數(shù)學(xué)規(guī)律法

2.1 規(guī)律分析

2.2 代碼實(shí)現(xiàn)

public static List<Integer> getRow(int rowIndex) {// 建立一個(gè)capacity=rowIndex+1的集合ArrayList<Integer> arrayList = new ArrayList<>(rowIndex + 1);// 設(shè)置第rowIndex行首位置的值long indexValue = 1;// 遍歷第rowIndex行所有位置for (int i = 0;i <= rowIndex;i++){// long強(qiáng)轉(zhuǎn)為int,將indexValue加入集合，發(fā)生了自動裝包int->IntegerarrayList.add((int)indexValue);// 根據(jù)規(guī)律設(shè)置下一個(gè)好下一個(gè)位置的值indexValue = indexValue*(rowIndex-i)/(i+1);}return arrayList;
}
/*
這里有個(gè)細(xì)節(jié)：我們定義indexValue時(shí)類型為long,為什么不設(shè)置為int類型，這樣便可以舍去加入集合時(shí)的強(qiáng)轉(zhuǎn)過程這是因?yàn)槿绻麑ndexValue定義為int類型，那么在代碼第六行計(jì)算indexValue*(rowIndex-i)時(shí)由于indexValue,rowIndex和i都為int，那么indexValue*(rowIndex-i)的結(jié)果也為int但是當(dāng)rowIndex過大時(shí)，計(jì)算該行某些位置時(shí)indexValue*(rowIndex-i)的值會超過int的范圍導(dǎo)致這個(gè)值為負(fù)數(shù)。因此，我們定義類型為long的話，由于long的精度比int高，而indexValue*(rowIndex-i)的結(jié)果自然為long類型，且沒有超過long的取值范圍，所以indexValue*(rowIndex-i)得到的便會是正常結(jié)果,而非因?yàn)閿?shù)據(jù)溢出結(jié)果變?yōu)樨?fù)數(shù)
*/

2.3 需要思考

我們定義indexValue時(shí)類型為long,為什么不設(shè)置為int類型，這樣便可以舍去加入集合時(shí)的強(qiáng)轉(zhuǎn)過程。

這是因?yàn)槿绻麑ndexValue定義為int類型，那么在代碼第六行計(jì)算 indexValue * ( rowIndex - i ) 時(shí)由于 indexValue , rowIndex 和 i 都為int，那么 indexValue * ( rowIndex - i ) 的結(jié)果也為int。但是當(dāng)rowIndex過大時(shí)，計(jì)算該行某些位置時(shí)indexValue*(rowIndex-i)的值會超過int的范圍導(dǎo)致這個(gè)值為負(fù)數(shù)。

因此，我們定義類型為long的話，由于long的精度比int高，而indexValue*(rowIndex-i)的結(jié)果自然為long類型，且沒有超過long的取值范圍，所以indexValue * ( rowIndex - i ) 得到的便會是正常結(jié)果，而非因?yàn)閿?shù)據(jù)溢出結(jié)果變?yōu)樨?fù)數(shù)。

第三部分：解法②-記憶法（備忘錄）

Memoization 記憶法（也稱備忘錄）是一種優(yōu)化技術(shù)，通過存儲函數(shù)調(diào)用結(jié)果（通常比較昂貴），當(dāng)再次出現(xiàn)相同的輸入（子問題）時(shí)，就能實(shí)現(xiàn)加速效果

    public List<Integer> getRow(int rowIndex) {ArrayList<Integer> list = new ArrayList<>(rowIndex + 1);// 設(shè)置首元素的值為1list.add(1);// 從第二行（行索引為1）開始遍歷for (int i = 1; i <= rowIndex; i++) {for (int j = i - 1; j > 0; j--) {// 規(guī)律： [i][j] 的取值應(yīng)為 [i-1][j-1] + [i-1][j]list.set(j, list.get(j - 1) + list.get(j));}// 末尾元素的值為1list.add(1);}return list;}

第四部分：對比總結(jié)

我們來看下兩種方法的執(zhí)行效率：

1?? 數(shù)學(xué)規(guī)律法

2?? 記憶法

很明顯，數(shù)學(xué)規(guī)律法花費(fèi)的時(shí)間更少，這是因?yàn)?數(shù)學(xué)規(guī)律法 只需要我們逐一計(jì)算第 rowIndex 行每個(gè)元素的值即可，而 記憶法 需要我們從第0行開始，計(jì)算每一行每一個(gè)元素的值。