Pascal's Triangle 2(leetcode java)

问题描述：

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?

问题分析：

第 rowIndex 行有 rowIndex + 1 个元素，给这 rowIndex + 1个元素赋初值 0，

row的第一个元素赋值为1，此时，row的内容为[1,0,0,0,......]

由第 j 行生成第j + 1行，初始为[1,0,0,0,......]，逆序将相邻两个元素相加后，赋值给后者
j == 0 时，生成的是 [1,1,0,0,......]
j == 1 时，生成的是 [1,2,1,0,......]
......
j == rowIndex - 1，生成最终结果

代码：

public List<Integer> getRow(int rowIndex) {List<Integer> row = new ArrayList<Integer>();if(rowIndex < 0) return row;// 第 rowIndex 行有 rowIndex + 1 个元素，给这 rowIndex + 1个元素赋初值 0for(int i = 0; i <= rowIndex; ++i){ row.add(0);}row.set(0, 1);//生成第rowIndex行数据，最小为第0行//由第 j 行逆序生成第j + 1行，初始为 1//j == 0 时，生成的是 1 1//j == 1 时，生成的是 1 2 1//......//j == rowIndex - 1，生成最终结果for(int j = 0; j < rowIndex; ++j){for(int k = rowIndex - 1; k > 0; --k){ //从最后一个元素开始，逆序计算row.set(k, row.get(k) + row.get(k - 1));}}row.set(rowIndex, 1); //给最后一位赋值1return row;}

 

转载于:https://www.cnblogs.com/mydesky2012/p/5163125.html

总结

以上是生活随笔为你收集整理的Pascal's Triangle 2(leetcode java)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。