k =3
return [1,3,3,1]
[
[1],
[1,1],
[1,2,1],
[1,3,3,1] <= k=3
]
2. Implementation
only O(k) extra space since if use Pascal's Triangle I's method, space:O(n)
cannot have a new List<Integer> for every row, so keep overwriting the existing one
List<Integer> would only keep current list element so for k =3 only keep 4 elements
// NOTE: 3(idx=2) = 2(idx=1) + 1(idx=2)
// NOTE: snippet
for (i = pre.size() -1 ; i > 0; i--) {
pre.set( i ,pre.get(i) + pre.get(i-1) );
}
pre.add(1);
// time :O(n^2), Space:O(k) public Listgenerate(int k) { List pre = new ArrayList (); // validate the input // NOTE: first row refers to k = 0 if ( k < 0 ) { return pre; } pre.add(1); for(int i = 1 ; i <= k;k++) { // NOTE: forward iterating would race //for (int i = 0 ; i < pre.size() ; i ++ ) // NOTE: 3(idx=2) = 1(idx=2) + 2(idx=1) for (i = pre.size() -1 ; i > 0; i--) { pre.set( i ,pre.get(i) + pre.get(i-1) ); } pre.add(1); } return pre; }
// NOTE: 3(idx=2) = 2(idx=1) + 1(idx=2) for ( i = pre.size()-2; i >=0 ;i--) { pre.set(i+1, pre.get(i) + pre.get(i+1) ); }3. Similar Ones:
Pascal's Triangle I
No comments:
Post a Comment