仁怀市城乡建设网站,小程序开发制作工具,手机网站首页经典案例,北京开公司一年费用文章目录第一部分#xff1a;题目第二部分#xff1a;解法①-数学规律法2.1 规律分析2.2 代码实现2.3 需要思考第三部分#xff1a;解法②-记忆法#xff08;备忘录#xff09;第四部分#xff1a;对比总结第一部分#xff1a;题目
#x1f3e0; 链接#xff1a;119.…
文章目录第一部分题目第二部分解法①-数学规律法2.1 规律分析2.2 代码实现2.3 需要思考第三部分解法②-记忆法备忘录第四部分对比总结第一部分题目 链接119. 杨辉三角 II - 力扣LeetCode
⭐ 难度简单 第二部分解法①-数学规律法
2.1 规律分析 2.2 代码实现
public static ListInteger getRow(int rowIndex) {// 建立一个capacityrowIndex1的集合ArrayListInteger arrayList new ArrayList(rowIndex 1);// 设置第rowIndex行首位置的值long indexValue 1;// 遍历第rowIndex行所有位置for (int i 0;i rowIndex;i){// long强转为int,将indexValue加入集合发生了自动装包int-IntegerarrayList.add((int)indexValue);// 根据规律设置下一个好下一个位置的值indexValue indexValue*(rowIndex-i)/(i1);}return arrayList;
}
/*
这里有个细节我们定义indexValue时类型为long,为什么不设置为int类型这样便可以舍去加入集合时的强转过程这是因为如果将indexValue定义为int类型那么在代码第六行计算indexValue*(rowIndex-i)时由于indexValue,rowIndex和i都为int那么indexValue*(rowIndex-i)的结果也为int但是当rowIndex过大时计算该行某些位置时indexValue*(rowIndex-i)的值会超过int的范围导致这个值为负数。因此我们定义类型为long的话由于long的精度比int高而indexValue*(rowIndex-i)的结果自然为long类型且没有超过long的取值范围所以indexValue*(rowIndex-i)得到的便会是正常结果,而非因为数据溢出结果变为负数
*/2.3 需要思考
我们定义indexValue时类型为long,为什么不设置为int类型这样便可以舍去加入集合时的强转过程。
这是因为如果将indexValue定义为int类型那么在代码第六行计算 indexValue * ( rowIndex - i ) 时由于 indexValue , rowIndex 和 i 都为int那么 indexValue * ( rowIndex - i ) 的结果也为int。但是当rowIndex过大时计算该行某些位置时indexValue*(rowIndex-i)的值会超过int的范围导致这个值为负数。
因此我们定义类型为long的话由于long的精度比int高而indexValue*(rowIndex-i)的结果自然为long类型且没有超过long的取值范围所以indexValue * ( rowIndex - i ) 得到的便会是正常结果而非因为数据溢出结果变为负数。
第三部分解法②-记忆法备忘录 Memoization 记忆法也称备忘录是一种优化技术通过存储函数调用结果通常比较昂贵当再次出现相同的输入子问题时就能实现加速效果 public ListInteger getRow(int rowIndex) {ArrayListInteger list new ArrayList(rowIndex 1);// 设置首元素的值为1list.add(1);// 从第二行行索引为1开始遍历for (int i 1; i rowIndex; i) {for (int j i - 1; j 0; j--) {// 规律 [i][j] 的取值应为 [i-1][j-1] [i-1][j]list.set(j, list.get(j - 1) list.get(j));}// 末尾元素的值为1list.add(1);}return list;}第四部分对比总结
我们来看下两种方法的执行效率
1️⃣ 数学规律法 2️⃣ 记忆法 很明显数学规律法花费的时间更少这是因为 数学规律法 只需要我们逐一计算第 rowIndex 行每个元素的值即可而 记忆法 需要我们从第0行开始计算每一行每一个元素的值。
