I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)

29th question (problem 119)

  1. Pascal's Triangle II

the issue's details

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

Notice that the row index starts from 0.

img 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?

Japanese translation

Returns a row of Pascal's triangles with an integer. rowIndexth

Note that the row index starts with ** 0 **.

**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]

Way of thinking

  1. Create an array and put 1 element for the number of rowIndex

  2. Turn the loop from 2 to rowIndex and then run the loop in the opposite direction to create the value.

  3. Use the finally created pascal as the return value

  4. ps The reason for going backwards in the second j-loop is that if you go forward, the i-th element is modified by the i-1th element. And it affects the calculation of the following factors:

Answer code

def getRow(rowIndex):
    pascal = [1]*(rowIndex + 1)
    for i in range(2,rowIndex+1):
        for j in range(i-1,0,-1):
            pascal[j] += pascal[j-1]
    return pascal

--I'll write it in Go too!

func getRow(rowIndex int) []int {
	ReArray := make([]int, rowIndex+1)
	ReArray[rowIndex], ReArray[0] = 0, 1
	for i := 0; i < rowIndex+1; i++ {
		for j := i; j >= 1; j-- {
			ReArray[j] += ReArray[j-1]
		}
	}
	return ReArray
}

Recommended Posts

I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried Grumpy (Go running Python).
I tried running faiss with python, Go, Rust
I tried Python> decorator
I tried fp-growth with python
I tried scraping with Python
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
I tried to touch Python (installation)
I tried web scraping with python.
I tried using Thonny (Python / IDE)
I tried running prolog with python 3.8.2.
I tried Line notification in Python
I tried SMTP communication with Python
[Python] I tried using YOLO v3
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried scraping Yahoo News with Python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I tried sending an email with python.
I tried using Bayesian Optimization in Python
I tried non-photorealistic rendering with Python + opencv
I tried using UnityCloudBuild API from Python
I tried to implement ADALINE in Python
I tried recursion with Python ② (Fibonacci sequence)
I tried to implement PPO in Python
Python: I tried the traveling salesman problem
Wrangle x Python book I tried it [1]
Mayungo's Python Learning Episode 8: I tried input
[Python] I tried to calculate TF-IDF steadily
I tried scraping Yahoo weather (Python edition)
I tried to touch Python (basic syntax)
I tried the Python Tornado Testing Framework
#I tried something like Vlookup with Python # 2
[LIVE] I tried to deliver the sunrise and sunset times nationwide every day
[Baseball Hack] I tried copying the Python MLB score & grade data acquisition script with Go in half a day