https://leetcode.com/problems/asteroid-collision/description/
The length of
Each asteroid will be a non-zero integer in the range
https://leetcode.com/problems/asteroid-collision/solution/
https://leetcode.com/problems/asteroid-collision/discuss/109694/JavaC++-Clean-Code
https://leetcode.com/problems/asteroid-collision/discuss/109692/Easy-Java-AC-with-LinkedList
X. No extra space
public int[] asteroidCollision(int[] asteroids) { if (asteroids == null || asteroids.length == 1) return asteroids; int end = -1; int i = 0; while (i < asteroids.length) { asteroids[++end] = asteroids[i]; if (asteroids[i] < 0) { while (end - 1 >= 0 && asteroids[end - 1] > 0) { int sum = asteroids[end - 1] + asteroids[end]; if (sum < 0) { asteroids[--end] = asteroids[i]; } else if (sum == 0) { end -= 2; break; } else { end--; break; } } } i++; } return Arrays.copyOf(asteroids, end + 1); }
https://leetcode.com/problems/asteroid-collision/discuss/109662/Java-solution-beat-90-No-extra-space.
We are given an array
asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. 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.
Example 1:
Input: asteroids = [5, 10, -5] Output: [5, 10] Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Example 2:
Input: asteroids = [8, -8] Output: [] Explanation: The 8 and -8 collide exploding each other.
Example 3:
Input: asteroids = [10, 2, -5] Output: [10] Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Example 4:
Input: asteroids = [-2, -1, 1, 2] Output: [-2, -1, 1, 2] Explanation: The -2 and -1 are moving left, while the 1 and 2 are moving right. Asteroids moving the same direction never meet, so no asteroids will meet each other.
Note:
asteroids will be at most 10000.[-1000, 1000]..
Say we have our answer as a stack with rightmost asteroid
top, and a new asteroid comes in. If new is moving right (new > 0), or if top is moving left (top < 0), no collision occurs.
Otherwise, if
abs(new) < abs(top), then the new asteroid will blow up; if abs(new) == abs(top) then both asteroids will blow up; and if abs(new) > abs(top), then the top asteroid will blow up (and possibly more asteroids will, so we should continue checking.)
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack();
for (int ast: asteroids) {
collision: {
while (!stack.isEmpty() && ast < 0 && 0 < stack.peek()) {
if (stack.peek() < -ast) {
stack.pop();
continue;
} else if (stack.peek() == -ast) {
stack.pop();
}
break collision;
}
stack.push(ast);
}
}
int[] ans = new int[stack.size()];
for (int t = ans.length - 1; t >= 0; --t) {
ans[t] = stack.pop();
}
return ans;
}
https://leetcode.com/problems/asteroid-collision/discuss/109694/JavaC++-Clean-Code
https://leetcode.com/problems/asteroid-collision/discuss/109692/Easy-Java-AC-with-LinkedList
public int[] asteroidCollision(int[] a) {
LinkedList<Integer> s = new LinkedList<>(); // use LinkedList to simulate stack so that we don't need to reverse at end.
for (int i = 0; i < a.length; i++) {
if (a[i] > 0 || s.isEmpty() || s.getLast() < 0)
s.add(a[i]);
else if (s.getLast() <= -a[i])
if (s.pollLast() < -a[i]) i--;
}
return s.stream().mapToInt(i->i).toArray();
}
The above approach is short but not intuitive, because it handles positive stars on the stack top with less mess than the incoming negative star once a time each loop.
More intuitively we can pop all positive star with less mass right away using a while loop in side the for loop. public int[] asteroidCollision(int[] a) {
LinkedList<Integer> s = new LinkedList<>();
for (int i : a) {
if (i > 0)
s.add(i);
else {
while (!s.isEmpty() && s.getLast() > 0 && s.getLast() < -i)
s.pollLast();
if (!s.isEmpty() && s.getLast() == -i)
s.pollLast();
else if (s.isEmpty() || s.getLast() < 0)
s.add(i);
}
}
return s.stream().mapToInt(i->i).toArray();
}
public int[] asteroidCollision(int[] asteroids) {
// stack
Deque<Integer> stack = new ArrayDeque<>();
for (int asteroid : asteroids) {
if (stack.isEmpty()) {
stack.addLast(asteroid);
} else {
handle(stack, asteroid);
}
log(stack);
}
// as a queue, fifo
return stack.stream().mapToInt(i -> i).toArray();
}
private void handle(Deque<Integer> stack, int asteroid) {
boolean newOnegone = false;
while (!stack.isEmpty()) {
int prev = stack.peekLast();
// -10 <-
if (asteroid < 0) {
if (prev < 0) {
break;
} else {
// prev = 20
if (prev > Math.abs(asteroid)) {
newOnegone = true;
break;
}
// prev = 10 or 5
stack.pollLast();
if (prev == Math.abs(asteroid)) {
newOnegone = true;
break;
}
}
} else {
// a:10
break;
}
}
if (!newOnegone) {
stack.addLast(asteroid);
}
}
X. No extra space
public int[] asteroidCollision(int[] asteroids) { if (asteroids == null || asteroids.length == 1) return asteroids; int end = -1; int i = 0; while (i < asteroids.length) { asteroids[++end] = asteroids[i]; if (asteroids[i] < 0) { while (end - 1 >= 0 && asteroids[end - 1] > 0) { int sum = asteroids[end - 1] + asteroids[end]; if (sum < 0) { asteroids[--end] = asteroids[i]; } else if (sum == 0) { end -= 2; break; } else { end--; break; } } } i++; } return Arrays.copyOf(asteroids, end + 1); }
public int[] asteroidCollision(int[] asteroids) {
if (asteroids.length < 2) {
return asteroids;
}
if (asteroids.length < 2) {
return asteroids;
}
int index = 1;
int end =0;
while (index < asteroids.length) {
if(end==-1) {
asteroids[0] = asteroids[index];
end=0;
index++;
continue;
} else {
if (asteroids[end] > 0 && asteroids[index] < 0) {
if (Math.abs(asteroids[end]) == Math.abs(asteroids[index])) {
end--;
index++;
} else if (Math.abs(asteroids[end]) > Math.abs(asteroids[index])) {
index++;
} else {
end--;
}
} else {
end++;
asteroids[end] = asteroids[index];
index++;
}
}
}
return Arrays.copyOf(asteroids, end+1);
