|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
- Note that the row index starts from 0.
- In Pascal's triangle, each number is the sum of the two numbers directly above it.
- Example:
- Input: 3
- Output: [1,3,3,1]
- Follow up:
- Could you optimize your algorithm to use only O(k) extra space?
复制代码
- class Solution {
- public List<Integer> getRow(int rowIndex) {
-
- List <Integer> array = new ArrayList<>();
- array.add(1);
- if(rowIndex == 0) return array;
- List <List<Integer>> re = new ArrayList<>();
- re.add(array);
-
- for(int i = 1; i <= rowIndex; i++){
-
- List<Integer> pre = re.get(i-1);
- List<Integer> cur = new ArrayList<>();
- cur.add(1);
-
- for(int j = 1; j < i ; j++){
-
- cur.add(pre.get(j) + pre.get(j-1));
- }
-
- cur.add(1);
- re.add(cur);
- }
-
- return re.get(re.size()-1);
- }
- }
复制代码
optimized with constant space
- class Solution {
- public List<Integer> getRow(int rowIndex) {
-
- ArrayList <Integer> array = new ArrayList<>();
- array.add(1);
- if(rowIndex == 0) return array;
- ArrayList<Integer> cur = new ArrayList<>();;
-
- for(int i = 1; i <= rowIndex; i++){
- cur.clear();
- cur.add(1);
-
- for(int j = 1; j < i ; j++){
-
- cur.add(array.get(j) + array.get(j-1));
- }
-
- cur.add(1);
- array.clear();
- array = (ArrayList<Integer>) cur.clone();
- }
-
- return cur;
- }
- }
复制代码 |
|