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)
Given an integer
rowIndex
, return therowIndexth
row 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.
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]
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