杨辉三角（二）

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
示例:
输入: 3
输出: [1,3,3,1]
进阶：
你可以优化你的算法到 O(k) 空间复杂度吗？

第一次提交
注意
List<List> tan = new ArrayList<List>();
tan.add(new ArrayList());
List newrow = new ArrayList();

class Solution {public List<Integer> getRow(int rowIndex) {List<List<Integer>> tan = new ArrayList<List<Integer>>();//0 rowtan.add(new ArrayList<Integer>());tan.get(0).add(1);for(int i = 1 ; i < 34 ; i++){List<Integer> newrow = new ArrayList<Integer>();List<Integer> prerow = tan.get(i-1);newrow.add(1);for(int j = 1;j<i;j++){newrow.add(prerow.get(j-1)+prerow.get(j));}newrow.add(1);tan.add(newrow);}return tan.get(rowIndex);}
}

很明显，复杂度是O(n^2),因为整个新建了一个33行的List，最笨的方法。不过杨辉三角的默写算是达标了。

评论区的：

public List<Integer> getRow(int rowIndex) {List<Integer> resultList = new ArrayList<Integer>();int middle = (rowIndex + 1)/2;boolean needY = (rowIndex%2 == 0);if(rowIndex == 0){resultList.add(1);return resultList;}int i = 0;for(; i < middle; i++){int yI= getYI(rowIndex,i,resultList);resultList.add(i,yI);resultList.add(i+1,yI);}if(needY){resultList.add(i,getYI(rowIndex,i,resultList));}return resultList;}public int getYI(int rowIndex,int i,List<Integer> list){if(i == 0){return 1;}else{double a = (double)list.get(i) * (double)(rowIndex - i + 1);double b = a / i;return (int) (b);}}

c++

vector<int> getRow(int rowIndex) {vector<int> result(rowIndex+1);result[0] = 1;for(int i = 1; i != rowIndex + 1; i++){result[i] = 1;for(int j = i-1; j != 0; j--){                result[j] += result[j-1];}}//forreturn result;
}

还有

public List<Integer> getRow(int rowIndex) {List<Integer> result = new LinkedList<>();int num = 1;for(int i = 0 ; i <= rowIndex; i++){result.add(num);num = num * (rowIndex-i) / (i + 1);}return result;}

66%的

class Solution {public List<Integer> getRow(int rowIndex) {List<Integer> row1=new ArrayList<Integer>();row1.add(1);if (rowIndex==0) {return row1;}for (int i = 1; i <=rowIndex; i++) {Iterator<Integer> it=row1.iterator();int a=0;List<Integer> row2=new ArrayList<Integer>();while (it.hasNext()) {int b=it.next();row2.add(a+b);a=b;}row2.add(1);row1=row2;}return row1;}
}

67.9%

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