FB一面面经

模拟stack的方式， 两个指针从两头同时向中间走， 一个变量计数左边的open parenthesis, 一个记录右边的close parenthesis, 左边碰到open ++, close --, 0的时候碰到close就是非法，改为点， 右边往左走同理， close++, open--, 最后左指针>=右指针的时候停止。

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

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

shuxiong 发表于 2018-11-7 15:04
指针有加有减 不一定extractly one pass呀

我也想到差不多的方法，不好证明就是one pass

加减的是计数变量，不是指针，这里的指针其实是数组下标，每次都往中间前进一步

请问楼主有消息了吗？

Moyimoyi 发表于 2018-11-7 18:07
请问楼主有消息了吗？

木有。紫薯紫薯

我上周面的第一题也是单调数组，我都过了一周了还没消息。。。

YaxiLi 发表于 2018-11-7 22:54
我上周面的第一题也是单调数组，我都过了一周了还没消息。。。

随缘随缘

Sidney_L 发表于 2018-11-7 14:44
模拟stack的方式， 两个指针从两头同时向中间走， 一个变量计数左边的open parenthesis, 一个记录右边的clo ...

感觉这种方法对于 （）（）（））这种情况还是不行？

可以用两个flag left和right，当left遇到左括号加一右括号减一，right相反 小于0时为invalid变成点
好像和刷题网二三吧有点像

1. public static String removeInvalidParentheses(String input) {
   
2.         char[] inputChars = input.toCharArray();
   
3.         int len = inputChars.length;
   
4.         int left = 0;
   
5.         int right = 0;
   
6.         for (int i = 0; i < len; i ++) {
   
7.             if (Character.isLetter(inputChars[i])) {
   
8.                 continue;
   
9.             }
   
10.             if (inputChars[i] == '(') {
    
11.                 left ++;
    
12.             }
    
13.             else if (inputChars[i] == ')') {
    
14.                 left --;
    
15.             }
    
16.             if (left < 0) {
    
17.                 inputChars[i] = '.';
    
18.                 left = 0;
    
19.             }
    
20.             if (inputChars[len - i - 1] == ')') {
    
21.                 right ++;
    
22.             }
    
23.             else if (inputChars[len - i - 1] == '(') {
    
24.                 right --;
    
25.             }
    
26.             if (right < 0) {
    
27.                 inputChars[len - i - 1] = '.';
    
28.                 right = 0;
    
29.             }
    
30.         }
    
31.         return new String(inputChars);
    
32.     }

复制代码

子怡怡起床了 发表于 2018-11-8 02:58
感觉这种方法对于 （）（）（））这种情况还是不行？

确实，脑子一热就觉得可行了，现在觉得one pass确实不知如何实现。。。