脸书电面硅晶

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

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

不谈了，dream company凉了 T_____T。还得继续move on，各位也加油咯！


补充内容 (2018-2-28 08:30):
写错了，应该是一遍除去(，另一遍除去)。哈哈，希望不要让大家误解，多多包涵。

请问第二题和lc301有什么不同呢？简单版本？

tonyabracadabra 发表于 2018-6-3 14:43
请问第二题和lc301有什么不同呢？简单版本？

简单版本就是只需要一个有效的结果就好了，LC版本要求所有的可行解

wasabi_akira 发表于 2018-6-4 01:39
简单版本就是只需要一个有效的结果就好了，LC版本要求所有的可行解

所以应该还是需要BFS走一遍原来的算法然后在找到之后break么~我在想如果是简化的有没有复杂度更低的算法~

tonyabracadabra 发表于 2018-6-4 02:12
所以应该还是需要BFS走一遍原来的算法然后在找到之后break么~我在想如果是简化的有没有复杂度更低的算法~

记不清了，大概就是前面扫一遍，后面扫一遍就差不多了。 ：）

wasabi_akira 发表于 2018-6-4 02:16
记不清了，大概就是前面扫一遍，后面扫一遍就差不多了。 ：）

嗯嗯我查到了

1. public String removeInvalidParentheses(String s) {
   
2.         String r = remove(s, new char[]{'(', ')'});
   
3.         String tmp = remove(new StringBuilder(r).reverse().toString(), new char[]{')', '('});
   
4.         return new StringBuilder(tmp).reverse().toString();
   
5. }
   
6. private String remove(String s, char[] p) {
   
7.         int stack = 0;
   
8.         for (int i = 0; i < s.length(); i++) {
   
9.                 if (s.charAt(i) == p[0])                stack++;
   
10.                 if (s.charAt(i) == p[1])                stack--;
    
11.                 if (stack < 0) {
    
12.                         s = s.substring(0, i) + s.substring(i + 1);
    
13.                         i--;
    
14.                         stack = 0;
    
15.                 }
    
16.         }
    
17.         return s;
    
18. }
    

复制代码

tonyabracadabra 发表于 2018-6-4 02:37
嗯嗯我查到了
[mw_shl_code=java,true]public String removeInvalidParentheses(String s) {
        String r ...

如果只要求输出第一个valid，这个是可以的， 参考https://github.com/tongzhang1994 ... %20Parentheses.java