Skip to content

Commit f5fe546

Browse files
fishercoder1534fishercoder1534
committed
add 1377
1 parent 0affc39 commit f5fe546

File tree

3 files changed

+170
-0
lines changed

3 files changed

+170
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ ★
88

99
| # | Title | Solutions | Video | Difficulty | Tag
1010
|-----|----------------|---------------|--------|-------------|-------------
11+
|1377|[Frog Position After T Seconds](https://leetcode.com/problems/frog-position-after-t-seconds/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1377.java) | |Hard|DFS|
1112
|1376|[Time Needed to Inform All Employees](https://leetcode.com/problems/time-needed-to-inform-all-employees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1376.java) | |Medium|DFS|
1213
|1375|[Bulb Switcher III](https://leetcode.com/problems/bulb-switcher-iii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1375.java) | |Medium|Array|
1314
|1374|[Generate a String With Characters That Have Odd Counts](https://leetcode.com/problems/generate-a-string-with-characters-that-have-odd-counts/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1374.java) | |Easy|String|

‎src/main/java/com/fishercoder/solutions/_1377.java

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.HashMap;
5+
import java.util.LinkedList;
6+
import java.util.List;
7+
import java.util.Map;
8+
import java.util.Queue;
9+
10+
/**
11+
* 1377. Frog Position After T Seconds
12+
*
13+
* Given an undirected tree consisting of n vertices numbered from 1 to n.
14+
* A frog starts jumping from the vertex 1.
15+
* In one second, the frog jumps from its current vertex to another unvisited vertex if they are directly connected.
16+
* The frog can not jump back to a visited vertex.
17+
* In case the frog can jump to several vertices it jumps randomly to one of them with the same probability,
18+
* otherwise, when the frog can not jump to any unvisited vertex it jumps forever on the same vertex.
19+
* The edges of the undirected tree are given in the array edges, where edges[i] = [fromi, toi] means that exists an edge connecting directly the vertices fromi and toi.
20+
* Return the probability that after t seconds the frog is on the vertex target.
21+
*
22+
* Example 1:
23+
* Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
24+
* Output: 0.16666666666666666
25+
* Explanation: The figure above shows the given graph.
26+
* The frog starts at vertex 1, jumping with 1/3 probability to the vertex 2 after second 1 and
27+
* then jumping with 1/2 probability to vertex 4 after second 2.
28+
* Thus the probability for the frog is on the vertex 4 after 2 seconds is 1/3 * 1/2 = 1/6 = 0.16666666666666666.
29+
*
30+
* Example 2:
31+
* Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
32+
* Output: 0.3333333333333333
33+
* Explanation: The figure above shows the given graph. The frog starts at vertex 1, jumping with 1/3 = 0.3333333333333333 probability to the vertex 7 after second 1.
34+
*
35+
* Example 3:
36+
* Input: n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 20, target = 6
37+
* Output: 0.16666666666666666
38+
*
39+
* Constraints:
40+
* 1 <= n <= 100
41+
* edges.length == n-1
42+
* edges[i].length == 2
43+
* 1 <= edges[i][0], edges[i][1] <= n
44+
* 1 <= t <= 50
45+
* 1 <= target <= n
46+
* Answers within 10^-5 of the actual value will be accepted as correct.
47+
* */
48+
public class _1377 {
49+
public static class Solution1 {
50+
public double frogPosition(int n, int[][] edges, int t, int target) {
51+
List<Integer>[] graph = new ArrayList[n];
52+
for (int i = 0; i < n; i++) {
53+
graph[i] = new ArrayList<>();
54+
}
55+
for (int[] edge : edges) {
56+
graph[edge[0] - 1].add(edge[1] - 1);
57+
graph[edge[1] - 1].add(edge[0] - 1);
58+
}
59+
boolean[] visited = new boolean[n];
60+
visited[0] = true;
61+
double[] probabilities = new double[n];
62+
probabilities[0] = 1f;
63+
Queue<Integer> queue = new LinkedList<>();
64+
queue.offer(0);
65+
while (!queue.isEmpty() && t-- > 0) {
66+
for (int i = queue.size(); i > 0; i--) {
67+
int vertex = queue.poll();
68+
int nextVerticesCount = 0;
69+
for (int v : graph[vertex]) {
70+
if (!visited[v]) {
71+
nextVerticesCount++;
72+
}
73+
}
74+
for (int v : graph[vertex]) {
75+
if (!visited[v]) {
76+
visited[v] = true;
77+
queue.offer(v);
78+
probabilities[v] = probabilities[vertex] / nextVerticesCount;
79+
}
80+
}
81+
if (nextVerticesCount > 0) {
82+
probabilities[vertex] = 0;
83+
}
84+
}
85+
}
86+
return probabilities[target - 1];
87+
}
88+
}
89+
}

‎src/test/java/com/fishercoder/_1377Test.java

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1377;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _1377Test {
10+
private static _1377.Solution1 solution1;
11+
private static int[][] edges;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _1377.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
edges = new int[][]{
21+
{1, 2},
22+
{1, 3},
23+
{1, 7},
24+
{2, 4},
25+
{2, 6},
26+
{3, 5},
27+
};
28+
assertEquals(0.16666666666666666, solution1.frogPosition(7, edges, 2, 4), 0);
29+
}
30+
31+
@Test
32+
public void test2() {
33+
edges = new int[][]{
34+
{1, 2},
35+
{1, 3},
36+
{1, 7},
37+
{2, 4},
38+
{2, 6},
39+
{3, 5},
40+
};
41+
assertEquals(0.3333333333333333, solution1.frogPosition(7, edges, 1, 7), 0);
42+
}
43+
44+
@Test
45+
public void test3() {
46+
edges = new int[][]{
47+
{1, 2},
48+
{1, 3},
49+
{1, 7},
50+
{2, 4},
51+
{2, 6},
52+
{3, 5},
53+
};
54+
assertEquals(0.16666666666666666, solution1.frogPosition(7, edges, 20, 6), 0);
55+
}
56+
57+
@Test
58+
public void test4() {
59+
edges = new int[][]{
60+
{2, 1},
61+
{3, 2},
62+
};
63+
assertEquals(1.0, solution1.frogPosition(3, edges, 1, 2), 0);
64+
}
65+
66+
@Test
67+
public void test5() {
68+
edges = new int[][]{
69+
{2, 1},
70+
{3, 2},
71+
{4, 1},
72+
{5, 1},
73+
{6, 4},
74+
{7, 1},
75+
{8, 7},
76+
};
77+
assertEquals(0.0, solution1.frogPosition(8, edges, 7, 7), 0);
78+
}
79+
80+
}

0 commit comments

Comments
 (0)