FB一轮电面

helloworld11 发表于 2017-11-9 13:41
楼主第二题是two pass每次去掉不符合的'('和')'？

是的是的。。

ivywu_94 发表于 2017-11-9 17:47
谢谢分享！楼主可不可以稍微详细讲一下remove parentheses 那道题呀？ 谢谢啊

唔，这个基本照着地里面经总结的代码写就好啦。。。我基本和那个写的一样。

zzz1322 发表于 2017-11-10 06:08
唔，这个基本照着地里面经总结的代码写就好啦。。。我基本和那个写的一样。

楼主请问可以有没有帖子的链接呢？ 我地里翻了半天没找到，谢谢啦。

补充内容 (2017-11-15 06:59):
就是StringBuilder + 2 pass这个做法的帖子。

补充内容 (2017-11-15 08:20):
找到了：https://instant.1point3acres.com/thread/180240

zzz1322 发表于 2017-11-10 06:08
唔，这个基本照着地里面经总结的代码写就好啦。。。我基本和那个写的一样。

想问一下楼主是先用arraylist记住那些invalid的左括号和右括号的index然后再对arraylist排序然后再用stringbuilder建立结果吗？

补充内容 (2017-11-25 03:03):
还是说是用set存那些invalid的左括号和右括号的index呢?

不用记录。。就直接判断一下当前的是否valid，如果valid就append到StringBuilder。
从左到右一次，从右到左一次

zzz1322 发表于 2017-11-25 03:36
不用记录。。就直接判断一下当前的是否valid，如果valid就append到StringBuilder。
从左到右一次，从右到 ...

但是这样的话，一开始的从左到右append会将一些invalid的右括号也添加进来。这样的话在从右向左去除invalid的右括号的时候如果从stringBuilder的中间去除的话每一次去除都是O（n）的操作。

补充内容 (2017-11-25 05:14):
而如果从左向右只append左括号的话，在从右向左append右括号的时候，如果append在stringbuilder的中间，每次append都是O（n）的

去括号那道题是不是只用返回一个解就行啦？

楼主哪个学校的？

ARUI35 发表于 2017-11-25 05:13
但是这样的话，一开始的从左到右append会将一些invalid的右括号也添加进来。这样的话在从右向左去除inval ...

是啊，从左到右会append一些invalid左括号，但是所有的右括号都是valid的。这个for loop结束之后，更新原来的 s = sb.toString()。重新初始化 sb = new StringBuilder() 然后再对这个新的s从右到左append一次，最后reverse一下

AuroraKK 发表于 2017-11-25 07:06
去括号那道题是不是只用返回一个解就行啦？

是的 字数字数。。