记一次面试经历

FB2

问题就是清除掉多余的括号。字符串里可能会有除括号外的其他字符。返回一个possible就可以不是返回所有的。

我的思路是一个stack辅助,保存left,遇到right如果stack为空则去掉这个right,如果不为空就pop。最后stack里面的剩下的就是invalid的left需要去掉。这么做有一些catch,第一就是你不能在push left的过程中直接remove right,否则stack存的index都乱了,因为我们动态修改了字符串长度。所以遇到非法right要先标记特殊字符然后最后再删掉。 最后删掉的时候也要注意其实还是在动态修改长度,index要记得再i 减减才可以继续循环(这个我忽略了)。

然后被问了一个不用stack的解法。没能自己想出来,给了提示。说,其实我们不用去记住left的每一个index。最左边的括号可以考虑是可以match anything的。这是他原话,没有让我明白其实。后来再经过例子的提示,明白了解法。 左边的有几个就需要有几个右边的来match,如果没有match的就是invalid的。那么我们仅需要统计左边和右边括号的数量,然后如果左边的多那就从后往前遍历数组,删掉前n个,n为左右数量差值。如果需要删掉右边的,那就从前往后遍历。

这个方法真心不错,之前练习的时候从来没想过这个思路,还是蛮开心的能学到东西。希望下一次学东西不是在面试现场啊。。这次能不能通过就看缘分吧,希望能继续下去!

Like what you read? Give DeReK a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.