118. Pascal's Triangle

题目：

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

链接: http://leetcode.com/problems/pascals-triangle/

一刷，这道题简单却解得并不好。

首先问题是numRows和range(N)时上限的考虑，因为range从0开始，所以要range(numRows - 1)
list.reverse()是in place的，reversed(list)返回值是新的 list
cur = cur.extend(second_half）返回的是None!!! cur.extend(second_half)就够了，这种错误平时根本不可能犯，太低级
numRows == 1是否作为特殊例子返回

有一个总结似乎可以避免4)，经常我会用prev, cur两个list，如果只用一个的话似乎可以少判断一次边界情况。

 1 class Solution(object):
 2     def generate(self, numRows):
 3         if numRows == 0:
 4             return []
 5         if numRows == 1:
 6             return [[1]]
 7         result = [[1]]
 8         prev = [1]
 9         cur = []
10         
11         for row in range(numRows - 1):
12             cur.append(1)
13             for idx in range(row / 2):
14                 cur.append(prev[idx] + prev[idx + 1])
15             second_half = reversed(cur)
16             if row % 2:
17                 cur.append(prev[row / 2] + prev[row / 2 + 1])
18             cur.extend(second_half)
19             result.append(cur)
20             prev, cur = cur, []
21         return result

2/17/2017, Java

有什么办法能避免19行每次重新建一个ArrayList？

 1 public class Solution {
 2     public List<List<Integer>> generate(int numRows) {
 3         List<List<Integer>> ret = new ArrayList<>();
 4         if (numRows <= 0) return ret;
 5         
 6         List<Integer> level = new ArrayList<>();
 7         List<Integer> previous = new ArrayList<>();
 8         int a;
 9         for (int i = 0; i < numRows; i++) {
10             for (int j = 0; j <= i; j++) {
11                 if (j == 0 || j == i) level.add(j, 1);
12                 else {
13                     a = previous.get(j) + previous.get(j - 1);
14                     level.add(j, a);
15                 }
16             }
17             ret.add(level);
18             previous = level;
19             level = new ArrayList<>();
20         }
21         return ret;
22     }
23 }

参考别人答案，只要把level的定义放在外层循环体内就可以了

其他改变，level是ArrayList，可以不用add(index, E)而直接用add(E)即可。

 1  public class Solution {
 2      public List<List<Integer>> generate(int numRows) {
 3          List<List<Integer>> ret = new ArrayList<>();
 4          if (numRows <= 0) return ret;
 5  
 6          for (int i = 0; i < numRows; i++) {
 7              ArrayList<Integer> level = new ArrayList<>();
 8              for (int j = 0; j <= i; j++) {
 9                  if (j == 0 || j == i) level.add(1);
10                  else {
11                      level.add(ret.get(i-1).get(j) + ret.get(i-1).get(j - 1));
12                  }
13              }
14              ret.add(level);
15          }
16          return ret;
17      }
18  }