Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

describe

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

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

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]
Copy the code

Example 2:

Input: rowIndex = 0
Output: [1]
Copy the code

Example 3:

Input: rowIndex = 1
Output: [1,1]
Copy the code

Note:

0 <= rowIndex <= 33
Copy the code

parsing

An integer rowIndex is given and we are required to return the contents of the rowIndex row in Yang Hui’s triangle. Pascal’s Triangle (118) is the same as Pascal’s Triangle (118). It is the same as Pascal’s Triangle (118). It is the same as Pascal’s Triangle (118).

The simplest way is to calculate all the contents of the front rowIndex line of Yang Hui triangle according to question 118, and finally only return the contents of the first rowIndex line. But it is clearly too slow.

answer

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex == 0: return [1]
        if rowIndex == 1: return [1,1]
        result = [[0],[1,1]]
        for i in range(2, rowIndex+1):
            tmp = [1]
            for j in range(1, i):
                tmp.append(result[-1][j-1]+result[-1][j])
            tmp.append(1)
            result.append(tmp)
        return result[-1]
        
        	      
		
Copy the code

The results

Given in the Python online submission to Pascal's Triangle II. Memory Usage: 10 ms 13.1 MB, less than 99.32% of Python online submissions for Pascal's Triangle II.Copy the code

parsing

The addition of all rows of Yang Hui triangles can be performed directly in a list, which can improve the operation efficiency.

answer

class Solution(object): def getRow(self, rowIndex): """ :type rowIndex: int :rtype: List[int] """ result = [1]*(rowIndex +1) for I in range(2,rowIndex+1): for j in range(i-1,0,-1): result[j] += result[j-1] return resultCopy the code

The results

Given in the Python online submissions for Pascal's Triangle II. Memory Usage: 13 MB, less than 39.40% of Python online submissions for Pascal's Triangle IICopy the code

Related topics

  • 118. Pascal’s Triangle

Original link: leetcode.com/problems/pa…

Your support is my biggest motivation