【Check 70】2024-05-10 - 118. 杨辉三角

[larscheng]

118. 杨辉三角

[larscheng]

思路

1 1，1 1，2，1 1，3，3，1 根据规律遍历计算，第n行第i个元素表示为n[i],n[i]=n-1[i-1]+n-1[i] 特殊情况：i=0或者i=n-1时，即每行第1和最后一个元素值==1

代码

    class Solution1 {

        public List<List<Integer>> generate(int numRows) {
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < numRows; i++) {
                List<Integer> temp = new ArrayList<>();
                for (int j = 0; j <= i; j++) {
                    if (j == 0 || j == i) {
                        temp.add(1);
                    } else {
                        temp.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                    }
                }
                res.add(temp);
            }
            return res;
        }
    }

复杂度

• 时间复杂度：O(n*n)
• 空间复杂度：O(1)