Given an integer numRows, return the first numRows of Pascal’s triangle. In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]Example 2:
Input: numRows = 1
Output: [[1]]
Generate a Pascal Triangle using GoLang
First declare a 2-dimension array with N rows, then fill each row, both ends are 1 and the internal value is equal to the sum of both numbers on its shoulder (Dynamic Programming Algorithm).
1 2 3 4 5 6 7 8 9 10 11 | func generate(numRows int) [][]int { var res = make([][]int, numRows) for i := 0; i < numRows; i ++ { res[i] = make([]int, i + 1) res[i][0], res[i][i] = 1, 1 for j := 1; j < i; j ++ { res[i][j] = res[i - 1][j] + res[i - 1][j - 1] } } return res } |
func generate(numRows int) [][]int { var res = make([][]int, numRows) for i := 0; i < numRows; i ++ { res[i] = make([]int, i + 1) res[i][0], res[i][i] = 1, 1 for j := 1; j < i; j ++ { res[i][j] = res[i - 1][j] + res[i - 1][j - 1] } } return res }
Another GoLang Implementation that appends row by row (beware that we need to deepcopy each row):
1 2 3 4 5 6 7 8 9 10 11 12 13 | func generate(numRows int) [][]int { var res [][]int var cur []int cur = append(cur, 1) for i := 0; i < numRows; i ++ { res = append(res, append([]int(nil), cur...)) for j := i; j > 0; j -- { cur[j] += cur[j - 1] } cur = append(cur, 1) } return res } |
func generate(numRows int) [][]int { var res [][]int var cur []int cur = append(cur, 1) for i := 0; i < numRows; i ++ { res = append(res, append([]int(nil), cur...)) for j := i; j > 0; j -- { cur[j] += cur[j - 1] } cur = append(cur, 1) } return res }
Pascal Triangle Implementations:
- Teaching Kids Programming – Pascal Triangle Algorithms and Applications
- Coding Exercise – Pascal Triangle II – C++ and Python Solution
- How to Print Pascal Triangle in C++ (with Source Code)
- Compute the Nth Row of a Pascal's Triangle using Dynamic Programming Algorithm
- GoLang: Generate a Pascal Triangle
--EOF (The Ultimate Computing & Technology Blog) --
GD Star Rating
loading...
417 wordsloading...
Last Post: Teaching Kids Programming - Sum of Distinct Positive Factorial Numbers via Depth First Search Algorithm
Next Post: Teaching Kids Programming - Swap Characters to Equalize Strings