Skip to content

Commit 99879b4

Browse files
fishercoder1534fishercoder1534
committed
add 1230
1 parent 3411d5d commit 99879b4

File tree

3 files changed

+70
-1
lines changed
  • paginated_contents/algorithms/2nd_thousand
  • src

3 files changed

+70
-1
lines changed

‎paginated_contents/algorithms/2nd_thousand/README.md

+2-1
Original file line numberDiff line numberDiff line change
@@ -370,6 +370,7 @@
370370
| 1242 | [Web Crawler Multithreaded](https://leetcode.com/problems/web-crawler-multithreaded/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1242.java) | | Medium | Concurrency |
371371
| 1237 | [Find Positive Integer Solution for a Given Equation](https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1237.java) | | Easy ||
372372
| 1232 | [Check If It Is a Straight Line](https://leetcode.com/problems/check-if-it-is-a-straight-line/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1232.java) | [:tv:](https://www.youtube.com/watch?v=_tfiTQNZCbs) | Easy ||
373+
| 1230 | [Toss Strange Coins](https://leetcode.com/problems/toss-strange-coins/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1230.java) | | Medium |DP
373374
| 1228 | [Missing Number In Arithmetic Progression](https://leetcode.com/problems/missing-number-in-arithmetic-progression/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1228.java) | | Easy ||
374375
| 1221 | [Split a String in Balanced Strings](https://leetcode.com/problems/split-a-string-in-balanced-strings/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1221.java) | | Easy | Greedy |
375376
| 1219 | [Path with Maximum Gold](https://leetcode.com/problems/path-with-maximum-gold/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1219.java) | | Medium | Backtracking |
@@ -414,7 +415,7 @@
414415
| 1114 | [Print in Order](https://leetcode.com/problems/print-in-order/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1114.java) | | Easy ||
415416
| 1110 | [Delete Nodes And Return Forest](https://leetcode.com/problems/delete-nodes-and-return-forest/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1110.java) | | Medium | Tree, DFS, BFS |
416417
| 1108 | [Defanging an IP Address](https://leetcode.com/problems/defanging-an-ip-address/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1108.java) | [:tv:](https://www.youtube.com/watch?v=FP0Na-pL0qk) | Easy ||
417-
| 1105 | [Filling Bookcase Shelves](https://leetcode.com/problems/filling-bookcase-shelves/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1105.java) || Medium |DP
418+
| 1105 | [Filling Bookcase Shelves](https://leetcode.com/problems/filling-bookcase-shelves/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1105.java) || Medium | DP
418419
| 1104 | [Path In Zigzag Labelled Binary Tree](https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1104.java) | | Medium | Math, Tree |
419420
| 1103 | [Distribute Candies to People](https://leetcode.com/problems/distribute-candies-to-people/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1103.java) | | Easy | Math |
420421
| 1100 | [Find K-Length Substrings With No Repeated Characters](https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/secondthousand/_1100.java) | | Medium | String, Sliding Window |

‎src/main/java/com/fishercoder/solutions/secondthousand/_1230.java

+21
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.fishercoder.solutions.secondthousand;
2+
3+
public class _1230 {
4+
public static class Solution1 {
5+
public double probabilityOfHeads(double[] prob, int target) {
6+
int n = prob.length;
7+
//initialize a 2-D array, column size should be target + 1
8+
//dp[i][j] means the probability of getting j heads using the first i coins
9+
//so dp[n][target] is the answer where n is the number of coins
10+
double[][] dp = new double[n + 1][target + 1];
11+
dp[0][0] = 1;
12+
for (int i = 1; i <= n; i++) {
13+
dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]);
14+
for (int j = 1; j <= target && j <= i; j++) {
15+
dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]);
16+
}
17+
}
18+
return dp[n][target];
19+
}
20+
}
21+
}

‎src/test/java/com/fishercoder/secondthousand/_1230Test.java

+47
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.fishercoder.secondthousand;
2+
3+
import com.fishercoder.solutions.secondthousand._1230;
4+
import org.junit.jupiter.api.BeforeEach;
5+
import org.junit.jupiter.api.Test;
6+
7+
import static org.junit.jupiter.api.Assertions.assertEquals;
8+
9+
public class _1230Test {
10+
private static _1230.Solution1 solution1;
11+
12+
@BeforeEach
13+
public void setup() {
14+
solution1 = new _1230.Solution1();
15+
}
16+
17+
@Test
18+
public void test1() {
19+
assertEquals(0.4, solution1.probabilityOfHeads(new double[]{0.4}, 1));
20+
}
21+
22+
@Test
23+
public void test2() {
24+
assertEquals(0.03125, solution1.probabilityOfHeads(new double[]{0.5, 0.5, 0.5, 0.5, 0.5}, 0));
25+
}
26+
27+
@Test
28+
public void test3() {
29+
assertEquals(0.125, solution1.probabilityOfHeads(new double[]{0.5, 0.25}, 2));
30+
}
31+
32+
@Test
33+
public void test4() {
34+
assertEquals(0.21875, solution1.probabilityOfHeads(new double[]{0.5, 0.25, 0.25}, 2));
35+
}
36+
37+
@Test
38+
public void test5() {
39+
assertEquals(0.375, solution1.probabilityOfHeads(new double[]{0.5, 0.5, 0.5, 0.5}, 2));
40+
}
41+
42+
@Test
43+
public void test6() {
44+
assertEquals(0.31250, solution1.probabilityOfHeads(new double[]{0.5, 0.5, 0.5, 0.5, 0.5, 0.5}, 3));
45+
}
46+
47+
}

0 commit comments

Comments
 (0)