2014年4月24日 星期四

[LeetCode] Pascal's Triangle II

Problem:
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?
Solution1:O(n^2)
public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        int []ret = new int[rowIndex+1];
        ret[0]=1;
        if(rowIndex==0) 
            return getList(ret);
        for(int j=1;j<rowIndex+1;j++){
            for(int i=j-1;i>0;i--){
                ret[i]=ret[i]+ret[i-1];
            }
            ret[j]=1;
        }
        return getList(ret);
    }
    
    public ArrayList<Integer> getList(int[] nums){
        ArrayList<Integer> ret = new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            ret.add(nums[i]);
        }
        return ret;
    }
}
Solution2:O(n^2) without space

public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0; i<=rowIndex;i++){
            list.add(getNum(rowIndex,i));
        }
        return list;
    }
    public int getcommon(int x, int y){
        if( y == 0)
            return x;
            
        return getcommon(y,x%y);
    }
    public int getNum(int m, int n){
        int ret = 1;
        int min = Math.min(n,m-n);    
        for(int i=1; i<=min;i++){
            int com = getcommon(m-i+1,i);
            int a = (m-i+1)/com;
            int b = (i)/com;
            
            if(ret %b == 0){
               ret/=b;
               ret *= a;
            }else{
                ret *= a;
                ret/=b;
            }
        }    
        return ret;
    }
}

沒有留言:

張貼留言