Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit82a298e

Browse files
add a solution for 452
1 parent5a98d2c commit82a298e

File tree

2 files changed

+41
-0
lines changed

2 files changed

+41
-0
lines changed

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

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,4 +54,31 @@ public int findMinArrowShots(int[][] points) {
5454
returnminArrows;
5555
}
5656
}
57+
58+
publicstaticclassSolution3 {
59+
/**
60+
* Another approach of mine: completely original.
61+
* 1. Sort the points by start first, if tie, sort by end, both ascendingly.
62+
* 2. While checking, we'll keep updating the ending to be the smaller one so that we don't possibly miss to burst a balloon. See test case 4 for this class.
63+
*/
64+
65+
publicintfindMinArrowShots(int[][]points) {
66+
intarrowShots =0;
67+
Arrays.sort(points, (a,b) ->a[0] !=b[0] ?Integer.compare(a[0],b[0]) :Integer.compare(a[1],b[1]));
68+
for (inti =0;i <points.length; ) {
69+
intend =points[i][1];
70+
intj =i +1;
71+
for (;j <points.length;j++) {
72+
if (points[j][0] <=end) {
73+
end =Math.min(end,points[j][1]);
74+
}else {
75+
break;
76+
}
77+
}
78+
i =j;
79+
arrowShots++;
80+
}
81+
returnarrowShots;
82+
}
83+
}
5784
}

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

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,11 +10,13 @@
1010
publicclass_452Test {
1111
privatestatic_452.Solution1solution1;
1212
privatestatic_452.Solution2solution2;
13+
privatestatic_452.Solution3solution3;
1314

1415
@BeforeClass
1516
publicstaticvoidsetup() {
1617
solution1 =new_452.Solution1();
1718
solution2 =new_452.Solution2();
19+
solution3 =new_452.Solution3();
1820
}
1921

2022
@Test
@@ -23,6 +25,7 @@ public void test1() {
2325
("[3,9],[7,12],[3,8],[6,8],[9,10],[2,9],[0,9],[3,9],[0,6],[2,8]");
2426
assertEquals(2,solution1.findMinArrowShots(points));
2527
assertEquals(2,solution2.findMinArrowShots(points));
28+
assertEquals(2,solution3.findMinArrowShots(points));
2629
}
2730

2831
@Test
@@ -31,6 +34,7 @@ public void test2() {
3134
("[-2147483646,-2147483645],[2147483646,2147483647]");
3235
assertEquals(2,solution1.findMinArrowShots(points));
3336
assertEquals(2,solution2.findMinArrowShots(points));
37+
assertEquals(2,solution3.findMinArrowShots(points));
3438
}
3539

3640
@Test
@@ -39,6 +43,16 @@ public void test3() {
3943
("[0,6],[0,9],[7,8]");
4044
assertEquals(2,solution1.findMinArrowShots(points));
4145
assertEquals(2,solution2.findMinArrowShots(points));
46+
assertEquals(2,solution3.findMinArrowShots(points));
47+
}
48+
49+
@Test
50+
publicvoidtest4() {
51+
int[][]points =CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray
52+
("[9,12],[1,10],[4,11],[8,12],[3,9],[6,9],[6,7]");
53+
assertEquals(2,solution1.findMinArrowShots(points));
54+
assertEquals(2,solution2.findMinArrowShots(points));
55+
assertEquals(2,solution3.findMinArrowShots(points));
4256
}
4357

4458
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp