I tried LeetCode every day 118. Pascal's Triangle (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)
28th question (problem 118)
- Pascal's Triangle
the issue's details
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.
(Japanese translation)
Given a non-negative integer * numRows *, generate the first * numRows * of Pascal's triangle.
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]
]
Way of thinking
-
Create an empty array and rotate for minutes by the number of numbers
-
In the loop, add [1] elements according to the number of appends.
-
Since the left end and the right end are 1, substitute the values with reference to the upper hierarchy in the range excluding it.
-
Use the finally created lists as the return value
Answer code
class Solution:
def generate(self, numRows):
lists = []
for i in range(numRows):
lists.append([1]*(i+1))
if i>1 :
for j in range(1,i):
lists[i][j]=lists[i-1][j-1]+lists[i-1][j]
return lists
--I'll write it in Go too!
func generate(numRows int) [][]int {
answer := make([][]int, numRows)
for i := 0; i < numRows; i += 1 {
a := make([]int, i+1)
// add ones
a[0], a[i] = 1, 1
if i > 1 {
for j := 1; j <= i/2; j += 1 {
a[j] = answer[i-1][j-1] + answer[i-1][j]
a[len(a)-1-j] = a[j]
}
}
answer[i] = a
}
return answer
}
Recommended Posts