【LeetCode】118. 杨辉三角（Pascal's Triangle）解题思路

题目如下（题目链接戳我）：

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
备注：在杨辉三角中，每个数是它左上方和右上方的数的和。

示例：
输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

也给出了杨辉三角的示例图：

杨辉三角

以下是我的解题思路：

我首先整理了前 5 行杨辉三角的数据；

根据题目的返回值要求（ List < List < Integer >> ）（我在中括号和字母之间故意加了空格），我把每一行看作一个集合，每个元素对应一个下标索引，我把索引也整理了一下；

然后得出了以下几条规律和方法：

第一个元素为1（这个其实不算规律，就是事实，只是为了一会写代码时方便写限制）
每一行数据集合 List< Integer > 的第一个元素为 1（也是事实）；
增加一个集合，用于记录上一行的数值；
每个元素等于上一个集合同索引的数值和前一个索引的数值的和（这也是个事实，不过要加个限制，见下条）；
每行集合中最后一个元素（索引为index）只等于上一行集合中索引为 index-1 的值；

思路整理完了，剩下写代码就很简单了。

public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> item;//当前行的集合
        List<Integer> last = null; //上一行的集合
        int index = 1; //行号，每行元素个数和行号一致
        while (index <= numRows) {
            item = new ArrayList<>();
            //循环index次，向item中添加元素
            a:
            for (int i = 0; i < index; i++) {
                if(last == null){
                    item.add(1);
                    break a;
                }else if(i == 0){
                    item.add(1);
                }else if(i == index - 1){
                    item.add(last.get(i - 1));
                }else{
                    item.add(last.get(i - 1) + last.get(i));
                }
            }
            last = item;
            list.add(item);
            index++;
        }
        return list;
    }

提交结果：

执行用时 : 1 ms, 在Pascal's Triangle的Java提交中击败了97.86% 的用户
内存消耗 : 33.6 MB, 在Pascal's Triangle的Java提交中击败了39.51% 的用户

【LeetCode】118. 杨辉三角（Pascal's Triangle）解题思路

推荐阅读更多精彩内容