Question
Child A is playing a message game with his friends. The rules of the game are as follows:
- There are
nplayers, all players are numbered0 ~ n-1, and the number of childAis0 - 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,
Acan send information toB, butBcannot send information toA). - 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 = 3output:
3Explanation: 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 = 2output:
0Explanation: Information cannot be passed from small A to number 2 in 2 rounds
limit:
2 <= n <= 101 <= k <= 51 <= relation.length <= 90, and relation[i].length == 20 <= 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];
};
More algorithm solutions, leetcode study notes, classic algorithm explanations ,check : https://lwebapp.com/en/tag/leetcode
Top comments (0)