735行星碰撞

下面我自己调了一万年的狗屎算法

我的思路是这样的

• 如果数组非空
  • 判断新来的和老的是否同号
    • 同号push
    • 异号->判断是相近还是相离
      • 相离，push
      • 相近->判断尾部函数是不是大于新来的元素的绝对值
        • 大于->撞死，下一轮循环
        • 等于->pop+continue
        • 小于->pop，再和栈顶比较
          • 到最后判断栈顶是否同号
          • 同号：push
          • 异号->判断栈顶是不是大于或等于
            • 大于->continue
            • 等于->pop+continue
• 如果数组为空
  • push

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
    vector<int> v;
    for (auto i:asteroids) {
        if (!v.empty()) {
            if (i * v.back() > 0) {
                v.push_back(i);
                continue;
            } else {
                if (v.back() < 0) {
                    v.push_back(i);
                    continue;
                } else {
                    if (v.back() > abs(i))
                        continue;
                    else if (v.back() < abs(i)) {
                       while (!v.empty() && v.back() * i < 0 && v.back() < abs(i)) {
                            v.pop_back();
                        }
                        if (!v.empty() && v.back() > abs(i))
                            continue;
                        if (!v.empty() && v.back() == abs(i)) {
                            v.pop_back();
                            continue;
                        }
                        if (!v.empty()&&v.back() < 0)
                            v.push_back(i);
                        if(v.empty())
                            v.push_back(i);
                    } else if (v.back() == abs(i)) {
                        v.pop_back();
                        continue;
                    }
                }
            }
        } else {
            v.push_back(i);
        }
    }
    return v;
    }
};

利用递归和梳理思路，其实可以更简单的表达

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        deque<int> d;
        int last = 0;
        for (auto& e : asteroids) {
            helper(e, d);
        }
        vector<int> v(d.begin(), d.end());
        return v;
    }
    void helper(const int a, deque<int>& s) {
        //deque空了，push
        if (s.empty()) {
            s.push_back(a);
            return;
        }
        //非空，那么令b = s.back()
        int b = s.back();
        //如果队尾和a同号，或者队尾<0，意思是队尾如果<0,肯定可以入队
        if (a * b > 0 || b < 0) {
            s.push_back(a);
        }//如果队尾和对首加起来等于0，这时候肯定是a*b<0且b>0的情况了，所以pop 
        else if (a + b == 0) {
            s.pop_back();
        }//如果绝对值b<绝对值a的话，先pop，再利用递归进行下一次判断 
        else if (abs(b) < abs(a)){
            s.pop_back();
            helper(a, s);
        }
    }
};