LeetCode 118:杨辉三角 II Pascal's Triangle II
公众号:爱写bug(ID:icodebugs)
作者:爱写bug
给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。
Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
Note that the row index starts from 0.
在杨辉三角中,每个数是它左上方和右上方的数的和。
In Pascal's triangle, each number is the sum of the two numbers directly above it.
示例:
输入: 3 输出: [1,3,3,1]
进阶:
你可以优化你的算法到 O(k) 空间复杂度吗?
解题思路:
和之前写的那篇118号杨辉三角基本类似。这道题只是不用考虑每行输出,只输出最后一行。这样只在一个数组上修改即可:该数 的值 = 该数的值+该数左边的值之和(该数不包括第一个和最后一个数)。
这道题只是不用考虑每一行输出,只输出最后一行。这样只在一个数组上修改即可:该数 的值 = 该数的值+该数左边的值之和(该数不包括第一个和最后一个数)。
用两个嵌套循环,外循环是要计算的每行数组,内循环在上一次计算的数组基础上更改数值得出该行数组。
需要注意的是:内循环 j 指针应该从每行的最后一个数开始更改。
如果 j 指针从左开始更改索引的值:
[1]
[1,1]
[1,2,1] 索引1 的值是索引 0 和 1的和,没问题
[1,3,4,1] 索引2 的值是索引 2 和索引 1的和 为4,而不是预期的3
因为我们是在同一个数组里更改每个数值的,所以如果做左边开始求值,索引 1 的值会从2变为3,此时计算索引2的值,由于该索引左边的值已经改变为3,该索引将不再是预期值。
起先我用的是 ArrayList<Integer>()
:
class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> nums = new ArrayList<Integer>(); nums.add(1); for (int i = 1; i <= rowIndex; i++) { for (int j = i - 1; j > 0; j--) { nums.set(j, nums.get(j) + nums.get(j - 1)); } nums.add(1); System.out.println(nums); } return nums; } }
提交时虽然能通过但是每次调用 set()、add() 导致性能很差很差。
Java:
class Solution { public List<Integer> getRow(int rowIndex) { Integer[] nums = new Integer[rowIndex+1];//所有值被默认置为0 Arrays.fill(nums, 0); nums[0] = 1; for (int i = 1; i <= rowIndex; i++) { for (int j = i; j >0; j--) { nums[j] = nums[j] + nums[j-1];//当j为1时,nums[j]为0,不影响最后一个值,不用单独给每行末尾赋值1 } } return Arrays.asList(nums);//转为List<Integer>型并返回 } }
Python3:
class Solution: def getRow(self, rowIndex: int) -> List[int]: nums = [1] for i in range(1, rowIndex+1): for j in range(i-1, 0, -1): nums[j] +=nums[j-1] nums.append(1) # 需要给末尾索引赋值1 return nums
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Python3入门(六)迭代器和生成器
本文介绍如何在python中使用迭代器和生成器 一、迭代器 迭代是Python最强大的功能之一,是访问集合元素的一种方式。迭代器是一个可以记住遍历的位置的对象。迭代器对象从集合的第一个元素开始访问,直到所有的元素被访问完结束。迭代器只能往前不会后退。迭代器有两个基本的方法:iter() 和 next()。字符串,列表或元组对象都可用于创建迭代器示例: list1 = ["a", "b", "c"] # 创建迭代器对象 ll = iter(list1) # 输出下一个元素 print(next(ll)) # 输出:a 1、创建一个迭代器 把一个类作为一个迭代器使用需要在类中实现两个方法 __iter__() 与 __next__() 。如果你已经了解的面向对象编程,就知道类都有一个构造函数,Python 的构造函数为 __init__(),
- 下一篇
在php中调用接口以及编写接口
在php中调用接口以及编写接口如:http://localhost/openUser.php?act=get_user_list&type=json 在这里openUser.php相当于一个接口,其中get_user_list 是一个API(获取用户列表),讲求返回的数据类型为JSON格式。 你只需要在你PHP代码中执行这条链接他就会返回。GET方式的直接使用 $file_contents = file_get_content('http://localhost/openUser.php?act=get_user_list&type=json') POST方式得用下面的(需要开启PHP curl支持)。 $url = 'http://localhost/openUser.php?act=get_user_list&type=json';$ch = curl_init ();curl_setopt ( $ch, CURLOPT_URL, $url );curl_setopt ( $ch, CURLOPT_RETURNTRANSFER, 1 );curl_setop...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- Red5直播服务器,属于Java语言的直播服务器
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Docker安装Oracle12C,快速搭建Oracle学习环境
- CentOS6,CentOS7官方镜像安装Oracle11G
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- CentOS关闭SELinux安全模块
- CentOS7编译安装Gcc9.2.0,解决mysql等软件编译问题
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16