FB一面面经

一面。。口音很重的国人小哥。

两道题

  1. monotonic array。。低频easy。。一开始上来懵了。。没刷过但是现做出来。。有点小Bug。。1,2,2,2这种后面连续相等的也是符合要求的

  2. remove 括号返回一个合法的。。但是输入是char array。。要inplace的将不合法的括号改为一个点,说了stack和two pass两种做法。。写了two pass。但是最后小哥说one pass和常数空间可以做。。我没想出来。。最后没时间他大概讲了下。。也没听懂。。有大神会在底下讲讲。。

貌似同学都是当天和隔天收到的二面通知。。上周五面得还没消息。。。已经move on 了。。大家加油。

2 pass + o(1) space是可行的,但1 pass + o(1) space应该是没法实现的。
正序pass可以过滤掉非法的’’)’’,但没法过滤掉非法的’’(’’。因为判定某个’’(’‘是否非法,需要用到后面的信息。
同理,逆序pass也只能过滤掉非法的’’(’’。
应该可以严格数学证明,有兴趣的同学可以试试

等等呗 感觉还是有戏的

谢谢楼主分享。写了两题,还好啊。可能面馆没有交review.。等等看。 第一题是最近的高频。"要inplace的将不合法的括号改为一个点"是什么意思啊?

就是比如输入是 )(ab 你要变成…ab。。inplace的改

想了想是不是two pointers可以做。left = 0, right = len-1, 遇到不是括号的往下一个移就好了,如果是括号,必须每次保证left =(, right = ),如果哪个不是,哪个就变成点,然后移动那个不对的指针,直到left > right,left = right的情况也有可能是要变点的。

真的能one pass + constant space么?求大神指点

这个不能保证移除最少啊。。()()()这个例子

用两个变量一个记录左括号 一个记录右括号?扫的过程中可以根据匹配情况改,不过扫一遍后发现左括号或者右括号多还得重新扫一遍改非法括号

如果给的input一定是invalid的话,这么做是不是是可以的

还是没太懂。。。
leetcode上 remove parenthesis这道题不是应该dfs或者bfs做吗? 就是那道hard题。

对,这个是two pass

除非有别的特殊条件限制,one pass是没法做的。比如说并没有要求移除最少。