Pascal Triangle I/II

• Easy
• keyword: Math
• 类似: Best meeting point, count digits

2道相关的题目, 即构造出杨辉三角.

第一题

• 这个题目直接iteration即可. 通过使用result里最后的list, 构造当前的list, 注意首尾加上一个1, 中间的就是通过上层的2个相邻的数相加得到.
• 代码如下. 注意ArrayList/Linkedlist的set/add的复杂度.

public List<List<Integer>> generateTTT(int numRows) {
    List<List<Integer>> result = new ArrayList<>();
    if (numRows < 1) return result;
    if (numRows >= 1) {
      List<Integer> tmp = new ArrayList<>();
      tmp.add(1);
      result.add(tmp);
    }
    if (numRows >= 2) {
      List<Integer> tmp = new ArrayList<>();
      tmp.add(1);
      tmp.add(1);
      result.add(tmp);
    }
    if (numRows >= 3) {
      for (int r = 3; r <= numRows; ++r) {
        List<Integer> tmp = new ArrayList<>();
        tmp.add(1);
        for (int c = 1; c < r - 1; ++c) {
          int val = result.get(r - 2).get(c - 1) + result.get(r - 2).get(c);
          tmp.add(val);
        }
        tmp.add(1);
        result.add(tmp);
      }
    }
    //helper(result, tmp, 1, numRows);
    return result;
  }

第二题

• 使用O(k)的空间, 得到第k层.
• 这里我是看了discuss一个同学对第一题的解, 从而做出来的. 这里利用一个性质: 每次将上一层的头部加一个1, 然后两两相加即可得到当前层.

• 例如:

  • [1, 1] => [1,1,1] => [1, 1+1, 1] => [1,2,1].
  • [1,2,1] => [1,1,2,1] => [1, 1+2, 2+1, 1] => [1,3,3,1].
  • [1,3,3,1] => [1,1,3,3,1] => [1,1+3,3+3,3+1,1] => [1,4,6,4,1].

• 代码如下:

public List<Integer> getRow(int rowIndex) {
    List<Integer> row = new ArrayList<>();
    for (int i = 0; i <= rowIndex; ++i) {
      row.add(0, 1);
      for (int j = 1; j < row.size()-1; ++j) {
        row.set(j, row.get(j) + row.get(j + 1));
      }
    }
    return row;
  }

总结

• 这有点像count digits, best meeting point, rotate graph. 都是找到性质, 从而直接解决问题. best meeting point是发现Median是解, rotate graph是知道公式, count digits是分析出3种情况, 乃至所有DP是找到关系(例如BTBSS IV, house robber(九章解法)).
• 这里第二题的公式确实不太可能想出来, 只有知道了才会写.