FB最新面经

这个机会来的比较意外。之前在地里找人内推都没有消息,结果在linkedin遇到猎头公司Vettery,把信息放上去后没想到第一个就是Facebook的recruiter联系到我。和recruiter随便聊了下就安排了电面。今天刚面完

题目并不难,Facebook是出了名的爱考原题。我这次的题目稍微有点变种lc921。这次是一个字符串只包含括号和字母,移除一些括号后,使所有括号都能匹配上,并打印出最终的字符串。例如a(b)c => a(b)c; )a(b)c()( => a(b)c(); 先用stack做的,但是follow up要求不要额外space,答案不算space(以为Java string immutable)。解法就是从左往右扫一遍,记录好(括号的个数openParenthsNum,在从右往左扫一遍,遇到)更新openParenthsNum,遇到多余的(去掉就好。

多谢,没明白怎么完全不用额外空间的,因为要左右各扫一遍记录不匹配括号的位置吧,试着写了下

public static String remove (String str) {
                StringBuilder sb = new StringBuilder();
                int rL = 0;
                int rR = 0;
                int[] idx = new int[str.length()];
                for (int i = 0; i < str.length(); i++) {
                        if (str.charAt(i) == ''('') {
                                rL++;
                        } else if (str.charAt(i) == '')'') {
                                if (rL > 0) rL--;
                                else idx = 1;
                        }
                }

                for (int i = str.length() - 1; i >= 0; i--) {
                        if (str.charAt(i) == '')'') {
                                rR++;
                        } else if (str.charAt(i) == ''('') {
                                if (rR > 0) rR--;
                                else idx = 1;
                        }
                }
                for (int i = 0; i < str.length(); i++) {
                        if (idx == 0) sb.append(str.charAt(i));
                }
                return sb.toString();
        }

补充内容 (2018-11-5 11:40):
复制粘贴过来格式全乱了,idx是数组,记录非法位置的

是 伞陵夷 简单版 ?

thanks for sharing

多谢楼主没设置多少可见棒棒

多谢楼主的分享

应该是 大侠厉害

就是301的第一个步骤,youtube上huahua的讲解不错

感谢分享!