非死不可 9/16 面筋

victorsterling 发表于 2016-9-29 02:53
如果是返回所有结果的话，需要考虑所有的可能性，所以要用dfs 把所有的都找一遍。这种难度就属于难一些的 ...

one pass怎么做？能具体说说思路吗

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

wopani007 发表于 2016-10-2 01:51
hi，感觉你去掉了多余的），但是没去掉多余的（

补充内容 (2016-10-2 14:51):

对，我写的有点麻烦了，可以从左到右遍历一遍得到delete list， 然后再从右到左得到结果就好了

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

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

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

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