This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

89. Binary tree expansion to flatten-binary-tree-to-linked-list

The label

  • The list
  • Binary tree
  • medium

The title

Leetcode portal

Let’s just open leetCode.

The root of the binary tree is root. Expand it into a single linked list:

The expanded list should also use TreeNode, with the right child pointing to the next node in the list and the left child always null.

The expanded list should be traversed in the same order as the binary tree.

Example:

Input: root = [6],2,5,3,4 1, null, output: [1, null, 2, null, 3, null, 4, null, 5, null, 6] input: root = [] output: [] input: root = [0] output: [0]Copy the code

The basic idea

And the way we’re going to do this is actually a type of traversal of a binary tree.

See traversal of binary trees

Think about the smallest operation of the problem and break it down! For the first time focus

1 1 1 1 / \ / \ 2! 5 - > 2! 5 -> 2 / \ \ \ \ \ 3! 4! June 3! 6 3\4! 4\5\6Copy the code

This rule is very easy to find, so how to write the program?

We see that the smallest operation on a node is actually flattening a binary tree

  1. Left subtree becomes right subtree
  2. The original right subtree hangs at the end of the current right subtree

So how do you flatten a tree into a linked list

  1. We first need to level the left subtree and the right subtree to continue to level this node, so the first step is to level the left subtree and the right subtree of root. In other words, the wave recursive operation is in front. (Think of it as a post-order traversal frame)

  2. The current node performs the minimum operation:

    1. Left subtree becomes right subtree
    2. The original right subtree hangs at the end of the current right subtree

Writing implement

var flatten = function(root) {
  if (root === null) {
    return null
  }
  // Perform recursion to level all subtrees, and then perform operation on current node (level current node)
  flatten(root.left)
  flatten(root.right)
  // Now the left and right subtrees are flattened (much like the second figure in the legend)
  // Perform minimal operations
  let origin_left = root.left
  let origin_right = root.right

  1. The left subtree becomes the right subtree
  root.left = null
  root.right = origin_left

  // 2. The original right subtree hangs at the end of the current right subtree
  // Get the last leveled node as the last mount point
  let lastRightNode = root
  while(lastRightNode.right ! = =null) {
    lastRightNode = lastRightNode.right
  }
  lastRightNode.right = origin_right
};
Copy the code

90. Distinct subsequences (distinct-intermediate)

The label

  • recursive
  • DP
  • difficult

The title

Leetcode portal

Let’s just open leetCode.

Given a string s and a string t, count the number of occurrences of t in a subsequence of S.

A subsequence of strings is a new string formed by deleting some (or none) characters without interfering with the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not)

The question data ensures that the answers fit into the range of 32-bit signed integers.

Example 1:

Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways to get "rabbit" from S. Arrow symbols on (^) characters that selecting rabbbit ^ ^ ^ ^ ^ ^ rabbbit ^ ^ ^ ^ ^ ^ rabbbit ^ ^ ^ ^ ^ ^Copy the code

It’s just finding the number of solutions.

The basic idea

When you see this kind of problem, you think of dynamic programming, looking for recursive formulas, which is really looking for relationships.

If you are not familiar with the basic concepts of dynamic programming, move to DP Basics

Basic steps

Let’s look at it from these three perspectives

  1. Search for optimal substructure (state representation)
  2. Induction of state transition Equation (State calculation)
  3. Boundary initialization

The problem itself counts the number of occurrences of T in a subsequence of S.

So let’s simplify things, we can actually imagine that these two strings are a little bit shorter, and we create two Pointers I and j

  • State said: dp[i][j]saids[0~i)Subsequence of andt[0~j)The emergence ofThe number ofSubproblems. Let’s cut short s and t, respectively
For example, s = "babgbag", t = "bag" I j note that < I,j closed before open so we cut short s' = S [0~ I) = "babgba" t' = t[0~j) = "ba" which is actually the last digit let's get rid of it, So this simplifies the problem and the solution to the original problem is dp[S.length][T.length]Copy the code

The relationship between the subproblem and the original problem is, in fact, the inference of the state transition equation

  • State transition equation

    • Think easy first, ifs[i] ! == t[j], indicating that even if s is subtracted by one, it does not affect the original problemdp[i][j] = dp[i - 1][j]Similar to s = ‘abcxxxx’ t = ‘ABC’, you can cut the x after s without affecting the original result.
    • And then ifs[i] === t[j]So there are two cases,
      • One is theThe last digit is the necessary digit 则 dp[i - 1][j - 1]
      • I don't need the last one, I can just drop itBecause it’s already set updp[i - 1][j]
    • So the equation isdp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

  • The boundary conditions

    • We can do it atdp[i][j]An empty string is inserted in front of it to indicate that a blank can be selected. Select “” empty, (j = 0) thent = "",dp[i][0] = 1Each substring is a solution, because an empty string is a subsequence of any string
    • When I = 0, there can be no solution dp[0][j] = 0

The following code is clear

Writing implement

var numDistinct = function(s, t) {
  // index = 0; // index = 0
  let [m, n] = [s.length + 1, t.length + 1]
  if (m < n) {
    return 0
  }
  let dp = new Array(m).fill(0).map(
    item= > new Array(n).fill(0))for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // Empty string is a subset of empty string
      if (j === 0) {
        dp[i][j] = 1
      } else if (i === 0) {
        dp[i][j] = 0
      } else {
        if (s[i-1] === t[j-1]) {
          dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        } else {
          dp[i][j] = dp[i-1][j]
        }
      }
    }
  }
  return dp[m - 1][n - 1]};let s = "babgbag", t = "bag"
console.log(numDistinct(s, t));
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference

  • Juejin. Cn/post / 690975…