118. Yang Hui triangle | brush question and punch card

create by db on 2021-3-9 17:19:13

Recently revised in 2021-3-9 17:29:19

Idle time to have a tight mind, busy time to have leisure fun

118. Yang Hui’s Triangle

  • Topic describes
  • Thought analysis
  • AC code
  • conclusion

Topic describes

Returns the directory

Given a non-negative integer numRows, generate the former numRows of the Yanghui triangle.

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

Example:

Input:5Output: [[1], [1.1], [1.2.1], [1.3.3.1], [1.4.6.4.1]]
Copy the code

Thought analysis

Idea 1: Dynamic programming (double-layer cycle)

In The Yang Hui triangle, each number is the sum of its upper left and upper right numbers. Therefore, for the two-dimensional array A storing The Yang Hui triangle, excluding the boundary case, the following relationship holds:

A[i][j] = A[i-1][j-1] + A[i-1][j];

So we can iterate with a double loop.

Idea 2: Recursion

To sum up, there are three points:

  1. Find the termination condition for the whole recursion
  2. Looking for a return value
  3. How does a recursion work

Find the termination condition for the whole recursion

We can terminate the recursion when numRows = 0 or when numRows = 1, because the first row is special and has only one 1, so we can use that as the termination condition for the whole recursion, and when numRows = 1, we can terminate the recursion and return the value down.

Looking for a return value

To find the return value, we also need to analyze, the question requires all the numbers of the whole Yang Hui triangle, so the final recursion should be List<List> (given by the question), that is, after each layer of recursion, we can update the List and return, and the final recursion is the answer we want.

How does a recursion work

Recursion is difficult here, many children boots just learn recursion, always confused here, in fact, we only need to pay attention to a recursion, because each layer of recursion process is the same, we just need to find the law of the recursion on the top, it is ok.

AC code

Solution 1: Double cycle

/ * * *@param {number} numRows
 * @return {number[][]}* /
var generate = function (numRows) {
  let result = []
  let rowArr = []
  if (numRows <= 0) {
    return result
  }
  for (let i = 0; i < numRows; i++) {
    rowArr = []
    for (let j = 0; j <= i; j++) {
      if (j > 0 && j < i) {
        rowArr.push(result[i - 1][j - 1] + result[i - 1][j])
      } else {
        rowArr.push(1)
      }
    }
    result.push(rowArr)
  }
  return result
}
Copy the code

Solution 2: Recursion

/ * * *@param {number} numRows
 * @return {number[][]}* /
var generate = function (numRows) {
  // Store the Yang Hui triangle to return
  let dg = []
  // If 0 rows, return null
  if (numRows === 0) return dg
  // Recursive exit, if 1 row, returns
  if (numRows === 1) {
    dg = [[1]]
    return dg
  }
  // recursive, note the return value!! That's step two
  dg = generate(numRows - 1)
  // We can see what lines 2 through 3 need to do for first level recursion
  // Get a list to store the third row, and then get the third row from the second row
  // The third line starts and ends with 1, and then the middle number is obtained
  // It is easy to get the formula inside the for loop by observing it
  // Don't forget the return value!!
  let prev = dg[numRows - 2]
  let row = [1]
  for (let j = 1; j < numRows - 1; j++) {
    row.push(prev[j - 1] + prev[j])
  }
  row.push(1)
  dg.push(row)
  return dg
}
Copy the code

Attached is another recursion of the big guy

  • Author: huang shan — he
/ * * *@param {number} numRows
 * @return {number[][]}* /
const generate = function(numRows) {
  if (numRows === 0) return []
  if (numRows === 1) return [[1]]

  const ans = generate(numRows - 1)
  const prev = ans[ans.length - 1]
  const item = []
  for (let i = 0; i < prev.length + 1; i++) {
    item[i] = (prev[i - 1] | |0) + (prev[i] || 0)}return ans.concat([item])
}

Copy the code

conclusion

Returns the directory

March hello, spring flowers. Come on!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign

Postscript: Hello friends, if you think this article is good, remember to give a thumbs-up or star, your thumbs-up and star is my motivation to write more and richer articles!Making the address

Document agreement



dbThe document library 由 dbusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on thegithub.com/danygitgitOn the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.