在leetcode面经上发现一道有意思的题目，大家可以一起讨论一下

Frango 发表于 2019-6-14 23:43
早上急着考试没表达清楚。
如果dq空或者当前字母和dp末字母相同，当前字母push到dq末尾.
否则，如果dq大 ...

不行的， 你用你的算法实验下 这个串 233322233

按照你的算法，应该得出33 ，而这题的答案应该是2

说 O(n) 的都是胡 JB 扯, 这题只能 DFS, On2 都不行

1. 3 111 2 111 2 111 2 111 22 111 3 111 3 222 3 111 3 111 3
   
2. 3 22222 3333
   
3. 33333
   
4. 空

复制代码

没想出什么好办法。和奇怪的打印机有些共同点，但是DP左和DP右之间仍然有些情况不能加起来，因为左右相连后不消却“等”的可能是有的。
可以加上memo但是对于算法复杂度不会降低。

是不是有什么数学的方法直接解？

怎么看都是模拟一遍就能做呀，搞一个栈进进出出不就行了？难道不是o(n)吗？

lokilokiloki 发表于 2019-6-15 02:47
说 O(n) 的都是胡 JB 扯, 这题只能 DFS, On2 都不行

同意你的说法，除了DFS真的想不到更好的办法了。
期待高人的解法。

DFS的N^2是怎么看出来的？

这个算是O(n)么

class Solution {
public:

  vector<int> candyCrush(vector<int> input) {
    if (input.size() < 3) {
      return input;
    }
   
    unordered_map<int, int> remove;
    int begin = 0;
    for (int i=1; i<input.size(); i++) {
      if (input[i]==input[i-1]) {
        if (i-begin>1) {
          remove[begin] = i;
        }
      } else {
        begin = i;
      }
    }
   
    unordered_set<int> s;
    for (auto range : remove) {
      for (int i=range.first; i<=range.second; i++) {
        s.insert(i);
      }
    }
   
    vector<int> vr;
    for (int i=0; i<input.size(); i++) {
      if (!s.count(i)) {
        vr.push_back(input[i]);
      }
    }
    return vr;
  }
};

silenceleaf 发表于 2019-6-15 01:05
[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] 怎么判断消掉的顺序？比如这个case是先消除index为2的三个2 ...

同思考这个问题在，感觉要有个从左到右的优先级之类的才能确定消除顺序