Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return
Return
[1,3,3,1]
.
Note:
Could you optimize your algorithm to use only O(k) extra space?
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;
}
}
沒有留言:
張貼留言