yoruru的努力日記

735. Asteroid Collision

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.

Constraints:

• 2 <= asteroids.length <= 104
• -1000 <= asteroids[i] <= 1000
• asteroids[i] != 0

SOL：

又是考驗英文能力的一個題目><

參考：花花酱 LeetCode 735. Asteroid Collision

題目是在描述有一堆小行星，+/-表方向，數字(絕對值)表行星的大小。當不同方向的行星相遇時，大行星會活著，小行星會死掉。若大小相同，就都死掉。

此外，有一個例子現在題目沒給，但花花的影片有(應該是以前有給?)

Input: asteroids = [-2,-1,1,2]

Output: [-2,-1,1,2]

在這個例子裏面，可以看到即使方向不同不一定就會碰撞。因為負的會一直向左，正的會一直向右，有點像數線的概念，因此他們不會相遇。

解題思路如上，令我比較驚豔的是花花在處理 stack[top] 被 asteroids[i] 撞飛，又要繼續檢查stack中的下一個行星的這種看似遞迴的問題，他很簡潔的使用 i-- (把asteroids[i]再處理一次) 來解決。

if(abs(stack[top])<abs(asteroids[i])) i--;

程式碼也比我原本寫得很簡潔好看很多，真不愧是刷題熟練的大神。

if(abs(stack[top])<abs(asteroids[i])){
    top--;
    i--;
}
else if(abs(stack[top])==abs(asteroids[i])){
    top--;
}

最後附上我的C程式碼：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
    int *stack = (int*)malloc(sizeof(int)*asteroidsSize);
    int top  = -1;
    for(int i = 0; i < asteroidsSize; i++){
        if(asteroids[i]>0)
            stack[++top]=asteroids[i];
        else if(asteroids[i]<0){
            if(top==-1 || stack[top]<0)
                stack[++top]=asteroids[i];
            else{
                if(abs(stack[top])<=abs(asteroids[i])){
                    if(abs(stack[top])<abs(asteroids[i])) i--;
                    top--;
                }
            }
        }
    }
    *returnSize = top+1;
    return stack;
}