Leetcode-118-杨辉三角

Leecode-118-Pascal’s Triangle

思路：动态规划

题目描述：

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

输入: 5
输出: 杨辉三角的前五行
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution：动态规划

• 思路：如果能知道上一行的杨辉三角，就可以根据每对相邻的值轻松计算出下一行。

• 首先：我们先生成整个triange矩阵，三角形的每一行都以子列表的形式存储。

• 然后，检查初始化情况，如果输入的行数为0,就会返回[1]。（也就是杨辉三角的第一行）

• 最后，如果numRows（输入的行数）大于0的话，那么我们用[1] 来初始化第一行。

具体填充方式如下所示：

Java

Solution :

class Solution{
    public List<List<Integer>> generate(int numRows){
        // 返回结果的数组
        List<List<Integer>> triangle = new ArrayList<>();

        // 第一步：特殊判断
        if (numRows == 0){
            return triangle;
        }

        // 第二步：初始化数组 把第一行变成[[1]]
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        // 第三步：状态转移(从第二行开始)
        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            // 当前行的元素
            List<Integer> row = new ArrayList<>();
            // 上一行的元素
            List<Integer> preRow = triangle.get(rowNum - 1);

            // 第一个元素永远是1
            row.add(1);

            // 中间的每个元素是上一行的 下标j - 1元素 加上 j下标的元素
            for (int j = 1;j < rowNum; j++){
                row.add(preRow.get(j-1) + preRow.get(j));
            }

            // 最后一个元素永远是1
            row.add(1);

            // 将每次的结果加到triangle的结果中
            triangle.add(row);
        }
        return triangle;
    }
}

测试用例：

public class MainClass {
    // Integer 数组转字符串输出
    public static String integerArrayListToString(List<Integer> nums, int length){
        if (length == 0){
            return "[]";
        }

        String result = "";
        for(int index = 0;index < length;index++){
            Integer num = nums.get(index);
            result += Integer.toString(num) + ", ";
        }

        return "[" + result.substring(0,result.length() - 2) + "]";
    }

    // Integer 数组转字符串输出 重载
    public static String integerArrayListToString(List<Integer> nums){
        return integerArrayListToString(nums,nums.size());
    }

    // 二维List<List<Integer>> 转字符串
    public static String int2dListToString(List<List<Integer>> nums){
        StringBuilder sb = new StringBuilder("[");
        for(List<Integer> list:nums){
            sb.append(integerArrayListToString(list));
            sb.append(",");
        }

        sb.setCharAt(sb.length() - 1,']');
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null){
            int numRows = Integer.parseInt(line);
            List<List<Integer>> ret = new Solution().generate(numRows);
            String out = int2dListToString(ret);
            System.out.println(out);
        }
    }
}

• 时间复杂度：O(numRows^2) ，两层循环，每层要运行rowNum次
• 空间复杂度：O(numRows^2)，额外需要的dp数组大小

不讲武德

// 重点：ArrayList如何初始化二维数组
class Solution {
    public List<List<Integer>> generate(int numRows) {
        Integer[][] a= {{1},
                {1, 1},
                {1, 2, 1},
                {1, 3, 3, 1},
                {1, 4, 6, 4, 1},
                {1, 5, 10, 10, 5, 1},
                {1, 6, 15, 20, 15, 6, 1},
                {1, 7, 21, 35, 35, 21, 7, 1},
                {1, 8, 28, 56, 70, 56, 28, 8, 1},
                {1, 9, 36, 84, 126, 126, 84, 36, 9, 1},
                {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1},
                {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
                {1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1},
                {1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1},
                {1, 14, 91, 364, 1001, 2002, 3003, 3432, 3003, 2002, 1001, 364, 91, 14, 1},
                {1, 15, 105, 455, 1365, 3003, 5005, 6435, 6435, 5005, 3003, 1365, 455, 105, 15, 1},
                {1, 16, 120, 560, 1820, 4368, 8008, 11440, 12870, 11440, 8008, 4368, 1820, 560, 120, 16, 1},
                {1, 17, 136, 680, 2380, 6188, 12376, 19448, 24310, 24310, 19448, 12376, 6188, 2380, 680, 136, 17, 1},
                {1, 18, 153, 816, 3060, 8568, 18564, 31824, 43758, 48620, 43758, 31824, 18564, 8568, 3060, 816, 153, 18, 1},
                {1, 19, 171, 969, 3876, 11628, 27132, 50388, 75582, 92378, 92378, 75582, 50388, 27132, 11628, 3876, 969, 171, 19, 1},
                {1, 20, 190, 1140, 4845, 15504, 38760, 77520, 125970, 167960, 184756, 167960, 125970, 77520, 38760, 15504, 4845, 1140, 190, 20, 1},
                {1, 21, 210, 1330, 5985, 20349, 54264, 116280, 203490, 293930, 352716, 352716, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1},
                {1, 22, 231, 1540, 7315, 26334, 74613, 170544, 319770, 497420, 646646, 705432, 646646, 497420, 319770, 170544, 74613, 26334, 7315, 1540, 231, 22, 1},
                {1, 23, 253, 1771, 8855, 33649, 100947, 245157, 490314, 817190, 1144066, 1352078, 1352078, 1144066, 817190, 490314, 245157, 100947, 33649, 8855, 1771, 253, 23, 1},
                {1, 24, 276, 2024, 10626, 42504, 134596, 346104, 735471, 1307504, 1961256, 2496144, 2704156, 2496144, 1961256, 1307504, 735471, 346104, 134596, 42504, 10626, 2024, 276, 24, 1},
                {1, 25, 300, 2300, 12650, 53130, 177100, 480700, 1081575, 2042975, 3268760, 4457400, 5200300, 5200300, 4457400, 3268760, 2042975, 1081575, 480700, 177100, 53130, 12650, 2300, 300, 25, 1},
                {1, 26, 325, 2600, 14950, 65780, 230230, 657800, 1562275, 3124550, 5311735, 7726160, 9657700, 10400600, 9657700, 7726160, 5311735, 3124550, 1562275, 657800, 230230, 65780, 14950, 2600, 325, 26, 1},
                {1, 27, 351, 2925, 17550, 80730, 296010, 888030, 2220075, 4686825, 8436285, 13037895, 17383860, 20058300, 20058300, 17383860, 13037895, 8436285, 4686825, 2220075, 888030, 296010, 80730, 17550, 2925, 351, 27, 1},
                {1, 28, 378, 3276, 20475, 98280, 376740, 1184040, 3108105, 6906900, 13123110, 21474180, 30421755, 37442160, 40116600, 37442160, 30421755, 21474180, 13123110, 6906900, 3108105, 1184040, 376740, 98280, 20475, 3276, 378, 28, 1},
                {1, 29, 406, 3654, 23751, 118755, 475020, 1560780, 4292145, 10015005, 20030010, 34597290, 51895935, 67863915, 77558760, 77558760, 67863915, 51895935, 34597290, 20030010, 10015005, 4292145, 1560780, 475020, 118755, 23751, 3654, 406, 29, 1}};

        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            list.add((List<Integer>)Arrays.asList(a[i]));
        }
        list = list.subList(0,numRows);
        return list;
    }
}

打赏