Skip to content

Commit 24b385a

Browse files
fishercoder1534fishercoder1534
committed
[N-0] add 735
1 parent caf579d commit 24b385a

File tree

3 files changed

+168
-0
lines changed

3 files changed

+168
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ Your ideas/fixes/algorithms are more than welcome!
2323
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
2424
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
2525
|737|[Sentence Similarity II](https://leetcode.com/problems/sentence-similarity-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_737.java) | O(nlogk + k) n is the length of max(words1, words2), k is the length of pairs| O(k) | Medium| Union Find
26+
|735|[Asteroid Collision](https://leetcode.com/problems/asteroid-collision/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_735.java) | O(n) | O(n) | Medium | Stack
2627
|734|[Sentence Similarity](https://leetcode.com/problems/sentence-similarity/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_734.java) | O(n*k) | O(1) | Easy | HashTable
2728
|733|[Flood Fill](https://leetcode.com/problems/flood-fill/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_733.java) | O(m*n) | O(m*n) | Easy | BFS, DFS
2829
|729|[My Calendar I](https://leetcode.com/problems/my-calendar-i/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_729.java) | O(n) | O(n) | Medium |

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

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package com.fishercoder.solutions;
2+
3+
import java.util.Stack;
4+
5+
/**
6+
* 735. Asteroid Collision
7+
*
8+
* We are given an array asteroids of integers representing asteroids in a row.
9+
* For each asteroid, the absolute value represents its size, and the sign represents its direction
10+
* (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
11+
* Find out the state of the asteroids after all collisions.
12+
* If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
13+
14+
Example 1:
15+
Input:
16+
asteroids = [5, 10, -5]
17+
Output: [5, 10]
18+
Explanation:
19+
The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
20+
21+
Example 2:
22+
Input:
23+
asteroids = [8, -8]
24+
Output: []
25+
Explanation:
26+
The 8 and -8 collide exploding each other.
27+
28+
Example 3:
29+
Input:
30+
asteroids = [10, 2, -5]
31+
Output: [10]
32+
Explanation:
33+
The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
34+
35+
Example 4:
36+
Input:
37+
asteroids = [-2, -1, 1, 2]
38+
Output: [-2, -1, 1, 2]
39+
Explanation:
40+
The -2 and -1 are moving left, while the 1 and 2 are moving right.
41+
Asteroids moving the same direction never meet, so no asteroids will meet each other.
42+
43+
Note:
44+
The length of asteroids will be at most 10000.
45+
Each asteroid will be a non-zero integer in the range [-1000, 1000]..
46+
47+
*/
48+
public class _735 {
49+
public static class Solution1 {
50+
public int[] asteroidCollision(int[] asteroids) {
51+
Stack<Integer> stack = new Stack();
52+
for (int i = 0; i < asteroids.length; i++) {
53+
if (!stack.isEmpty() && stack.peek() > 0 && asteroids[i] < 0) {
54+
if (Math.abs(stack.peek()) < Math.abs(asteroids[i])) {
55+
stack.pop();
56+
stack.push(asteroids[i]);
57+
collide(stack);
58+
} else if (Math.abs(stack.peek()) == Math.abs(asteroids[i])) {
59+
stack.pop();
60+
}
61+
} else {
62+
stack.push(asteroids[i]);
63+
}
64+
}
65+
int[] result = new int[stack.size()];
66+
int i = stack.size();
67+
while (!stack.isEmpty()) {
68+
result[--i] = stack.pop();
69+
}
70+
return result;
71+
}
72+
73+
private void collide(Stack<Integer> stack) {
74+
do {
75+
Integer top = stack.pop();
76+
if (!stack.isEmpty() && stack.peek() * top < 0) {
77+
if (stack.peek() < Math.abs(top)) {
78+
stack.pop();
79+
stack.push(top);
80+
} else if (stack.peek() == Math.abs(top)) {
81+
stack.pop();
82+
break;
83+
} else {
84+
break;
85+
}
86+
} else if (stack.isEmpty() || stack.peek() * top > 0) {
87+
stack.push(top);
88+
break;
89+
}
90+
} while (!stack.isEmpty());
91+
}
92+
}
93+
}

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

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

0 commit comments

Comments
 (0)