fb phone希望印度姐姐手下留情

刚面完fb的phone interviewlc 301 remove invalid parentheses 的变形，remove最少的parentheses使它valid，只返回一个解即可。
比如："(a))"

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

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

107" border="0" alt="" />

发个java的解法，只扫描一遍，用stack存储invalid括号的位置，最后把invalid的括号删除就可以了

public String removeInvalid(String input) {
        Stack<Integer> stack = new Stack<Integer>();

        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else if (c == ')') {
                if (stack.isEmpty() || input.charAt(stack.peek()) != '(') {
                    stack.push(i);
                } else {
                    stack.pop();
                }
            }
        }

        StringBuilder sb = new StringBuilder(input);
        while (!stack.isEmpty()) {
            sb.deleteCharAt(stack.pop());
        }

        return sb.toString();
    }

建一个缓存buff解决问题，遇到括号前存入缓存，遇到“(”括号就缓存入栈，遇到“)”就取出栈顶加上左右括号然后更新缓存，最后拼接在一起就好了
   
def removeInvalidParentheses(self, s):
        a = []
        cnt = 0
        buf = ""
        for c in s:
            if c!="(" and c!=")":
                buf+=c
            if c=="(":
                if cnt>=len(a):
                    a.append(buf)
                else:
                    a[cnt] = buf
                buf = ''
                cnt += 1
            if c==")":
                if cnt != 0:
                    buf = a[cnt-1] + '('+buf+')'
                    cnt -= 1
        return ''.join(a[0:cnt]) + buf

觉得用stack 的方法 比较clean。或者，这么写也行。

    String removeParentheses(String input, char[] p) {
        int l =0;
        StringBuilder sb = new StringBuilder();
        for (int i =0; i<input.length(); i++) {
            if (input.charAt(i) == p[0]) {
                l++;
            } else if (input.charAt(i) == p[1]) {
                l--;
            }
            if (l<0) {
                l++;
            } else {
                sb.append(input.charAt(i));
            }
        }
        if (l != 0) {
            return new StringBuilder(removeParentheses(sb.reverse().toString(), new char[]{')', '('})).reverse().toString();
        }
        return sb.toString();
    }

想问问LZ两个for loop思路是怎么解的？
如果用一个count统计左括号的个数，如果出现左括号就+1，出现右括号就-1
如果count = 0，还有右括号出现就删去这个右括号，如果走完count ！= 0，就从后往前删count个左括号？ 不知道左括号太多的方法处理对不对

LZ面的SDE么？这似乎是FB 的tag下面hard的题，电面就是hard？

zmy1101 发表于 2017-10-31 06:34
想问问LZ两个for loop思路是怎么解的？
如果用一个count统计左括号的个数，如果出现左括号就+1，出现右括 ...

两个for loop就是从左到右去除不合法的左括号，然后从右到左去除不合法的右括号。
你说的这个不能保证都合法吧

beibeixhb 发表于 2017-10-31 06:44
LZ面的SDE么？这似乎是FB 的tag下面hard的题，电面就是hard？

这个题其实不是很难。
我是enterprise engineer, 偏full stack, 也算SDE一种吧？不清楚

可不可以一个在一个for loop里一个下标递增一个递减， 不过还是扫了2遍

1. 
   
2. def getvalidparentheses(s):
   
3.     n = len(s)
   
4.     left_count, right_count = 0, 0
   
5.     left_ret, right_ret = '', ''
   
6.     for i in xrange(n):
   
7.         if s[i] == '(':
   
8.             left_count += 1
   
9.             left_ret += '('
   
10.         elif s[i] == ')':
    
11.             if left_count > 0:
    
12.                 left_count -= 1
    
13.                 left_ret += ')'
    
14.         else:
    
15.             left_ret += s[i]
    
16.         if s[-(i+1)] == ')':
    
17.             right_count += 1
    
18.             right_ret = ')' + right_ret
    
19.         elif s[-(i+1)] == '(':
    
20.             if right_count > 0:
    
21.                 right_count -= 1
    
22.                 right_ret = '(' + right_ret
    
23.         else:
    
24.             right_ret = s[-(i+1)] + right_ret
    
25.     return left_ret if len(left_ret) < len(right_ret) else right_ret
    

复制代码

第一，我们不知道具体要 删除多少个 ，开括号， 闭括号。所以这题一分为二， 先删闭括号， 保证这一轮结束 所有剩下的闭括号，y有 对应的开括号可以match O(n)
然后用同样的算法套路 开括号。O(n)；

一共O（2n）



补充内容 (2017-10-31 07:35):
所以是不存在 一个 for loop 的one pass？

补充内容 (2017-10-31 07:35):
除非用map存index

yzkst06100 发表于 2017-10-31 07:29
第一，我们不知道具体要 删除多少个 ，开括号， 闭括号。所以这题一分为二， 先删闭括号， 保证这一轮结束  ...

对的，我后来用的这个O(2n)的办法。但是没想到O(n)的，写得太慢了，时间不够了

raychainmah 发表于 2017-10-31 07:06
可不可以一个在一个for loop里一个下标递增一个递减， 不过还是扫了2遍

错了。。。请忽略

smiliy宝儿 发表于 2017-10-31 07:46
对的，我后来用的这个O(2n)的办法。但是没想到O(n)的，写得太慢了，时间不够了

楼主就一题吗？这个2n应该也可以过啊