杨辉三角

题目

给定一个非负整数 *numRows，*生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

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

解法

解法一： 递归。

下面一行的m值是由上面一行n值决定的。比如下面一行的第 i 个元素 m[i] 值是由上面一行的第 i-1 个元素的值n[i-1]与第i个元素的值n[i]的相加的和，如果i-1是n的最后一个元素，那么第i个元素的值为0即可。

class Solution {

    // 递归
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if(numRows <= 1){
            list.add(1);
            result.add(list);
            return result;
        }
        result = generate(numRows-1);
        List<Integer> list1 = result.get(numRows - 2);
        for(int i = 0 ; i < numRows ; i++ ){
            if(i == 0){
                list.add(1);
                continue;
            }
            int num = (i <= list1.size() - 1) ? list1.get(i) : 0;
            int preNum = list1.get(i-1);
            list.add(num+preNum);
        }

        result.add(list);
        return result;
        
    }
}

解法二： 迭代，思路同上面的递归解法，换汤不换药。

class Solution {

    // 迭代
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0 ; i < numRows ; i++){
            List<Integer> list = new ArrayList<>();
            if(i == 0){
                list.add(1);
                result.add(list);
                continue;
            }
            List<Integer> pre = result.get(i-1);
            for(int j = 0 ; j <= i ; j++){
                if(j == 0){
                    list.add(1);
                    continue;
                }
                int num = (j <= pre.size()-1) ? pre.get(j) : 0;
                int preNum = pre.get(j - 1);
                list.add(num+preNum);
            }
            result.add(list);
        }
        return result;
    }
}

总结

本篇文章讲解了算法题目的思路和解法，代码和笔记由于纯手打，难免会有纰漏，如果发现错误的地方，请第一时间告诉我，这将是我进步的一个很重要的环节。以后会定期更新算法题目以及各种开发知识点，如果您觉得写得不错，不妨点个关注，谢谢。