问题描述:
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1]
.
Note:
Could you optimize your algorithm to use only O(k) extra space?
原问题链接:https://leetcode.com/problems/pascals-triangle-ii/
问题分析
从实现的情况来看,这个问题的实现思路和前一个还稍微有点不一样。前一个是要求记录所有到第k个的三角序列,而这里只要记录第k个。而从前面要求来看,k = 3的时候,它这一行有4个元素,那么对于第k个序列来说,它这一行应该有k + 1个元素。
因为题目中要求使用O(k) 的空间,所以我们不能不断的申请空间。在这里可以使用两个k + 1长度的数组。int[] pre, int[]cur。我们最初始的情况是一个仅仅包含有数字1的元素。所以需要将pre[0] = 1。然后每次我们通过pre进行转换得到cur,然后再将cur和pre互换。在实现里我们需要定义一个两层的循环,一层表示从1到rowIndex,表示当前构造的是第几行,而里面的循环则是根据前一行进行转换。我们可以先将cur[0], cur[row]设置为1,而对于里面的每个元素,则有cur[i] = pre[i] + pre[i-1]。
详细的代码实现如下:
public class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> res = new ArrayList<>(); int curr[] = new int[rowIndex + 1]; int prev[] = new int[rowIndex + 1]; prev[0] = 1; for(int row = 1; row <= rowIndex; row++) { curr[0] = 1; curr[row] = 1; for(int i = 1; i < row; i++) curr[i] = prev[i] + prev[i - 1]; int[] swap = curr; curr = prev; prev = swap; } for(int i = 0; i <= rowIndex; i++) res.add(prev[i]); return res; } }
相关推荐
主要介绍了基于Java实现杨辉三角 LeetCode Pascal's Triangle的相关资料,需要的朋友可以参考下
Pascal's Triangle Given two sorted integer arrays A and B, merge B into A as one sorted array.Note: You may assume that A has enough space (size that is greater or equal to m + n)to hold additional ...
leetcode添加元素使和等于 Leetcode Part1 共55道 1 plusOne easy 描述:用一组数据表示一个整数,实现整数加一的操作 主要思路:主要考虑最高位进位的情况,可以创建一个长度加一的...Pascal's Triangle II easy 描
Pascal's Triangle (杨辉三角) 124 二叉树最大路径和 136 x ^ x = 0 169 Majority Vote Algorithm (最大投票数算法) 240 检索二阶矩阵 189 数组操作的时间复杂度比较 206 反转单向链表 226 反转二叉树 459 重复子...
119_Pascal's_Triangle_II 169_Majority_Element 229_Majority_Element_II 274_H_索引 275_H_Index_II 217_Contain_Duplicate 55_Jump_Game 45_Jump_Game_II 121_Best_Time_to_Buy_and_Sell_Stock 122_Best_Time_to_...
462 | [Minimum Moves to Equal Array Elements II](https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/) | [C++](./C++/minimum-moves-to-equal-array-elements-ii.cpp) [Python](./Python/...
Pascal's Triangle easy O O 119 Pascal's Triangle II easy O 要满足只用一个array大小空间O(k) k为input大小来完成,须具备backtracking概念 151 Reverse Words in a String medium O 这题有点算是easy的程度, ...
leetcode-js Leecode 经典题目 JavaScript TypeScript 题解。 Leetcode's answers by JavaScript and TypeScript. easy 66.加一 (Plus One) 67.二进制求和 (Add Binary) ...119.杨辉三角 II (Pascal's Triangle)
2.使用数组作为带符号的缓冲区118.Pascal's Triangle -> 理解结构并做167 Two Sum II - 输入数组已排序:使用排序数组的条件,使用前后两个指针35.Search Insert Position -> 线性搜索/二分搜索(左右各有1个间隙) ...
Pascal's Triangle v. Merge Sorted Array vi. Sum vii. Find Minimum in Rotated Sorted Array viii. Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. ...
Pascal's Triangle #0121 - Best Time to Buy and Sell Stock #0125 - Valid Palindrome #0136 - Single Number #0167 - Two Sum - Input Array is sorted #0189 - Rotate Array #0217 - Contains Duplicate #0242 -...
Pascal's Triangle II Spiral Matrix Spiral Matrix II ZigZag Conversion Divide Two Integers Text Justification Max Points on a Line Community QQ 群: 237669375 Github: ...
leetcode SDE-问题 标准 SDE 问题列表 第一天:(数组) 日 问题陈述 解决方案 困难 使用的数据结构 使用的算法 时间复杂度 空间复杂度 补充阅读 在 N 个整数的数组中查找重复项 中等的 大批 不适用 上) O(1) 在不...