給定一個索引 k，返回帕斯卡三角形（楊輝三角）的第 k 行。
例如：
給定 k = 3，則返回 [1, 3, 3, 1]
你可以優(yōu)化你的算法到 O(k) 的空間復雜度嗎？
使用遞歸的方式： Ck[n] = Ck-1[n-1] + Ck-1[n]【超時了】
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<Integer>(rowIndex+1);
int half = rowIndex / 2;
if(rowIndex == 1){
result.add(1);
result.add(1);
return result;
}
for(int i=0;i<rowIndex + 1;i++){
//如果是另一半，則取對稱元素
if(i > half) {
result.add(result.get(rowIndex - i));
}
else{
result.add(getNum(rowIndex, i));
}
}
return result;
}
//索引k， 第n個
private Integer getNum(int k, int n) {
if(k == 0 || k == 1){
return 1;
}
if(n == 0 || n == k) {
return 1;
}
return getNum(k-1, n-1) + getNum(k-1, n);
}
}
以上之所以出現(xiàn)超時，是因為遞歸調用時存在多次重復調用。
比如在計算getNum(10, 3)時會發(fā)起調用：
遞歸.png
如上圖所示，getNum(8,2),getNum(7,1)和getNum(7,2)會調用多次，越到后面，重復調用的遞歸會更多，如果把這些遞歸調用的結果保存下來，效果會不會更好呢？
class Solution {
private Map<String,Integer> cache = new HashMap<String, Integer>();
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<Integer>(rowIndex+1);
int half = rowIndex / 2;
if(rowIndex == 1){
result.add(1);
result.add(1);
return result;
}
for(int i=0;i<rowIndex + 1;i++){
//如果是另一半，則取對稱元素
if(i > half) {
result.add(result.get(rowIndex - i));
}
else{
result.add(getNum(rowIndex, i));
}
}//0 1 2 3 1
return result;
}
//索引k， 第n個
private Integer getNum(int k, int n) {
if(cache.get(k + ":" + n) != null){
return cache.get(k + ":" + n);
}
if(k == 0 || k == 1){
return 1;
}
if(n == 0 || n == k) {
return 1;
}
int r = getNum(k-1, n-1) + getNum(k-1, n);
cache.put(k + ":" + n, r);
return r;
}
}
結果很nice, Leetcode給的結論是【4ms】，然而這個結果卻是所有答案中耗時最大的，難道還有優(yōu)化的地步。
楊輝三角規(guī)律：
第n行第1個數(shù)： 1
第n行第2個數(shù)：1×(n-1)
第n行第3個數(shù)：1×(n-1)×(n-2)/2
第n行第4個數(shù): 1×(n-1)×(n-2)/2*(n-3)/3
用索引講：
第k索引行第0索引數(shù)：1
第k索引行第1索引數(shù)：1×k
第k索引行第2索引數(shù)：1×k×(k-1)/2
第k索引行第3索引數(shù)：1×k×(k-1)/2×(k-2)/3
所以最終答案： 【耗時1ms】
class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> result = new ArrayList<Integer>(rowIndex+1);
int half = rowIndex / 2;
if(rowIndex == 1){
result.add(1);
result.add(1);
return result;
}
for(int i=0;i<rowIndex + 1;i++){
if(i == 0){
result.add(1);
continue;
}
//如果是另一半，則取對稱元素
if(i > half) {
result.add(result.get(rowIndex - i));
}
else{
result.add(Double.valueOf(1.0 * result.get(i-1) * (rowIndex - (i-1)) / i).intValue());
}
}//0 1 2 3 1
return result;
}
}
總結： 楊輝三角每行元素不僅和上一行有關系，同一行元素之間的關系也頗為密切。而遞歸則是采用第一種方案，不用緩存在計算大數(shù)時會出現(xiàn)超時，而第二種方案則非常輕松實現(xiàn)。
