Pascal's Triangle II

Q:
Given an index k, return the k^th 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?

A:
-----------5th pass ------------比第四次又有精简----好无聊的感觉------

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new LinkedList<Integer>();
        for(int i =0;i <= rowIndex;i++){
            for(int j = 0;j < list.size()-1;j++)
                list.set(j, list.get(j) + list.get(j+1));
            list.add(0,1);
        }
        return list;
    }
}

---------4th pass ------------每次在原本的list上增加一个即可

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new LinkedList<Integer>();
        if(rowIndex < 0)
            return list;
        list.add(1);
        for(int i =0;i<rowIndex;i++){
            int lastSize = list.size();
            for(int j =0;j<lastSize-1;j++) // set one as the sum of its above two
                list.set(j,list.get(j)+list.get(j+1));
            list.add(0,1);
        }
        return list;
    }
}

-----------------1th pass ---------多次声明新的List----------------

public class Solution {
  
    public ArrayList<Integer> getRow(int rowIndex) {
         ArrayList<Integer> al = new  ArrayList<Integer>();
         if(rowIndex<0)
            return al;
        al.add(1);
        for(int i = 0;i< rowIndex; i++){
             ArrayList<Integer> newAl = new  ArrayList<Integer>();
             
             for(int j =0;j<al.size()-1;j++)
                newAl.add(al.get(j) + al.get(j+1));
             newAl.add(0,1);
             newAl.add(1);
            al = newAl;
        }
        return al;
    }
}

Mistakes:
1:  很恶心的是，这个行数，也是从0行开始算起。 哎，也算是自己的题意没有看清楚。
     注意，人家给的参数的名字 是rowIndex
2：应该是在每一次，要计算，填入最新行的时候， 先清除本行。
    而不是再上次用完之后，清除。（其实也没问题。但是，那样，返回的时候，就不方便了。）

----------------------------------2 nd Pass ---------------------
上面的空间，严格来讲，并不是O(k)的关系，因此，这次，声明了2个list

public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        ArrayList<Integer> lastAl = new ArrayList<Integer>();
        if(rowIndex <0)
            return al;

        al.add(1);// add 1 at beginning
        if(rowIndex == 0){
            return al;
        }
        al.add(1);// add 1 at beginning
        if(rowIndex == 1){
            return al;
        }
        lastAl.add(1); // so that we do not need to consider 1
        for(int i =2;i<=rowIndex;i++){
            ArrayList<Integer> tmp = lastAl;
            lastAl = al;
            al=tmp;
            // update al into a new value
            int nLast = lastAl.size();
            for(int j = 1;j<nLast-1;j++){
                al.set(j,lastAl.get(j-1)+lastAl.get(j));
            }
            al.add( lastAl.get(nLast-1)+lastAl.get(nLast-2)  );
            al.add(1);
        }
        return al;
    }
}

Error:
1:  当base = = 0 和1 的情况之后， 我们直接计算rowIndex>=2的情况的时候， 是基于==1的基础上的，，可是， al。add是在 if语句里的，造成了空的情况。
2： 我们的考量，是基于 last中的第一个，是1， 从而不用考虑的。
     但是，当直接从2 开始计算的时候,  要考虑到，当前的 应该是i+2个数字的。 但是，原本接下来的空间，只有 i 个， 因此，最后要加2个。 

public class Solution {

    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        ArrayList<Integer> lastAl = new ArrayList<Integer>();
        
        al.add(1);// add 1 at beginning
        if(rowIndex == 0)
            return al;
        lastAl.add(1);
        for(int i =1;i<=rowIndex;i++){
            ArrayList<Integer> tmp = lastAl;
            lastAl = al;
            al=tmp;
            // update al into a new value
            int nLast = lastAl.size();
            for(int j = 1;j<nLast-1;j++){
                al.set(j,lastAl.get(j-1)+lastAl.get(j));
            }
            if(nLast-2>=0) // except for the row [1 1]
                al.add( lastAl.get(nLast-1)+lastAl.get(nLast-2)  );
            al.add(1);
        }
        return al;
    }
}