LeetCode - Easy - 119. Pascal‘s Triangle II

女爷i 2022-12-28 11:25 113阅读 0赞

## Topic ##

*  Array

## Description ##

[https://leetcode.com/problems/pascals-triangle-ii/][https_leetcode.com_problems_pascals-triangle-ii]

Given an integer rowIndex, return the rowIndexth row of the Pascal’s triangle.

Notice that the row index starts from 0.

![8c3da7a30a5796e97de5bd9cbc677776.png][]

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

**Follow up**:

Could you optimize your algorithm to use only O(k) extra space?

**Example 1**:

Input: rowIndex = 3
    Output: [1,3,3,1]

**Example 2**:

Input: rowIndex = 0
    Output: [1]

**Example 3**:

Input: rowIndex = 1
    Output: [1,1]

**Constraints**:

*  0 <= rowIndex <= 33

## Analysis ##

略

## Submission ##

import java.util.LinkedList;
    import java.util.List;
    
    public class PascalsTriangleII { 
        public List<Integer> getRow(int rowIndex) { 
        	List<Integer> result = new LinkedList<Integer>();
        	if(rowIndex < 0) return result;
        	
        	for(int i = 0; i <= rowIndex; i++) { 
        		result.add(0, 1);
        		for(int j = 1 ; j < result.size() - 1; j++) 
        			result.set(j, result.get(j) + result.get(j + 1));
        	}
            return result;
        }
    }

## Test ##

import static org.junit.Assert.*;
    import static org.hamcrest.CoreMatchers.*;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    
    import org.junit.Test;
    
    public class PascalsTriangleIITest { 
    
    	@Test
    	public void test() { 
    		PascalsTriangleII obj = new PascalsTriangleII();
    
    		assertThat(obj.getRow(3), is(new ArrayList<>(Arrays.asList(1, 3, 3, 1))));
    		assertThat(obj.getRow(0), is(new ArrayList<>(Arrays.asList(1))));
    		assertThat(obj.getRow(1), is(new ArrayList<>(Arrays.asList(1, 1))));
    		assertThat(obj.getRow(4), is(new ArrayList<>(Arrays.asList(1, 4, 6, 4, 1))));
    	}
    }

[https_leetcode.com_problems_pascals-triangle-ii]: https://leetcode.com/problems/pascals-triangle-ii/
[8c3da7a30a5796e97de5bd9cbc677776.png]: /images/20221120/4422a7c5330844c48727a65c55e033ea.png