LeetCode每日一练（杨辉三角）

素颜马尾好姑娘i 2022-10-18 15:59 158阅读 0赞

直接看题：

> 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。  
> 在杨辉三角中，每个数是它左上方和右上方的数的和。  
> 示例:  
> 输入: 3  
> 输出: \[1,3,3,1\]

题目要求的是给定一个非负索引k，要求得到杨辉三角中的第k行，杨辉三角相信大家都不陌生了吧，不明白的同学去百度一下补补课呦。

对于这道题，因为给定了索引k的取值范围，所以我们可以先求出33行的杨辉三角存入一个二维数组，然后根据k的具体值返回对应一行的数据；那么具体代码该如何写呢？我们先来分析一下：  
![在这里插入图片描述][20210708165119150.png]  
可以很容易发现其中的规律，首先第1行有1个数值，第2行有2个数值，第3行有3个数值，以此类推，第i行就有i个数值；其次，对于每一行，其第一个和最后一个元素值均为1，由此可以得出如下代码：

@Test
        public void test() { 
            // 因为k小等于33，最多需要计算33行
            int[][] nums = new int[32][];
            // 对于第i行，其均有i列
            for (int i = 0; i < nums.length; ++i) { 
                nums[i] = new int[i + 1];
            }
            for (int i = 0; i < nums.length; ++i) { 
                for (int j = 0; j < nums[i].length; ++j) { 
                    if (j == 0 || j == i) { 
                        // 每一行的第一个和最后一个元素均为1
                        nums[i][j] = 1;
                    }
                }
            }
            for (int[] num : nums) { 
                for (int n : num) { 
                    System.out.print(n + "\t");
                }
                System.out.println();
            }
        }

运行结果：

1	
    1	1	
    1	0	1	
    1	0	0	1	
    1	0	0	0	1	
    1	0	0	0	0	1	
    1	0	0	0	0	0	1	
    1	0	0	0	0	0	0	1	
    ......

现在的关键在于这些0位置上的元素值该如何计算？仔细观察杨辉三角的结构，也不难发现这个规律：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]  
这些值均由它对应的上一行元素值加上一行元素的前一个元素值所得，比如：第五行的6，它就由对应的上一行元素值3和3的前一个元素值3相加所得，由此继续改造代码：

@Test
        public void test() { 
            // 因为k小等于33，最多需要计算33行
            int[][] nums = new int[32][];
            // 对于第i行，其均有i列
            for (int i = 0; i < nums.length; ++i) { 
                nums[i] = new int[i + 1];
            }
            for (int i = 0; i < nums.length; ++i) { 
                for (int j = 0; j < nums[i].length; ++j) { 
                    if (j == 0 || j == i) { 
                        // 每一行的第一个和最后一个元素均为1
                        nums[i][j] = 1;
                    }else { 
                        // 对于其它位置，其值等于对应上一行的元素值加对应上一行元素的前一个元素值
                        nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
                    }
                }
            }
            for (int[] num : nums) { 
                for (int n : num) { 
                    System.out.print(n + "\t");
                }
                System.out.println();
            }
        }

运行结果：

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
    ......

现在已经得到了杨辉三角，只需根据给定的k值获取对应一行的数组值即可，最后的代码：

@Test
        public void test() { 
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入k值:");
            int k = sc.nextInt();
            // 因为k小等于33，最多需要计算33行
            int[][] nums = new int[k][];
            // 对于第i行，其均有i列
            for (int i = 0; i < nums.length; ++i) { 
                nums[i] = new int[i + 1];
            }
            for (int i = 0; i < nums.length; ++i) { 
                for (int j = 0; j < nums[i].length; ++j) { 
                    if (j == 0 || j == i) { 
                        // 每一行的第一个和最后一个元素均为1
                        nums[i][j] = 1;
                    } else { 
                        // 对于其它位置，其值等于对应上一行的元素值加对应上一行元素的前一个元素值
                        nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
                    }
                }
            }
            // 获取k行数据
            int[] num = nums[k - 1];
            List<Integer> list = new ArrayList<>();
            for (int i : num) { 
                list.add(i);
            }
            System.out.println(list);
            sc.close();
        }

运行结果：

请输入k值:
    6
    [1, 5, 10, 10, 5, 1]

由于LeetCode中有输入输出的条件限制，所以仍然需要修改代码：

import java.util.Scanner;
    
    class Solution { 
        public List<Integer> getRow(int rowIndex) { 
            int[][] nums = new int[rowIndex + 1][];
            // 对于第i行，其均有i列
            for (int i = 0; i < nums.length; ++i) { 
                nums[i] = new int[i + 1];
            }
            for (int i = 0; i < nums.length; ++i) { 
                for (int j = 0; j < nums[i].length; ++j) { 
                    if (j == 0 || j == i) { 
                        // 每一行的第一个和最后一个元素均为1
                        nums[i][j] = 1;
                    } else { 
                        // 对于其它位置，其值等于对应上一行的元素值加对应上一行元素的前一个元素值
                        nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
                    }
                }
            }
            // 获取k行数据
            int[] num = nums[rowIndex];
            List<Integer> list = new ArrayList<>();
            for (int i : num) { 
                list.add(i);
            }
            return list;
        }
    }

需要注意的是，题目示例的第三行结果是\[1,3,3,1\]：  
![在这里插入图片描述][20210708172233438.png]  
说明它是从第0行开始计算的，注意这个细节，最后当然就是代码通过测试了：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 1]  
这道题到这里就算是结束了，但是题目仍然给了一个进阶要求：

> 进阶：你可以优化你的算法到 O(k) 空间复杂度吗？

对于刚才的程序，我们可以计算一下空间复杂度，对于一个k行的数组，其空间复杂度为(1 + k) \* k / 2，可见对于空间的消耗是比较大的，那么有没有一个办法能够将空间复杂度降到O(k)，也就是仅使用一个容量为k的数组实现这一需求呢？

想象一下，对于某一行的杨辉三角数据，其值应该是上方元素值加左上方元素值，所以，我们完全可以将每一行的数据先存在一个一维数组中，再通过它求出接下来的每一行，比如求第3行的元素值，那么首先需要得出第一行，第一行的元素值就只有一个1：  
![在这里插入图片描述][20210708175145494.png]  
对于第二行，它的元素值为2个1：  
![在这里插入图片描述][20210708175218310.png]  
但很显然，我们不能这么做，因为这会导致接下来的每一行都无法正确计算，应该在计算除第一行外的每一行开始前放置一个值0作为占位  
![在这里插入图片描述][20210708175535227.png]

此时我们只需每次都从右往左反推出该位置上的元素值即可，对于第二行的最后一个元素，其值等于上方和左上方的值相加，也就是索引0和索引1位置上的元素值相加，得到1重新赋值给索引1：  
![在这里插入图片描述][20210708175603199.png]  
接着计算第3行，第3行有3个元素值，在计算前先添加一个值0：  
![在这里插入图片描述][20210708175646784.png]  
此时从右往左计算，最后一个元素值等于索引1和索引2位置上的元素值相加，结果为1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 2]

倒数第二个元素值等于索引0和索引1位置上的元素值相加，结果为2：  
![在这里插入图片描述][2021070818063866.png]

然后继续添0：  
![在这里插入图片描述][2021070818010671.png]  
以同样的方式继续计算，最后一个元素值等于索引3和索引2位置上（其实也就是当前位置加上左边位置）的元素值，结果为1：  
![在这里插入图片描述][20210708180819934.png]  
继续求解：  
![在这里插入图片描述][20210708180902947.png]  
继续往左求解：  
![在这里插入图片描述][20210708180952980.png]  
这个过程虽然有点绕，但其实也很好理解，对于为什么要进行添0操作，我们完全可以从杨辉三角的构造中得到答案：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 3]  
对于每一行的元素值，都需要先知晓其前一行的元素分布，首先第0行和每一行的第一个元素都不需要考虑，值肯定是1，所以我们从每一行的最后开始计算，一直计算到第一个元素值停止，这些位置上的元素值都等于上方加左上方的元素值，比如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 4]  
第1行的第2个元素1就应该由上方的0和左上方的1相加得到，但因为现在只有一个数组了，所以添0是必须的，0充当的就是最后一个元素的上方元素值，由此得到规律，对于每个元素值，其都等于一维数组中当前位置的元素值加上前一个位置的元素值之和。

最终可以得出代码：

class Solution { 
        public static List<Integer> getRow(int rowIndex) { 
            List<Integer> nums= new ArrayList<Integer>();
            nums.add(1);
            for (int i = 1; i <= rowIndex; ++i) { 
                nums.add(0);
                for (int j = i; j > 0; --j) { 
                    nums.set(j, nums.get(j) + nums.get(j - 1));
                }
            }
            return nums;
        }
    }

这样就把空间复杂度成功降至O(k)。

[20210708165119150.png]: /images/20221005/71aaff0b58ef42248347756147003fb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]: /images/20221005/3343b5ffe3af49838d27755192113cd8.png
[20210708172233438.png]: /images/20221005/4c13dbafba3f448eb55be96b90c2da59.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 1]: /images/20221005/da9ce7a51c4e4415b6b0f9c34bad1d4e.png
[20210708175145494.png]: /images/20221005/41c606cad747469e8f6561d56ca8f7a4.png
[20210708175218310.png]: /images/20221005/4a2721d7bee04983a418de674dd6bed7.png
[20210708175535227.png]: /images/20221005/94bcd7e5568a44ad8d4dbad72795f927.png
[20210708175603199.png]: /images/20221005/cde81e76c8b540e88220a45816526427.png
[20210708175646784.png]: /images/20221005/b7f8edb6567b4cdb8788868624286e6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 2]: /images/20221005/2cc330be0c904655a8f4a61b3408e9d7.png
[2021070818063866.png]: /images/20221005/1956b88e73f647b6a9eafd22e32eb1e5.png
[2021070818010671.png]: /images/20221005/e528043de1c34d1992b8f13d30284b57.png
[20210708180819934.png]: /images/20221005/3ccd915fcad9402ab79d4b07c3bca211.png
[20210708180902947.png]: /images/20221005/40dd300523af446791f1eef507d2b8a3.png
[20210708180952980.png]: /images/20221005/5a9ae63d51994863a16dbf31e1db7acd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 3]: /images/20221005/f40e809bb6534c91b60184f4acb2db4a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 4]: /images/20221005/fdc12a626f1e4041a0f7e38476480dcc.png