LeetCode-118-PascalsTriangle

118杨辉三角

题目描述

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

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

示例

示例 1:

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

输入: numRows = 1
输出: [[1]]


提示:

1 <= numRows <= 30

题解一：

    /**
     * 思路：根据杨辉三角特性
     * a.周边元素都是1
     * b.中间元素都值等于由上层紧密连接的元素和
     * 时间复杂度：O（n）
     * 空间复杂度：O（1）
     *
     * @param numRows 杨辉三角的前numRows行
     * @return 杨辉三角集合
     */
    public List> generate1(int numRows) {
        List> rows = new ArrayList<>(numRows);
        // 从左至右
        for (int i = 1; i <= numRows; i++) {
            List row = new ArrayList<>(i);
            for (int j = 1; j <= i; j++) {
                int val =0;
                // 每行的第一个元素和最后一个元素都是 1
                if (j == 1 || j == i) {
                    val = 1;
                } else {
                    // 获取上一行数据
                    List preRow = rows.get(i - 2);
                    val = preRow.get(j - 2) + preRow.get(j -1);
                }
                row.add(val);
            }
            rows.add(row);
        }
        return rows;
    }

可以换成适合程序员的方式（从0计数），这里判断if (j == 0 || j == i)第一列和最后一列，会被sonar警告

SonarLint: Remove this expression which always evaluates to "false"

这里表达式是没问题的，sonar是个小傻瓜（四川话HMP）

    /**
     * 思路：根据杨辉三角特性
     * a.周边元素都是1
     * b.中间元素都值等于由上层紧密连接的元素和
     * 

     * 时间复杂度：O（n）
     * 空间复杂度：O（1）
     *
     * @param numRows 杨辉三角的前numRows行
     * @return 杨辉三角集合
     */
    public List> generate2(int numRows) {
        List> rows = new ArrayList<>(numRows);
        // 从左至右
        for (int i = 0; i < numRows; i++) {
            List row = new ArrayList<>(i + 1);
            for (int j = 0; j <= i; j++) {
                int val =0;
                // 每行的第一个元素和最后一个元素都是 1
                if (j == 0 || j == i) {
                    val = 1;
                } else {
                    // 获取上一行数据
                    List preRow = rows.get(i - 1);
                    val = preRow.get(j - 1) + preRow.get(j);
                }
                row.add(val);
            }
            rows.add(row);
        }
        return rows;
    }

题解二：

题解二感觉比题解一稍微复杂但是都是O(n)的复杂度，区别是，题解一在我们要计算某个值需要的值是被计算好放在集合里面，我们直接取出来即可，例如：

因为是从左至右，从上到下，我们计算第三行的值时，第二行的所有值已经被计算出来，只需要取出来求和。

题解二的话从左至右，从下到上，计算值时去取上一层的两个值之和，但是这两个值有可能现在还不存在

例如当前计算值 row=5, column = 1, 此时我们应需要找到 row = 4, column = 0与column=1，第四行第0列因为超出边界是返回0值，第四行第1列也不知道值是多少，需要知道第三行第一列的值…直到走到了第一行第一列，返回了1，后续的值也可以计算出来了。虽然这个比较复杂，但是优势是，如果后面有个需求是求指定行列的值，那么我们只需要把与这行列的相关数据计算出来，而不用构造全部的数据。

    /**
     * 思路：根据杨辉三角特性
     * a.周边元素都是1
     * b.中间元素都值等于由上层紧密连接的元素和
     * 

     * 时间复杂度：O（n）
     * 空间复杂度：O（1）
     *
     * @param numRows 杨辉三角的前numRows行
     * @return 杨辉三角集合
     */
    public List> generate3(int numRows) {
        List> rows = new ArrayList<>(numRows);
        // 从右至左
        for (int i = 1; i <= numRows; i++) {
            calRowValueFromBottomToTop(rows, numRows, i);
        }
        return rows;
    }

    /**
     * 由下至上计算指定杨辉三角行列值
     *
     * @param rows   杨辉三角集合
     * @param row    杨辉三角行
     * @param column 杨辉三角列
     * @return 指定行列值
     */
    public int calRowValueFromBottomToTop(List> rows, int row, int column) {
        // 如果超出边界返回 0，因为我们的任意值都是由两个数之和而来的
        if (column < 1 || column > row) {
            return 0;
        }
        List list = null;
        // 如果当前行号大于集合大小，证明需要初始化
        if (row > rows.size()) {
            list = new ArrayList<>(row);
        } else {
            list = rows.get(row - 1);
        }
        // 如果要取的值已经存在（比如我要取3行的2列，如果list.size = 3，证明已经存在），直接返回
        if (column <= list.size()) {
            return list.get(column - 1);
        }
        int parentRight = calRowValueFromBottomToTop(rows, row - 1, column - 1);
        int parentLeft = calRowValueFromBottomToTop(rows, row - 1, column);
        int value = parentRight + parentLeft;
        // 第一行数据的值左右相加等于0，这里手动赋值一下
        value = value == 0 ? 1: value;
        list.add(value);
        // 初始化并添加第一个数据后加入行集合
        if (list.size() == 1) {
            rows.add(list);
        }
        return value;
    }