LeetCode Notes: Send message

#leetcode

Question

Child A is playing a message game with his friends. The rules of the game are as follows:

  1. There are n players, all players are numbered 0 ~ n-1, and the number of child A is 0
  2. Each player has a fixed number of other players (or may not) who can transmit information. The relationship of sending information is one-way (for example, A can send information to B, but B cannot send information to A).
  3. Each round of information must be passed to another person, and the information can pass through the same person repeatedly

Given a total number of players n, and a two-dimensional array relation formed by the relationship [player number, corresponding to passable player number]. Returns the number of solutions passed from A (number 0) to the partner number n-1 through k rounds; if it cannot be reached, it returns 0.

Example 1:

Input: n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0, 4]], k = 3

output: 3

Explanation: The information starts at the number 0 of the small A, passes through 3 rounds, and reaches the number 4. There are 3 schemes, 0->2->0->4, 0->2->1->4, 0->2->3->4.

Example 2:

Input: n = 3, relation = [[0,2],[2,1]], k = 2

output: 0

Explanation: Information cannot be passed from small A to number 2 in 2 rounds

limit:

  • 2 <= n <= 10
  • 1 <= k <= 5
  • 1 <= relation.length <= 90, and relation[i].length == 2
  • 0 <= relation[i][0], relation[i][1] < n and relation[i][0] != relation[i][1]

Solution One

Analysis:

Depth-First Search (DFS), starting from position 0 to search for the next position recursively, each time the specified number of steps is found recursively to stop, when stopping, it is judged whether the target position meets the requirements, and if the requirements are met, the count is incremented by 1.

Code:

/**
 * DFS
 * @param {number} n
 * @param {number[][]} relation
 * @param {number} k
 * @return {number}
 */
var numWays = function (n, relation, k) {
  // count the number of paths
  let ways = 0;
  const list = new Array(n).fill(0).map(() => new Array());

  // Collect multiple transfer positions corresponding to a start position, so that it is convenient to traverse the transfer positions together
  for (const [from, to] of relation) {
    list[from].push(to);
  }

  const dfs = (index, step) => {
    // When the number of steps reaches the specified k steps, it is passed to the n-1 position to meet the requirements
    if (step === k) {
      if (index === n - 1) {
        ways++;
      }
      // No matter whether the requirements are met or not, you can stop after taking k steps
      return;
    }
    // recursively traverse all paths in the list
    const targetList = list[index];
    for (const nextIndex of targetList) {
      dfs(nextIndex, step + 1);
    }
  };

  // The first step is fixed from 1
  dfs(0, 0);
  return ways;
};

Solution Two

Analysis:

Breadth-First Search (BFS), construct a one-dimensional array, store all the results of the traversal to the k step in this array, and finally count how many results meet the requirements.

Code:

/**
   BFS
 * @param {number} n
 * @param {number[][]} relation
 * @param {number} k
 * @return {number}
 */
var numWays = function (n, relation, k) {
  const list = new Array(n).fill(0).map(() => new Array());

  // Collect multiple transfer positions corresponding to a start position, so that it is convenient to traverse the transfer positions together
  for (const [from, to] of relation) {
    list[from].push(to);
  }

  // pedometer
  let step = 0;
  // start at starting position 0
  let queue = [0];
  // 1. There is no next target, no need to traverse
  // 2. No need to traverse when the number of steps reaches k
  while (queue.length && step < k) {
    step++;
    // Get each position of the current queue, and all the corresponding next positions are also stored in the queue, and delete each current position at the same time, because it has already passed, here is the difference between BFS and DFS
    const length = queue.length;
    for (let i = 0; i < length; i++) {
      let index = queue.shift();
      let targetList = list[index];
      for (const nextIndex of targetList) {
        queue.push(nextIndex);
      }
    }
  }

  // count the number of paths
  let ways = 0;
  if (step === k) {
    while (queue.length) {
      if (queue.shift() === n - 1) {
        ways++;
      }
    }
  }
  return ways;
};

Solution Three

Analysis:

Dynamic programming (DP), construct a (k + 1) * n two-dimensional array, store the counts of all the results of the traversal to the k step in this array, the count of the positions of n - 1 when looking at the last k steps is the number of solutions.

for example

var n = 5,
  relation = [
    [0, 2],
    [2, 1],
    [3, 4],
    [2, 3],
    [1, 4],
    [2, 0],
    [0, 4],
  ],
  k = 3;

Constructs an array of 4 * 5, starting at step 0, arr[0][0] counts as 1

0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 0, 0, 0]
2: (5) [0, 0, 0, 0, 0]
3: (5) [0, 0, 0, 0, 0]

first round

0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 1, 0, 1]
2: (5) [0, 0, 0, 0, 0]
3: (5) [0, 0, 0, 0, 0]

second round

0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 1, 0, 1]
2: (5) [1, 1, 0, 1, 0]
3: (5) [0, 0, 0, 0, 0]

third round

0: (5) [1, 0, 0, 0, 0]
1: (5) [0, 0, 1, 0, 1]
2: (5) [1, 1, 0, 1, 0]
3: (5) [0, 0, 1, 0, 3]

At the end of the third round, the number of solutions that reached n - 1 was 3

Code:

/**
 * @param {number} n
 * @param {number[][]} relation
 * @param {number} k
 * @return {number}
 */
var numWays = function (n, relation, k) {
  const dp = new Array(k + 1).fill(0).map(() => new Array(n).fill(0));
  dp[0][0] = 1;
  for (let i = 0; i < k; i++) {
    for (const [src, dst] of relation) {
      dp[i + 1][dst] += dp[i][src];
    }
  }
  return dp[k][n - 1];
};

Reference

Comments