前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode-119. 杨辉三角II(java)

LeetCode-119. 杨辉三角II(java)

作者头像
bug菌
发布2023-05-27 15:16:08
1580
发布2023-05-27 15:16:08
举报

一、前言:

👨‍🎓作者:bug菌 ✏️博客:CSDN​、掘金等 💌公众号:​​猿圈奇妙屋​​ 🚫特别声明:原创不易,转载请附上原文出处链接和本文声明,谢谢配合。 🙏版权声明:文章里可能部分文字或者图片来源于互联网或者百度百科,如有侵权请联系bug菌处理。

二、题目描述:

题目:

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

LeetCode-119. 杨辉三角II(java)_杨辉三角
LeetCode-119. 杨辉三角II(java)_杨辉三角

 具体请看如下示例:

示例 1:

代码语言:javascript
复制
输入: rowIndex = 3
 输出: [1,3,3,1]

示例 2:

代码语言:javascript
复制
输入: rowIndex = 0
 输出: [1]

示例 3:

代码语言:javascript
复制
输入: rowIndex = 1
 输出: [1,1]

提示:

  • ​0 <= rowIndex <= 33​

题目来源: ​​LeetCode官网​​题目难度:⭐⭐

三、思路分析:

       这题我一开始拿到以为是直角形状的杨辉三角,其实不然,这题在我上题所解的非常类似​​《LeetCode118.杨辉三角》​​​。无非此题就是在上期的基础上,按要求返回指定行的数据进行返回。其实思路也很简单,你既然能按照指定的行数输出数据,那你也可以指定输出某一行的数据,对吧,你只需要最后在结果集上 ​​return list.get(rowIndex)​​即可。

  • 每一行的开始和结尾数字都为1。
  • 第​​n+1​​​行的第i个数字等于第​​n​​​行的​​i-1​​​个数字加上第 ​​n​​​ 行的i个数字。用二维数组表示就是 ​​a[i+1][j]=a[i][j-1]+a[i][j]​
  • 然后按指定num进行输出即可。

       别想着用递归啊,我试过了,通过不了力扣的测试用例的。

LeetCode-119. 杨辉三角II(java)_List_02
LeetCode-119. 杨辉三角II(java)_List_02

四、算法实现:

AC代码

具体算法代码实现如下:

代码语言:javascript
复制
class Solution {
     public List<Integer> getRow(int rowIndex) {
         //定义一个二维集合。
         List<List<Integer>> ret = new ArrayList<List<Integer>>();
         for (int i = 0; i <= rowIndex; i++) {
             List<Integer> row = new ArrayList<Integer>();
             //由于只是给杨辉三角内的位置赋值,所以是j<=i
             for (int j = 0; j <= i; j++) {
                 //根据规律,使用if else 赋值
                 //头尾都是1
                 if (j == 0 || j == i) {
                     row.add(1);
                 } else {
                     row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                 }
             }
             ret.add(row);
         }
         //直接返回该行即可
         return ret.get(rowIndex);
     }
 }

五、总结:

leetcode提交运行结果截图如下:

LeetCode-119. 杨辉三角II(java)_杨辉三角_03
LeetCode-119. 杨辉三角II(java)_杨辉三角_03

复杂度分析:

  • 时间复杂度:O(rowIndex^2)。
  • 空间复杂度:O(1)。不考虑返回值的空间占用。

       这题其实就没啥好讲的啦,再做不出来,就该伸出手来打了啊,毕竟看过我上一期的讲解,这道题无非就是在上一道题上指定返回集合中的某一行,这还不简单么,是吧,但是可能也有小伙伴们是直接看到我这题的,所以就建议没做杨辉三角I 的同学可以看看我这期​​《LeetCode118.杨辉三角》​​。

       再者,解题道路千万条,欢迎小伙伴们脑洞大开,如果你们有啥更好的想法或者思路,欢迎评论区告诉我哦,大家一起互相借鉴互相学习,方能成长的更快。

       好啦,以上就是本期的所有内容啦,咱们下期见咯。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-02-02,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、前言:
  • 二、题目描述:
  • 三、思路分析:
  • 四、算法实现:
  • 五、总结:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档