current position:Home>leetcode 119. Pascal's Triangle II(python)

leetcode 119. Pascal's Triangle II(python)

2022-01-30 13:22:22 Wang Daya

Little knowledge , Great challenge ! This article is participating in “ A programmer must have a little knowledge ” Creative activities .

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 code 

Example 2:

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

Example 3:

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

Note:

0 <= rowIndex <= 33
 Copy code 

analysis

According to the meaning , Gives an integer rowIndex , Ask us to return to the... In the Yanghui triangle rowIndex The content of the line . This question and 118. Pascal's Triangle The investigation points are the same , It's all about investigating the basic principle of Yang Hui triangle , It's just 118 In the question, you should return to the front n All the content of the line , But this question only returns to the first rowIndex The content of the line , Be the same in essentials while differing in minor points , In fact, it is to find regular questions .

The easiest way is to imitate 118 The front of Yang Hui's triangle rowIndex All the contents of the line are calculated , Finally, only the... Is returned rowIndex The content of the line is enough . But it's obviously 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 code 

Running results

Runtime: 35 ms, faster than 10.55% of Python online submissions for Pascal's Triangle II.
Memory Usage: 13.1 MB, less than 99.32% of Python online submissions for Pascal's Triangle II.	
            
 Copy code 

analysis

You can add Yang Hui triangle of all rows directly on a list , This can improve the computational 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 result
            
 Copy code 

Running results

Runtime: 8 ms, faster than 99.57% of Python online submissions for Pascal's Triangle II.
Memory Usage: 13.5 MB, less than 39.40% of Python online submissions for Pascal's Triangle II.
 Copy code 

Related topics

Original link :leetcode.com/problems/pa…

Your support is my greatest motivation

copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201301322207790.html

Random recommended