首页 > 代码库 > leetcode----------Pascal's Triangle II

leetcode----------Pascal's Triangle II

2024-10-30 19:19:02   205人阅读

题目

Pascal‘s Triangle II

通过率29.8%
难度Easy

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?

 

首先要将Pascal‘s Triangle 和Pascal‘s Triangle II两道题目一起来看，两者都是对Pascal‘s Triangle的处理；

但是两道题目给定的参数意义是有很大区别的，Pascal‘s Triangle是给定numRows（即总的行数）；Pascal‘s Triangle II给出的是rowIndex（行的索引，即第几行），因为Pascal‘s Triangle的行下标是从0开始的，所以两道题目的初始化是需要特别注意的区分的。尤其是关于0的处理；

因为Pascal‘s Triangle是层层嵌套的，下一层的元素是由上一层的元素求得，但是此题目又对空间做了要求，所以在循环调用的过程中每求得一行都要对前一行的空间进行clear，这样才能保证空间复杂度是O(k）。

java代码：

public class Solution {    public List<Integer> getRow(int rowIndex) {        List<Integer> list = new ArrayList<Integer>();        List<Integer> list2 = new ArrayList<Integer>();        if(rowIndex<0) return list;        for(int i=0;i<=rowIndex;i++){            if(i==0) {                list2.add(1);            }else             for(int j=0;j<=i;j++){                if(j==0 || j==i){                    list2.add(1);                }                else{                    list2.add(list.get(j-1)+list.get(j));                }            }            List<Integer> temp = list;            list=list2;            list2=temp;            list2.clear();        }        return list;    }}

 

leetcode----------Pascal's Triangle II


联系
我们