首页 > 其他 > 详细

leetCode-Pascal's Triangle II

时间:2017-11-26 20:59:00      阅读:237      评论:0      收藏:0      [点我收藏+]

Description:
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?

My Solution:

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

Better Solution:

class Solution {
    public List<Integer> getRow(int rowIndex) {
        rowIndex+=1;
        int[][] res=new int[rowIndex][];
        List<Integer> RES=new ArrayList<>();
        for(int i=0;i<rowIndex;i++){
            res[i]=new int[i+1];
            for(int j=0;j<i+1;j++){
                if(j==0||j==i)res[i][j]=1;
                else res[i][j]=res[i-1][j-1]+res[i-1][j];
                if(i==rowIndex-1)RES.add(res[i][j]);
            }
        }
        return RES;
    }
}

Best Solution:

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result=new ArrayList<Integer>();
        for(int k=0,value=1;k<=rowIndex;k++){
            result.add(value);
            //核心
            value=(int)((long)value*(rowIndex-k)/(k+1));
        }
        return result;
    }
}

leetCode-Pascal's Triangle II

原文:http://www.cnblogs.com/kevincong/p/7900348.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!