【LeetCode解题报告】《算法基础004

• 一、杨辉三角
• • 1.题目
  • 2.分析
  • 3.代码
• 二、杨辉三角II
• • 1.题目
  • 2.分析
  • 3.代码

118.杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
1 <= numRows <= 30

从杨辉三角找到了几点规律：

1. 杨辉三角可以看作一个二维数组，有对应的行和列。
2. 对于杨辉三角第n行：行数= 列数 = 元素个数 = n
3. 第二行开始，每行首尾元素都为1。即： a [ n − 1 ] [ 0 ] = a [ n − 1 ] [ n − 1 ] = 1 a[n - 1][0] = a[n - 1][n - 1] = 1 a[n−1][0]=a[n−1][n−1]=1
4. “每个数是它左上方和右上方的数的和”，类比组合数的递推公式：
   C n m = C n − 1 m + C n − 1 m − 1 = > a [ i ] [ j ] = a [ i − 1 ] [ j ] + a [ i − 1 ] [ j − 1 ] C_n^m = C_{n - 1}^m + C_{n - 1}^{m - 1} => a[ i ][ j ] = a[ i - 1 ][ j ] + a[ i - 1 ][ j - 1 ] Cnm​=Cn−1m​+Cn−1m−1​=>a[i][j]=a[i−1][j]+a[i−1][j−1]

    public List> generate(int numRows) {
        int[][] a = new int[numRows][numRows];
        for (int i = 0;i < numRows;i++){
            for (int j = 0;j <= i;j++){
                if (j == 0 || j == i){
                    //首尾为1
                    a[i][j] = 1;
                } else {
                    a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
                }
            }
        }
        //存入list集合
        List> list2 = new ArrayList<>();
        List list;
        for (int i = 0;i < a.length;i++){
            list = new ArrayList<>();
            for (int j = 0;j <= i;j++){
                list.add(a[i][j]);
            }
            list2.add(list);
        }
        return list2;
    }

119.杨辉三角II

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
0 <= rowIndex <= 33

• 这道题可以直接套用第一题的思路，直接输出指定rowIndex行的元素即可。
• 得益于昨天矩阵的其中一道题，涉及到一维数组与二维数组之间的转换，总算想到这道题的优化方法：通过将杨辉三角存到一个一维数组中降低空间复杂度

这道题大部分的规律我都是通过列举部分数据来总结得出：

1. 定义一维数组 int[] result，数组长度为：
   ( r o w I n d e x + 2 ) ( r o w I n d e x + 1 ) 2 frac{(rowIndex + 2) (rowIndex + 1)}{2} 2(rowIndex+2)(rowIndex+1)​，具体规律如下：（本质是等差数列求和）
   rowIndex = 0 , 长度为 1；
   rowIndex = 1，长度为 3；
   rowIndex = 2，长度为 6；
2. 将二维数组数据遍历存到一维数组 result 中（这里实际上是没有创建二维数组的，只是写了遍历二维数组的for循环）
3. 给定一个一维数组 result 的初始下标 index = 0，每遍历一个数据，就存到一维数组中，然后 index 自增。
4. 遍历到首尾元素时，元素为1，即： result[index++] = 1;
5. 【难点】由于实际上没有二维数组，所以存非首尾元素的数据不能直接通过组合数递推公式来做。这里又需要找规律：
   列出rowIndex = 4 数组 result 的元素：[1, 1,1, 1,2,1, 1,3,3,1, 1,4,6,4,1]

从上面的数据可以总结出以下规律：
result[index] = result[index - i] + result[index - i - 1];

6. 将赋值好的一维数组 result ，取出指定下标范围的元素，存到List集合中。
   1.由于杨辉三角对应层数的元素个数分别为：1,2,3,4,5…，所以：
   指定一维数组下标 = 该层数rowIndex以上全部层的元素个数之和（即等差数列求和）
   2.因此，遍历时 rowIndex 对应的一维数组下标范围为： [ ( r o w I n d e x + 1 ) ∗ r o w I n d e x / 2 , ( r o w I n d e x + 1 ) ∗ r o w i n d e x / 2 + r o w I n d e x ] [(rowIndex + 1) * rowIndex / 2,(rowIndex + 1) * rowindex / 2 + rowIndex] [(rowIndex+1)∗rowIndex/2,(rowIndex+1)∗rowindex/2+rowIndex]

    public List getRow(int rowIndex) {
        //将杨辉三角存到一个一维数组中
        int[] result = new int[(rowIndex + 2) * (rowIndex + 1) / 2];
        //一维数组初始下标
        int index = 0;
        for (int i = 0;i <= rowIndex;i++){
            for (int j = 0;j <= i;j++){
                if (j == 0 || j == i){
                    //首尾为1
                    result[index++] = 1;
                } else {
                    result[index] = result[index - i] + result[index - i - 1];
                    index++;
                }
            }
        }
        //存入list集合
        //遍历数组的下标范围[(rowIndex + 1) * rowIndex / 2,(rowIndex + 1) * rowindex / 2 + rowIndex]
        List list = new ArrayList<>();
        int i = (rowIndex + 1) * rowIndex / 2;
        int j = i;
        while (j <= i + rowIndex){
            list.add(result[j]);
            j++;
        }
        return list;
    }