2015年10月6日星期二

Leetcode 119 Pascal's Triangle II

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?
Solution 1: same idea as DP optimize the space. Note if iterate from end to start for each line will be easier as no need to record the pre element.
 public class Solution {  
   public List<Integer> getRow(int rowIndex) {  
     List<Integer> res=new ArrayList<>();  
     for (int i=0; i<=rowIndex; i++) {  
       res.add(1);  
       for (int j=i-1; j>0; j--) {  
         res.set(j,res.get(j)+res.get(j-1));  
       }  
     }  
     return res;  
   }  
 }  

没有评论:

发表评论