phpcms 手机网站模板,手机网站开发总结,wordpress execl,建筑工程公司起名字大全目录
题目链接#xff1a;118. 杨辉三角 - 力扣#xff08;LeetCode#xff09;
题目描述
示例
提示:
解法一#xff1a;利用特性构建杨辉三角
1. 结果存储结构#xff1a;
2. 初始化和循环遍历每一层#xff1a;
3. 构建每一层#xff1a;
4. 填充中间的元素118. 杨辉三角 - 力扣LeetCode
题目描述
示例
提示:
解法一利用特性构建杨辉三角
1. 结果存储结构
2. 初始化和循环遍历每一层
3. 构建每一层
4. 填充中间的元素
5. 添加最后一个元素
6. 将当前行添加到结果集
7. 更新 len
8. 返回最终结果
Java写法
C写法
运行时间
时间复杂度和空间复杂度
解法二递归
递归思路
Java写法
C写法
关键变化 运行时间
时间复杂度和空间复杂度
解法三不讲武德版面向测试用例编程
Java写法
运行时间
总结
解法总结
小结 题目链接118. 杨辉三角 - 力扣LeetCode
注下述题目描述和示例均来自力扣 题目描述
给定一个非负整数 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 解法一利用特性构建杨辉三角
1. 结果存储结构
这里使用 ListListInteger 来存储杨辉三角的每一行数据。res 是最终返回的结果集它是一个二维列表存放着每一层的数组。
2. 初始化和循环遍历每一层
len 代表当前层的元素个数。每一层的元素个数是递增的从 1 开始。numRows 是杨辉三角的行数for 循环遍历每一行numberOfLayers 代表当前的行索引从 0 开始。
3. 构建每一层
每一行是一个 ListInteger并且我们首先将 1 加入到列表中因为每一行的第一个元素总是 1。
4. 填充中间的元素
中间的元素是由上一行的相邻两个元素相加得到的。res.get(numberOfLayers - 1) 取得上一行的数据然后 get(i) 取得上一行中第 i 个元素get(i - 1) 取得上一行中第 i - 1 个元素将它们相加并将结果添加到当前行 one 中。i 从 1 开始到 len - 2因为第一个和最后一个元素已经加到 one 中了。
5. 添加最后一个元素
除了第一行所有的行最后一个元素都是 1所以通过判断当前层是不是第一层来决定是否添加最后一个元素 1。
6. 将当前行添加到结果集
每次生成一行后将它添加到 res 中。
7. 更新 len
每次处理完一层后len 增加 1因为下一行的元素个数比当前行多一个。
8. 返回最终结果
最终返回 res即生成的完整杨辉三角。 Java写法
class Solution {public ListListInteger generate(int numRows) {// 定义出返回的结果集ListListInteger res new ArrayList();// 1// 1 1// 1 2 1// 1 3 3 1// 1 4 6 4 1// 那么其实我们把杨辉三角抽象到我们的二维数组链表中// 就是边上的数都是1中间的数是上一个数组中当前索引的数前一个索引的数// 定义出 len 表示一层的数量 1,2,3...int len 1;// numberOfLayers表示层数for(int numberOfLayers 0; numberOfLayers numRows; numberOfLayers){// 记录一层的数据ListInteger one new ArrayList();one.add(1);int i 1;for(;i len - 1; i){// 将两数相加再放入列表one.add(res.get(numberOfLayers - 1).get(i) res.get(numberOfLayers - 1).get(i - 1));}if(numberOfLayers ! 0){one.add(1);}res.add(one);len;}return res;}
}
C写法
C 中没有 List 类型通常使用 vector 来替代。同时在 C 中我们也使用 vectorvectorint 来表示二维数组。代码结构与 Java 类似。
#include vector
using namespace std;class Solution {
public:vectorvectorint generate(int numRows) {// 定义返回的结果集vectorvectorint res;// numberOfLayers表示层数for (int numberOfLayers 0; numberOfLayers numRows; numberOfLayers) {// 记录当前行的数据vectorint one;one.push_back(1); // 每行的第一个元素为1// 中间元素是上一行的相邻元素之和for (int i 1; i numberOfLayers; i) {one.push_back(res[numberOfLayers - 1][i - 1] res[numberOfLayers - 1][i]);}// 每行的最后一个元素为1除了第一行if (numberOfLayers 0) {one.push_back(1);}// 将当前行添加到结果集res.push_back(one);}return res;}
};运行时间 时间复杂度和空间复杂度 时间复杂度 外层循环遍历每一行循环次数为 numRows即 O(n)。内层循环对每一行的元素进行处理每一行最多有 numRows 个元素最坏情况下是 O(n)。因此时间复杂度是 其中 n 是杨辉三角的行数。 空间复杂度 结果 res 存储了每一行的元素空间复杂度为 即每一行的元素数量之和1 2 3 ... n是 。 解法二递归
递归思路
递归起始初始时杨辉三角的第一行 [1] 被添加到 list 中。递归生成每一行 每次递归调用都会生成当前行并添加到 list 中。当前行通过上一行的元素计算得出首先是第一个 1然后是中间的元素通过相邻两个元素之和得出最后是尾部的 1。递归终止当生成的行数等于 numRows 时停止递归。 Java写法
class Solution {public ListListInteger generate(int numRows) {// 初始化存储杨辉三角的二维列表ListListInteger list new ArrayList();// 初始化第一行 [1]ListInteger arr new ArrayList();arr.add(1);list.add(arr);// 如果只需要生成第一行直接返回if(numRows 1) return list;// 否则递归生成剩下的行method(numRows, list, arr);return list;}void method(int number, ListListInteger list, ListInteger arr){// 如果已经生成了所需的行数则停止递归if(list.size() number){return;}// 初始化新的一行ListInteger newArr new ArrayList();newArr.add(1); // 每一行的第一个元素是1// 计算中间的元素通过上一行相邻元素之和填充for(int i 0; i arr.size() - 1; i) {newArr.add(arr.get(i) arr.get(i 1));}newArr.add(1); // 每一行的最后一个元素是1list.add(newArr); // 添加当前行到结果中// 递归生成下一行method(number, list, newArr);}
}C写法
关键变化
vector 替换 ListC 中没有 List 类改为使用 vector这是 C 标准库中最常用的动态数组类型。push_back 替代 addC 的 vector 使用 push_back() 方法来添加元素替代 Java 中的 add() 方法。引用传递为了提高性能method 函数中的 list 和 arr 都采用了引用传递vectorint 和 vectorvectorint这样可以避免复制数据。 #include vector
using namespace std;class Solution {
public:vectorvectorint generate(int numRows) {// 初始化存储杨辉三角的二维向量vectorvectorint list;// 初始化第一行 [1]vectorint arr {1};list.push_back(arr);// 如果只需要生成第一行直接返回if (numRows 1) return list;// 否则递归生成剩下的行method(numRows, list, arr);return list;}private:void method(int number, vectorvectorint list, vectorint arr) {// 如果已经生成了所需的行数则停止递归if (list.size() number) {return;}// 初始化新的一行vectorint newArr {1}; // 每一行的第一个元素是1// 计算中间的元素通过上一行相邻元素之和填充for (int i 0; i arr.size() - 1; i) {newArr.push_back(arr[i] arr[i 1]);}newArr.push_back(1); // 每一行的最后一个元素是1list.push_back(newArr); // 添加当前行到结果中// 递归生成下一行method(number, list, newArr);}
};运行时间 就离谱测试用例比较有特点导致的多跑几次可以遇到一次0ms 的情况这种操作在力扣不是第一次出现了居然比下面的不讲武德版本还快无语了 时间复杂度和空间复杂度
时间复杂度O(n^2)生成杨辉三角时生成每行的元素需要遍历前一行的元素所以总时间复杂度为二次方。空间复杂度O(n^2)需要存储杨辉三角的所有行每一行的元素个数是递增的空间复杂度也是二次方。 解法三不讲武德版面向测试用例编程 这么搞笑的解法在我看见只有 这么点数据的时候我就发现了非常抽象哈。
Java写法
class Solution {public ListListInteger 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集合之中ListListInteger list new ArrayList();for (int i 0; i numRows; i) {list.add((ListInteger)Arrays.asList(a[i]));}// 直接返回即可return list;}
} 运行时间 没啥提升我是没有想到的过于离谱了还是。 总结
解法总结 解法一迭代构建 使用二维数组 ListListInteger 存储杨辉三角。从第一行 [1] 开始逐行构建每行的首尾元素为 1中间的元素为上一行相邻两个元素之和。时间复杂度O(n^2)空间复杂度O(n^2)。 解法二递归构建 递归地生成每一行通过上一行的元素计算当前行的值。时间复杂度O(n^2)空间复杂度O(n^2)。 解法三硬编码 直接定义一个二维数组包含了杨辉三角的所有行。适用于测试用例数较少的情况时间复杂度和空间复杂度均为常数级别。
小结
解法一和解法二通过动态计算逐行生成杨辉三角适合处理较大的 numRows 值。解法三虽然效率较高但不具通用性只适用于有限的 numRows 值。
