大家好,我是千与千寻,最近更新的有点频繁啊,主要是最近感觉学到了太多有用的东西,想来和大家分享。
上一期我们分享了LeetCode算法题目中的股票交易合集,今天我们来讲解一下LeetCode中的一个特例——杨辉三角问题合集。更多题解合集持续关注我,编程能力的提高,需要用算法题的刷题数量来喂出来的,下面我们直接进入技术环节!
另外,各位最近的股票基金怎么样了,不用说了,都是泪啊~
所以还是要说投资是一场持久战,就如同人生一样,一时的失利,那算不了什么,只要我们坚持心中的目标,终会有实现的一天,白酒,反弹!
在本次的算法题解中我们介绍杨辉三角的题目,涉及杨辉三角的题目一共有两道,分别为LeetCode118,以及LeetCode119,我们逐一进行讲解。
LeetCode 118:
杨辉三角 I:
给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
测试示例:
输入: 5输出:[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
思路解析:
针对本道题目我们需要先进行思路的转换,
因为我们总是将杨辉三角想像成为等腰三角形
但是这样其实很不利于思路的构建,
因为本题中的数据结构其实是一个二维数组,
而且是一个首位对齐的二维数组,
本题的关键在于搞清楚杨辉三角整体的计算规律,
其计算公式为下一层的数字为上一层数组的两个相邻数字相加之和
搞清楚了杨辉三角的本质,我们看一下具体的算法步骤。
算法流程:
(1)新建一个二维数组list,用于最终结果的返回
(2)搭建每一层的杨辉三角元素存储数组,用于存放杨辉三角的数组
(3)根据杨辉三角的外部元素特点,对索引为0,以及索引为当前所在层
最右端的元素进行赋值为1的操作
(4)如果不是最外围的元素,我们对其进行公式的计算,
第i行杨辉三角的第j个元素等于:
第i-1行第j-1的元素与第i-1行的第j个元素进行相加。
(5)将当前的计算得到的杨辉三角所在行
放入整个杨辉三角的二维数组
(6)返回整个杨辉三角的二维数组即可
编写代码:
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list = new ArrayList();
for(int i=0;i<numRows;i++){
List<Integer> res = new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0||j==i){
res.add(1);
}else{
res.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
}
}
list.add(res);
}
return list;
}
}
LeetCode 119:
给定一个非负索引 k,其中k ≤ 33,返回杨辉三角的第k行。
测试示例:
输入: 3输出: [1,3,3,1]
思路解析:
本题与上一道题的原理是相同的,只不过上一道题目要求输出的是整个的杨辉三角二维数组,本题目输出的为其中一层的数组。因此整体构建的是杨辉三角的内容也是相同的。仅仅需要在实际的编码中对二维数组的输出进行修改。其计算公式为下一层的数字为上一层数组的两个相邻数字相加之和搞清楚了杨辉三角的本质,我们看一下具体的算法步骤。
算法流程:
(1)新建一个二维数组list,用于最终结果的返回(2)搭建每一层的杨辉三角元素存储数组,用于存放杨辉三角的数组
(3)根据杨辉三角的外部元素特点,对索引为0,以及索引为当前所在层最右端的元素进行赋值为1的操作(4)如果不是最外围的元素,我们对其进行公式的计算,第i行杨辉三角的第j个元素元素为第i-1行第j-1的元素与第i-1行的第j个元素进行相加。(5)将当前的计算得到的杨辉三角所在行放入整个杨辉三角的二维数组(6)返回对应索引的杨辉三角对应行数的一维数组即可。
编写代码:
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> list = new ArrayList();
for(int i=0;i<=rowIndex;i++){
List<Integer> res = new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0||j==i){
res.add(1);
}else{
res.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
}
}
list.add(res);
}
return list.get(rowIndex);
}
}
············END············
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有