LeetCode - Easy - 118. Pascal‘s Triangle

朴灿烈づ我的快乐病毒、 2022-12-28 11:16 216阅读 0赞

## Topic ##

*  Array

## Description ##

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

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

![8c3da7a30a5796e97de5bd9cbc677776.png][]

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

**Example**:

Input: 5
    Output:
    [
         [1],
        [1,1],
       [1,2,1],
      [1,3,3,1],
     [1,4,6,4,1]
    ]

## Analysis ##

方法一：我写的

方法二：别人写的

## Submission ##

import java.util.ArrayList;
    import java.util.List;
    
    public class PascalsTriangle { 
    
    	//方法一：我写的
    	public List<List<Integer>> generate1(int numRows) { 
    		List<List<Integer>> result = new ArrayList<>();
    		if (numRows <= 0)
    			return result;
    
    		for (int i = 1; i <= numRows; i++) { 
    			List<Integer> tempList = new ArrayList<>();
    
    			for (int j = 0; j < i; j++) { 
    				if (j == 0 || j == i - 1) { 
    					tempList.add(1);
    					continue;
    				}
    
    				List<Integer> lastList = result.get(i - 2);
    				tempList.add(lastList.get(j) + lastList.get(j - 1));
    			}
    
    			result.add(tempList);
    		}
    
    		return result;
    	}
    
    	//方法二：别人写的
    	public List<List<Integer>> generate2(int numRows) { 
    		List<List<Integer>> allrows = new ArrayList<List<Integer>>();
    		ArrayList<Integer> row = new ArrayList<Integer>();
    		for (int i = 0; i < numRows; i++) { 
    			row.add(0, 1);
    			for (int j = 1; j < row.size() - 1; j++)
    				row.set(j, row.get(j) + row.get(j + 1));
    			allrows.add(new ArrayList<Integer>(row));
    		}
    		return allrows;
    
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import static org.hamcrest.CoreMatchers.*;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    import org.junit.Test;
    
    public class PascalsTriangleTest { 
    
    	@Test
    	public void test() { 
    		PascalsTriangle obj = new PascalsTriangle();
    
    		List<List<Integer>> expected = new ArrayList<List<Integer>>();
    		
    		expected.add(Arrays.asList(1));
    		expected.add(Arrays.asList(1,1));
    		expected.add(Arrays.asList(1,2,1));
    		expected.add(Arrays.asList(1,3,3,1));
    		expected.add(Arrays.asList(1,4,6,4,1));
    		
    		assertThat(obj.generate1(5), is(expected));
    		assertThat(obj.generate2(5), is(expected));
    		
    		
    	}
    }

[https_leetcode.com_problems_pascals-triangle]: https://leetcode.com/problems/pascals-triangle/
[8c3da7a30a5796e97de5bd9cbc677776.png]: /images/20221120/0c0f402e3727460d9b5e7acaae45248f.png