Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 33 "1. Two Sum" starting from zero

Basically, I would like to solve the easy acceptance in descending order.

Twitter I'm doing it.

problem

118. Pascal's Triangle

I happened to see this problem solved in Java on YouTube, so I decided to try it too.

The difficulty level is Easy!

The problem is that we are given the natural number numRows, so make a Pascal's triangle like the one in the example.

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

Commentary

Since it is decided to insert 1 at the beginning and the end, it seems good to prepare a state where 1 is inserted in advance and append 1 again at the end of the process. The problem is how to calculate and insert the sum of the upper numbers, but it seems that you can get and add two elements by turning the for loop twice. This time, I wrote it so that if numRows is 0 and 1, it is excluded as an exception. By doing this, I think that it is easier to read because it is only necessary to write the processing from the third stage.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        elif numRows == 1:
            return [[1]]
        
        triangle = [[1]]
        
        for i in range(1,numRows):
            row = [1]
              
            for j in range(1,i):
                row.append(triangle[i-1][j-1] + triangle[i-1][j])
            
            row.append(1)
            triangle.append(row)
            
        return triangle
# Runtime: 28 ms, faster than 73.84% of Python3 online submissions for Pascal's Triangle.
# Memory Usage: 13.8 MB, less than 7.14% of Python3 online submissions for Pascal's Triangle.

Yes, it looks like this.

This way of writing is better! I wrote it in this language! If you have any questions, please feel free to comment.

[PYTHON] Let Code Day 34 starting from scratch "118. Pascal's Triangle"

Overview

problem

Commentary