1377. The position of the frog after T seconds
Difficulty Hard 57
You are given an undirected tree of n vertices numbered from 1 to n. The frog starts jumping from vertex 1. The rules are as follows:
- In one second, the frog jumps from the current vertex it is on to another unvisited vertex (if they are directly connected).
- A frog cannot jump back to a vertex it has already visited.
- If the frog can jump to several different vertices, then it has an equal chance of jumping to any one of them.
- If the frog cannot jump to any unvisited vertex, it will stay in place every time it jumps.
The edges of an undirected tree are described by an array edges, where edges[i] = [ai, bi] means that there is a direct connection between ai and bi An edge between two vertices.
Returns the probability that the frog will be on the target vertex target after t seconds. Results within 10-5 of the actual answer will be considered correct.
Example 1:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4 Output: 0.16666666666666666 Explanation: The diagram above shows the jumping path of a frog. The frog jumps from vertex 1, there is a 1/3 probability of jumping to vertex 2 in the first second, and then there is a 1/2 probability of jumping to vertex 4 in the second second, so the probability that the frog is at vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.
Example 2:
Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7 Output: 0.3333333333333333 Explanation: The diagram above shows the jumping path of a frog. The frog jumps from vertex 1, and there is a probability of 1/3 = 0.3333333333333333 that it can jump to vertex 7 after 1 second.
Tip:
1 <= n <= 100edges. length == n - 1edges[i].length == 21 <= ai, bi <= n1 <= t <= 501 <= target <= n
BFS simulation
BFS simulation, when traversing each node, first check whether the adjacent nodes of the current node have been visited, if they have been visited, it means that they can’t move, stay in place, and add the node to the queue, otherwise Add unvisited nodes to the queue. Loop t times in total, and finally find the element whose value = target in the queue
class Solution {<!-- -->
public double frogPosition(int n, int[][] edges, int t, int target) {<!-- -->
if(n == 1 & amp; & amp; t == target) return 1.0;
if(n == 1 & amp; & amp; t != target) return 0.0;
List<Integer>[] g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for(int[] e : edges){<!-- -->
int x = e[0]-1, y = e[1]-1;
g[x].add(y);
g[y].add(x);
}
target--;
Deque<Pair<Integer, Double>> dq = new ArrayDeque<>();
boolean[] vis = new boolean[n];
dq.addLast(new Pair<>(0, 1.0));
vis[0] = true;
int step = 0;
while(!dq.isEmpty()){<!-- -->
int size = dq. size();
while(size-- > 0){<!-- -->
Pair<Integer, Double> p = dq.pollFirst();
int s = g[p.getKey()].size();
for(int y : g[p.getKey()]){<!-- -->
if(vis[y])
s -= 1;
}
if(s == 0) dq. addLast(p);
else{<!-- -->
for(int y : g[p.getKey()]){<!-- -->
if(!vis[y]){<!-- -->
vis[y] = true;
dq.addLast(new Pair<>(y, p.getValue() * (1.0 / s)));
}
}
}
}
step + = 1;
if(step == t) break;
}
while(!dq.isEmpty()){<!-- -->
Pair<Integer, Double> p = dq.pollFirst();
if(p.getKey() == target){<!-- -->
return p. getValue();
}
}
return 0.0;
}
}
DFS recursion (top-down + bottom-up)
https://leetcode.cn/problems/frog-position-after-t-seconds/solution/dfs-ji-yi-ci-you-qu-de-hack-by-endlessch-jtsr/
Since the answer is obtained by multiplying several fractions with a numerator of 1, simply multiply the denominators, and finally calculate the reciprocal, which can avoid the loss of precision caused by floating-point multiplication. In addition, integers are usually more computationally efficient than floating-point numbers.
- Top-down is one side [pass], while multiplying the number of sons c, if the target can be reached in the tth second, or the target is reached in less than t seconds and the target is a leaf node (at this time, every jump will stop in place), then record the answer as the reciprocal of the product and return a boolean indicating the end of the recursion
- **The bottom-up idea is similar. After finding the target, do multiplication in the process of [return]. **Personally, I prefer this way of writing, because the multiplication is only done after the target is found, and the top-down will blindly do the multiplication even if it searches in the subtree that does not contain the target
Tips:
You can add a No. 0 neighbor to node 1, so as to avoid judging that the current node is the root node 1, and also avoid the special judgment of n = 1
In addition, the time in DFS does not increase from 0 to t, but decreases to 0 from leftT = t, so that the code only needs to compare with 0 instead of t, thereby reducing the introduction of a variable outside of DFS.
Top to bottom: (hand)
class Solution:
def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
g = [[] for _ in range(n + 1)]
g[1] = [0] # Tips to reduce extra judgment
for x, y in edges:
g[x].append(y)
g[y].append(x) # build tree
ans = 0
def dfs(x: int, fa: int, left_t: int, prod: int) -> True:
# Must be at target after t seconds (just arrived, or target is the leaf stopped in place)
if x == target and (left_t == 0 or len(g[x]) == 1):
nonlocal ans
ans = 1 / prod
return True
if x == target or left_t == 0: return False
for y in g[x]: # traverse x's son y
if y != fa and dfs(y, x, left_t-1, prod * (len(g[x]) - 1)):
return True # Find the target and no longer recurse
return False # target not found
dfs(1, 0, t, 1)
return ans
Bottom-up: (return)
class Solution:
def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
g = [[] for _ in range(n + 1)]
g[1] = [0] # Tips to reduce extra judgment
for x, y in edges:
g[x].append(y)
g[y].append(x) # build tree
ans = 0
def dfs(x: int, fa: int, left_t: int) -> True:
# Must be at target after t seconds (just arrived, or target is the leaf stopped in place)
if left_t == 0:
return x == target
if x == target:
return len(g[x]) == 1
for y in g[x]: # traverse x's son y
if y != fa:
prod = dfs(y, x, left_t-1) # find target
if prod:
return prod * (len(g[x]) - 1) # multiply the number of sons and return directly
return 0 # target not found
prod = dfs(1, 0, t)
return 1 / prod if prod else 0