剑指 Offer II 037. 小行星碰撞

剑指 Offer II 037. 小行星碰撞

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

示例 4：

输入：asteroids = [-2,-1,1,2]
输出：[-2,-1,1,2]
解释：-2 和 -1 向左移动，而 1 和 2 向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。

解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
    int r[asteroidsSize];
    r[0]=asteroids[0];
    int size=1;
    int i;
    for(i=1;i<asteroidsSize;i++){
        int now=asteroids[i];
      //  printf("-- %d %d %d",now,r[size-1],size);
      if(size==0){
           r[size++]=now;
           continue;

      }
        if(now*r[size-1]<0&&now<0){
            //printf("%d %d ",abs(now),abs(r[size-1]));
            while(abs(r[size-1])<=abs(now)&&size!=0&&now*r[size-1]<0&&now<0){
                if(abs(r[size-1])==abs(now)){
                    size--;
                   // printf("%d ",size);
                    break;
                }
                //if(size==)
              
                size--;
                if(size==0){
                    break;
                }
            }
            if(size>=1)
            if(now*r[size-1]>0&&r[size]!=-now){
                 r[size++]=now;

            }
            if(size==0&&r[0]!=-now){
                  r[size++]=now;

            }
        
        

        }
        else{
            r[size++]=now;
         //   printf("| %d ",size);
        }

    }
   // printf("size %d ",size);
    for(i=0;i<size;i++){
        asteroids[i]=r[i];
      //  printf("%d ",r[i]);
    }
    * returnSize=size;
    return asteroids;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59