麻烦问问大家消消乐这题正确解法。。

input = "aabbbbaccddddc", output = "&qu

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

解释，但我还是太渣写不出来。求地里的大哥帮忙写写，给点思路。。。

这个楼里有正确答案 http://www.1point3acres.com/bbs/thread-428868-1-1.html

qwqwqw74189 发表于 2018-10-12 08:28
这个楼里有正确答案 http://www.1point3acres.com/bbs/thread-428868-1-1.html

看到了，感谢！！

这用stack写不出来？…

来自一亩三分地官方APP

我想问个问题，像('aaabbba') 这种test case，前面的aaa是直接删掉，还是得等后面的a才删啊，如果是前面的情况，可以用stack，返回a，如果是后面的情况，返回空，应该只能用递归。

gggpps 发表于 2018-10-13 01:33
我想问个问题，像('aaabbba') 这种test case，前面的aaa是直接删掉，还是得等后面的a才删啊，如果是前面的 ...

这个感觉确实定义的不明确，我个人觉得是每一步“同时”消除所有可以消除的，所以第一步之后前6个字符都没有了，但是最后一个a无法消除，所以最后剩a

肥宅快乐水 发表于 2018-10-12 12:27
这用stack写不出来？…

来自一亩三分地官方APP

单纯用Leetcode提供的普通1D消消乐stack解法不行。
用楼主的test case， AAABBBA, 当B放入的瞬间就会消去前面stack里的AAA(或者 ('A',3)这么一个tuple，那么后面的A就无法被去除掉会得到A为结果的

yayafuture 发表于 2019-9-16 07:06
这个感觉确实定义的不明确，我个人觉得是每一步“同时”消除所有可以消除的，所以第一步之后前6个字符都 ...

这题如果是游戏，肯定是同时消了

我觉得解法和lc上的思路类似。
可以弄个count[]先算出每个字母连续的个数。从左往右遍历一遍
然后从右面往左遍历一遍，双指针消除A A A B B B   A
1 2 3  1 2 3   1
              p1  p2
p1 >= 3消除， p1 -= 3

A A A B B B   A
1 2 3  1 2 3   1
     p1        p2
p1 (A) == p2(A).如果p1 != p2, p2= p1; p2 --;
p 1 + p2 >= 3消除
p1 -=3, p2 += 1

这题我感觉用Stack + local variable maintain 上一次看见的char是可以解的， local variable更新滞后于stack push/pop 就好  

最后你stack里剩下的要么是留下来的char，要么是空