【力扣】杨辉三角问题

【力扣】杨辉三角I

✌杨辉三角快速入门

每行端点与结尾的数为1，每行其他元素的值等于它左上方和右上方的数的和。

💬输出杨辉三角I问题

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

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

🍵思路分析

根据输入的numRows，可以知道每行的长度len，然后对每行长度进行判断即可，如果是头尾则赋值为1，否则就等于上一行的左上方和右上方元素相加。

✍️ 算法实现

 public List<List<Integer>> generate(int numRows) {
        //返回数组
        List<List<Integer>> lists = new ArrayList<>();
        //从第一行开始的，下标为1
        for (int row = 1; row < numRows + 1; row++) {
            List<Integer> tmp = new ArrayList<>();
            int len = row;
            for (int i = 0; i < len; i++) {
                if (i == 0 || i == len - 1) {
                    tmp.add(1);
                } else {
                    tmp.add(lists.get(row - 2).get(i - 1) + lists.get(row - 2).get(i));
                }
            }
            lists.add(tmp);
        }
        return lists;
    }

【力扣】杨辉三角II

💬 输出杨辉三角II问题

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

输入: rowIndex = 3
输出: [1,3,3,1]

输入: rowIndex = 0
输出: [1]

输入: rowIndex = 1
输出: [1,1]

🍵思路分析

为减少空间复杂度，每次迭代依赖“上一行”的数据，迭代之后的数据覆盖“上一行”的数据，每次迭代计算时，从前往后进行计算，可以避免“上一行”数据发生变化

✍️ 算法实现

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>(rowIndex + 1);
        int left = 1, right = 1;
        list.add(1);
        for (int i = 1; i < rowIndex + 1; i++) {
            list.add(1);
            left = 1;
            for (int j = 1; j < i; j++) {
                right = list.get(j);
                list.set(j, left + right);
                left = right;
            }
        }
        return list;
    }
}

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
⭐️ 收藏，你的青睐是我努力的方向！
👄 评论，你的意见是我进步的财富！