非死不可 9/16 面筋

今天上午面了非死不可，口音挺标准的男人，说是internatinalization组的，上来先来个自我介绍接着就是做题
LC301 Remove Invalid Parentheses，我突然发现这个题我快

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

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

g>补充内容 (2016-9-17 03:41):
感觉自己真要像公司名字一样，非死不可了

看来需要确保在做题之前做好沟通工作啊。。。
帮楼主祈祷onsite

kobe24 发表于 2016-9-28 14:22
one pass怎么做？能具体说说思路吗

写的有点麻烦，time complexity O(n), 感觉不是很efficient，在这里抛砖引玉一下

1. public static String remove(String s) {
   
2.                 StringBuilder sb = new StringBuilder();
   
3.                 int cur = 0;
   
4.                 LinkedList<Integer> list = new LinkedList<>();
   
5.                 for (int i = 0; i < s.length(); i++) {
   
6.                         if (s.charAt(i) == '(') {
   
7.                                 cur++;
   
8.                                 list.addLast(i);
   
9.                         } else if (s.charAt(i) == ')') {
   
10.                                 if (cur > 0) {
    
11.                                         cur--;
    
12.                                         list.removeLast();
    
13.                                 }
    
14.                         }
    
15.                 }
    
16.                 cur = 0;
    
17.                
    
18.                 if (!list.isEmpty()) {
    
19.                         int del = list.removeFirst();
    
20.                         for (int i = 0; i < s.length(); i++) {
    
21.                                 if (i == del) {
    
22.                                         if (!list.isEmpty()) {
    
23.                                                 del = list.getFirst();
    
24.                                         }
    
25.                                         continue;
    
26.                                 }
    
27.                                 if (s.charAt(i) == '(') {
    
28.                                         cur++;
    
29.                                         sb.append(s.charAt(i));
    
30.                                 } else if (s.charAt(i) == ')') {
    
31.                                         if (cur > 0) {
    
32.                                                 cur--;
    
33.                                                 sb.append(s.charAt(i));
    
34.                                         }
    
35.                                 } else {
    
36.                                         sb.append(s.charAt(i));
    
37.                                 }
    
38.                         }
    
39.                 } else {
    
40.                         for (int i = 0; i < s.length(); i++) {
    
41.                                 if (s.charAt(i) == '(') {
    
42.                                         cur++;
    
43.                                         sb.append(s.charAt(i));
    
44.                                 } else if (s.charAt(i) == ')') {
    
45.                                         if (cur > 0) {
    
46.                                                 cur--;
    
47.                                                 sb.append(s.charAt(i));
    
48.                                         }
    
49.                                 } else {
    
50.                                         sb.append(s.charAt(i));
    
51.                                 }
    
52.                         }
    
53.                 }
    
54.                
    
55.                
    
56.                 return sb.toString();
    
57.         }

复制代码

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

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

为楼主祈福

lz是不是面经没仔细看啊？面经里涉及到这道题90%都是返回一个结果啊。

lz是怎么拿到面试的呢。
您是明年5月毕业么。

同为楼主祈福

不能背题呀。。这题如果就返回一个结果的话，2-pass扫两遍就做出来了。。

问下楼主FB用的什么编辑器电面呀？HackerRank? Collabedit?

这道题究竟怎么做？我看很多网上答案都是用bfs，为啥有些人说扫一遍就可以

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

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