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)
- Pascal's Triangle II
the issue's details
Given an integer
rowIndex, return therowIndexthrow of the Pascal's triangle.Notice that the row index starts from 0.
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.
rowIndexthNote 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
-
Create an array and put 1 element for the number of rowIndex
-
Turn the loop from 2 to rowIndex and then run the loop in the opposite direction to create the value.
-
Use the finally created pascal as the return value
-
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