“This is the 27th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

What is “Yang Hui triangle”, presumably we are not strange ~~

In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.

Yang Hui’s Triangle (Yang Hui’s Triangle

Problem 1: Given a non-negative integer numRows, generate the former numRows of a “Yang Hui triangle”.

Example 1: input: numRows = 5 output: [[1], [1, 1], [1, 2, 1],,3,3,1 [1], [1,4,6,4,1]] example 2: input, output numRows = 1: [[1]]Copy the code

Their thinking

The idea is simple, grasp the characteristics of Yang Hui triangle: 1 element in line 0, 2 elements in line 1, 3 elements in line 2; In this case, the push

The relationship between the element in the next row and the element in the previous row is (starting with 0). For example, element 2 in row 2, column 1, is equal to 1+1 (the same column in the previous row plus the element in the previous column).

JavaScript implementation

/** * @param {number} numRows * @return {number[][]} */ var generate = function (numRows) { const res = []; /** let egg=[ [1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1] ] */ for (let i = 0; i < numRows; I++) {// look at the example array above, line 0 with 1 element, line 1 with 2 elements, and line 2 with 3 elements.... const row = new Array(i + 1).fill(1); For (let j = 1; for (let j = 1; j < row.length - 1; Row [j] = res[i-1][j] + res[i-1][j] + res[i-1][j-1]; } res.push(row); } return res; };Copy the code

Problem 2: Given a non-negative index rowIndex, return the rowIndex ** row of the “Yang Hui triangle”.

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]Copy the code

Their thinking

Clever recursion:

  • I represents the rowIndex, and layer I has I +1 elements
  • J represents the position of the element in the current hierarchy
  • f[i][j] = (f[i – 1][j – 1] || 0) + (f[i – 1][j] || 0)
/** * @param {number} rowIndex * @return {number[]} */ const getRow = function(rowIndex) {/** * const getRow = function(rowIndex) { f[i][j] = (f[i - 1][j - 1] || 0) + (f[i - 1][j] || 0) */ if (rowIndex === 0) { return [1]; } const arr = getRow(rowIndex - 1); return Array.from({length: rowIndex + 1}) .map((_, index) => (arr[index - 1] || 0) + (arr[index] || 0)); };Copy the code

OK, that’s it

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~~