735. Asteroid Collision - Medium

前往題目

想法

• 小行星相撞有可能會消失，如果一方比較大；如果一樣大兩個都會消失。這樣來看的話可能需要一個額外的array，不然會有空位而且還要移動element

思路

快解出來了，但時間用得有點久，還是看看neetcode大大怎麼寫的

其實蠻簡單的，只要列出判斷條件和使用stack就可以輕鬆解

1. 疊代每個行星
2. 每次疊代都檢查是否與最近一個行星相撞，把兩數加起來就可以很快判斷誰大誰小或是相等
3. 相撞完後如果當前行星還活著就加到stack裡
4. 最後回傳stack的element就好

Code

Stack在Java中沒有快速轉換成int[]的方法，所以只好土法煉鋼，不然就是純int[]，不用stack

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack();
        
        for (int ast : asteroids) {
            // Definitely collide
            while (!stack.isEmpty() && ast < 0 && stack.peek() > 0) {
                // Difference between the colliding asteroids
                // So able to know who is larger etc.
                int diff = ast + stack.peek();
                // Negative asteroid is larger
                if (diff < 0) {
                    stack.pop();
                } else if (diff > 0) {
                    ast = 0;
                } else { // They are the same size
                    stack.pop();
                    ast = 0;
                }
            }

            // Push to the stack
            if (ast != 0) stack.push(ast);
        }

        int[] res = new int[stack.size()];
        for (int i = res.length - 1; i >= 0; --i) {
            res[i] = stack.pop();
        }

        return res;
    }
}

2024/05/06

• 沒找出判斷條件

2024/08/08

• 差了一點，忘了用循環