Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/119.html
Given an integer rowIndex
, return the rowIndexth
(0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
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]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex)
extra space?
Algorithm
Except for the first and last numbers, the other numbers are the sum of the left and right values in the previous line. Then we only need two for loops.
Except for the first number being 1, the following numbers are the sum of the value of the previous loop plus the value of the previous position, and keep updating the value of each position. You can get the number in the nth row.
Code
-
public class Pascals_Triangle_II { public class Solution_noExtraSpace { public List<Integer> getRow(int rowIndex) { List<Integer> res = new ArrayList<>(); res.add(1); for (int i = 1; i <= rowIndex; ++i) { for (int j = i; j >= 1; --j) { res.set(j, res.get(j) + res.get(j - 1)); } } return res; } } public class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(); if (rowIndex < 0) { return row; } row.add(1); if (rowIndex == 0) { return row; } for (int i = 2; i <= rowIndex + 1; i++) { List<Integer> current = new ArrayList<>(row); for (int j = 1; j < i; j++) { if (j < row.size()) { int add = row.get(j) + row.get(j - 1); // j starts at 1, so j-1 guaranteed ok current.set(j, add); } else { // current.set(j, 1); current.add(1); // @note: the last one, just add, not set } } row = current; } return row; } } } ############ class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<>(); for (int i = 0; i < rowIndex + 1; ++i) { row.add(1); } for (int i = 2; i < rowIndex + 1; ++i) { for (int j = i - 1; j > 0; --j) { row.set(j, row.get(j) + row.get(j - 1)); } } return row; } }
-
// OJ: https://leetcode.com/problems/pascals-triangle-ii/ // Time: O(N^2) // Space: O(1) class Solution { public: vector<int> getRow(int rowIndex) { vector<int> ans(rowIndex + 1, 1); for (int i = 2; i <= rowIndex; ++i) { for (int j = i - 1; j > 0; --j) ans[j] += ans[j - 1]; } return ans; } };
-
class Solution: def getRow(self, rowIndex: int) -> List[int]: row = [1] * (rowIndex + 1) for i in range(2, rowIndex + 1): for j in range(i - 1, 0, -1): row[j] += row[j - 1] return row ############ class Solution(object): def getRow(self, rowIndex): """ :type rowIndex: int :rtype: List[int] """ fact = [1] * (rowIndex + 1) ans = [1] * (rowIndex + 1) for i in range(1, rowIndex + 1): fact[i] = fact[i - 1] * i for i in range(1, rowIndex): ans[i] = fact[-1] / (fact[i] * fact[rowIndex - i]) return ans
-
func getRow(rowIndex int) []int { row := make([]int, rowIndex+1) row[0] = 1 for i := 1; i <= rowIndex; i++ { for j := i; j > 0; j-- { row[j] += row[j-1] } } return row }
-
function getRow(rowIndex: number): number[] { let ans = new Array(rowIndex + 1).fill(1); for (let i = 2; i < rowIndex + 1; ++i) { for (let j = i - 1; j > 0; --j) { ans[j] += ans[j - 1]; } } return ans; }
-
impl Solution { pub fn get_row(row_index: i32) -> Vec<i32> { let n = (row_index + 1) as usize; let mut res = vec![1; n]; for i in 2..n { for j in (1..i).rev() { res[j] += res[j - 1]; } } res } }