LeetCode 118. 杨辉三角

118. 杨辉三角

解题思路

• 每一排的第一个数字和最后一个数字都是1，$result[i][0] = result[i][i] = 1$
• 其余位置的数字，是左上方数字 + 正上方数字 $result[i][j] = result[i - 1][j -1] + result[i - 1][j]$

参考代码

解法一:

class Solution {
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> generate(int numRows) {
        if(numRows >= 1) {
            result.add(Arrays.asList(1));
        }

        if(numRows >= 2) {
            result.add(Arrays.asList(1,1));
        }

        for(int i = 2; i < numRows; i ++) {
            List<Integer> tmp = new ArrayList<>();
            for (int k = 0; k <= i; k++) {
                tmp.add(1);
            }

            for(int j = 1; j < i; j ++) {
                int sum = result.get(i - 1).get(j) + result.get(i - 1).get(j - 1);
                tmp.set(j, sum);
            }
            result.add(new ArrayList<>(tmp));
        }
        return result;
    }
}

解法二:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>(numRows);
        result.add(List.of(1));

        for(int i = 1; i < numRows; i ++) {
            List<Integer> tmp = new ArrayList<>(i + 1);
            tmp.add(1);
            for(int j = 1; j < i; j ++) {
                tmp.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
            }
            tmp.add(1);
            result.add(tmp);
        }
        return result;
    }
}