[facebook]第一轮技术电面

今天面了一个半星期前约的电面，国人小哥面的，题目不是很难，两道题各写一个函数，statement如下：

1. merge two arrays in-place
例子：
a = [2,4,6,8, _, _, _, _]
b = [1,3,5,7]

Note：_代表空的位置，用以merge。a的actual length与b一样，并且a的空余位置足够放入b。a, b都是sorted array，要求in-place merge两个array。
感受：题目条件明确，简单思路就是从两个数列的尾部（这个例子中对于a是从8开始）比较，哪个更大就放在a的末端。需要注意到当a被遍历完后，要将b剩下的数字照搬到a的前端。

2. balance parentheses in a string
例子：
"(a)()" -> "(a)()"
"((bc)" -> "(bc)"
")))a((" -> "a"
"(a(b)" ->"(ab)" or "a(b)"

Note: balance的意思就是把原来string里unpaired的括号变成paired的形式。如果有多个可能的结果， 比如上述最后一种情况，我们就只需要输出一个对的结果即可，所以这点简化了题目的难度。
感受： 遍历string， 用一个stack存储每个open parenthesis的index，也就是'('的i

游客，本帖隐藏的内容需要积分高于 188 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

4.gif" smilieid="112" border="0" alt="" />然后我觉得我的解法也行的通，所以跟他说了下，他也表示认同，但需要回去检验下。欢迎大家参与讨论！

就是这样。

希望进入下一轮吧，顺便求点大米！

不用stack, 使用 counter 记录违规的括号, 两个loop, 第一个从左到右删')', 第二个从右到左删'('

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        s = delR(s);
        s = delL(s);
        return s;
    }
   
    private String delR(String s) {
        StringBuilder sb= new StringBuilder();
        for (char c : s.toCharArray()) {
            sb.append(c);
            if (c == '(') {
                l++;
            } else if (c == ')') {
                if (l > 0) l--;
                else {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
        return sb.toString();
    }
   
   
    private String delL(String s) {
        StringBuilder sb= new StringBuilder();
        for (int i = s.length()-1; i >= 0; i--) {
            char c = s.charAt(i);
            sb.insert(0,c);
            if (c == ')') {
                l++;
            } else if (c == '(') {
                if (l > 0) l--;
                else sb.deleteCharAt(0);
            }
        }
        return sb.toString();
    }
}

spoonfree 发表于 2016-6-3 03:57
恩，我这里表述得不是很清楚，把unpaired的括号变成paired的形式指 维持原来已经配对的括号， 解决掉那些 ...

稍微想了一下space O(1), one pass的做法：
用一个int来维护，遇到左括号+1, 右括号-1, <0就直接去掉当前右括号，最后结果>0就往后补齐右括号。

mdyuki1016 发表于 2016-6-7 18:47
不用stack, 使用 counter 记录违规的括号, 两个loop, 第一个从左到右删')', 第二个从右到左删'('

public ...

不错不错。其实可以不用insert(0, c). 直接最后sb.reverse().toString() 就好了。

“balance的意思就是把原来string里unpaired的括号变成paired的形式。”

那为什么：")))a((" -> "a" 而不是 ”((()))a(())“ ? 否则的话所有testcase直接去掉所有括号就成立了。。

Wingszero 发表于 2016-6-3 03:19
“balance的意思就是把原来string里unpaired的括号变成paired的形式。”

那为什么：")))a((" -> "a" 而 ...

恩，我这里表述得不是很清楚，把unpaired的括号变成paired的形式指 维持原来已经配对的括号， 解决掉那些未配对的括号。至于你怎么解决，是删除冗余括号还是添加括号，自己选择。当时面试官给我的例子，看上去是删除，所以我就默认是删除了。把括号都删除，这题就没意思了呀！

有没有版主支持新人一记大米？

第二题是不是类似lc 301 Remove invalid parentheses?

用两个变量代替stack中的括号数？

Nirvason 发表于 2016-6-3 04:20
第二题是不是类似lc 301 Remove invalid parentheses?

蛮不一样，LC这道只减不增，最短，并返回所有情况。

Nirvason 发表于 2016-6-3 04:20
第二题是不是类似lc 301 Remove invalid parentheses?

这题只用找出一种可能解就好，所以复杂度没lc 301高。

我按照只有删除括号的操作重写了下代码

1. public class balance {
   
2.         String solution (String string) {
   
3.                 int countOpen = 0, countClose = 0;
   
4.                 char[] str =  string.toCharArray();
   
5.                 StringBuilder res = new StringBuilder();
   
6.                
   
7.                 int i = 0, j = str.length - 1;
   
8.                
   
9.                 while(i < j) {
   
10.                         if(str[i] == '(') {
    
11.                                         countOpen++;
    
12.                                 }
    
13.                         else if(str[i] == ')') {
    
14.                                         if(countOpen == 0) str[i] = '#';
    
15.                                         else countOpen--;
    
16.                                 }
    
17. 
    
18. 
    
19.                         if(countClose >= 0) {
    
20.                                 if(str[j] == ')') {
    
21.                                         countClose++;
    
22.                                 }
    
23.                                 else if(str[j] == '(') {
    
24.                                         if(countClose == 0) str[j] = '#';
    
25.                                         else countClose--;
    
26.                                 }
    
27.                         }
    
28.                         i++;
    
29.                         j--;
    
30.                        
    
31.                 }
    
32.                 if(i == j) {
    
33.                         if(str[i] == '(') countOpen++;
    
34.                         if(str[j] == ')') countClose++;
    
35.                 }
    
36.                
    
37.                 if(countOpen > countClose) {
    
38.                         int count = countOpen - countClose;
    
39.                         while(count > 0) {
    
40.                                 if(str[i] == '(') {
    
41.                                         str[i] = '#';
    
42.                                         count--;
    
43.                                 }
    
44.                                 i--;
    
45.                         }
    
46.                 }
    
47.                 else {
    
48.                         int count = countClose - countOpen;
    
49.                         while(count > 0) {
    
50.                                 if(str[j] == ')') {
    
51.                                         str[j] = '#';
    
52.                                         count--;
    
53.                                 }
    
54.                                 j++;
    
55.                         }
    
56.                 }
    
57.                
    
58.                 for(i = 0; i < str.length; i++) {
    
59.                         if(str[i] != '#') {
    
60.                                 res.append(str[i]);
    
61.                         }
    
62.                 }
    
63.                
    
64.                 return res.toString();
    
65.         }
    
66. }
    

复制代码

我发给面试我的小哥看了下，他人很nice的帮我看了下，然后分享了一个更好的思路。我也分享给大家以供参考。

I've read through your final code and it appears to be working - I haven't found a counter example yet. A much cleaner way to do this is do 2 rounds of scans with a counter on open parens first and one with a counter on close parens. The first scan finds all unmatched close parens and the second one finds all unmatched open parens (similar to what you did in your loop). This way you don't have to handle the case when two pointers meet.