小行星碰撞(使用deque操作)

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

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

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

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
         Deque<Integer> sta = new LinkedList<>();
        for(int a : asteroids){
            if(!sta.isEmpty() && sta.peekLast()>0 && a < 0){
            boolean disappear = false;

            // while的目的是为了持续向左撞
            while(!sta.isEmpty() && sta.peekLast() > 0 && a < 0){
                int peng = sta.peekLast() + a;
                if(peng == 0){
                    disappear = true;
                    sta.pollLast();
                    // sta.pollLast();
                    break;
                }else if(peng > 0){
                    disappear = true;
                    // sta.pollLast();
                    break;
                }else {
                    sta.pollLast();
                    break;
                }
            }
            if(disappear == false){
                sta.addLast(a);
            }
        }else{
            sta.addLast(a);
        }
        }
        int n = sta.size();
        int[] res = new int[n];
        for(int i = 0; i < n; i++){
            res[i] = sta.pollFirst();
        }
        return res;
    }
}

这里使用for以deque.size()为限制条件会出问题,因为拿出是以从队列拿出的方式,所以deque的长度发生了变化会少值

普通队列(一端进另一端出):
Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出)
Deque deque = new LinkedList()
堆栈
Deque deque = new LinkedList()

 

       第一个元素 (头部)      最后一个元素 (尾部)
       抛出异常    特殊值      抛出异常    特殊值
插入    addFirst(e)    offerFirst(e)    addLast(e)    offerLast(e)
删除    removeFirst()    pollFirst()    removeLast()    pollLast()
检查    getFirst()    peekFirst()    getLast()    peekLast()

小行星碰撞(使用deque操作)

上一篇:私有定义指令


下一篇:2021CCPC网络选拔赛题解