本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

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

119.给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

思路分析

首先，我们先将杨辉三角特殊处理一下，如下图：

进行如图所示的处理后，将每一行的元素看成是数组的元素，并可以得出以下结论：

第k行的0和k-1位置上的元素始终是1；
第k行的i位置（0<i<k-1）上的元素为第k-1行i-1与i位置上的元素之和。

根据以上结论便得出如下118题的代码。

而119题这是要展示第k+1行的数据，因此只需要做出简单的小调整：

k值从0开始
只需要返回第k+1行的数据

由以上得出如下119题第一份代码。

此方案是可以优化的，每次计算出一行数据，都需要用一个数组来保存，才能根据这一行的数据来计算下一行，我们可以考虑在同一个数组中进行原位操作，从而将空间复杂度变为O(1)。
而这里如果从前向后计算，会因为值被替换而导致结果错误，例如根据第4行计算第5行的2位置的值时，由于1位置的值4已经计算出来并替换了第4行的1位置的3，所以会导致计算结果错误，因此这里考虑从后向前开始计算。

优化后的代码如下119题第二份代码。

代码展示

// 118题
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ret = new ArrayList<>();
    // 特殊值处理
    if (numRows == 0)
        return ret;
    Integer[] nums = null;
    for (int k = 1; k <= numRows; k++) {
        // 记录k-1行的内容
        Integer[] lastNums = nums;
        // 初始化k行数组
        nums = new Integer[k];
        for (int j = 0; j < k; j++) {
            if (j == 0 || j == k - 1) {
                nums[j] = 1;
            } else {
                nums[j] = lastNums[j - 1] + lastNums[j];
            }
        }
        ret.add(new ArrayList<>(Arrays.asList(nums)));
    }
    return ret;
}
复制代码

// 119题
public List<Integer> getRow(int rowIndex) {
    Integer[] nums = null;
    for (int k = 0; k <= rowIndex; k++) {
        // 记录k-1行的内容
        Integer[] lastNums = nums;
        // 初始化k行数组
        nums = new Integer[k + 1];
        for (int j = 0; j < k + 1; j++) {
            if (j == 0 || j == k) {
                nums[j] = 1;
            } else {
                nums[j] = lastNums[j - 1] + lastNums[j];
            }
        }
    }
    return Arrays.asList(nums);
}

// 优化
public List<Integer> getRow1(int rowIndex) {
    Integer[] nums = new Integer[rowIndex + 1];
    for (int k = 0; k <= rowIndex; k++) {
        for (int j = k; j >= 0; j--) {
            if (j == 0 || j == k) {
                nums[j] = 1;
            } else {
                nums[j] = nums[j - 1] + nums[j];
            }
        }
    }
    return Arrays.asList(nums);
}
复制代码