FB 电面跪经

hello_ · 2017-10-18 07:04:52

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

FB电面，两三周之前面的，隔了三天催来了据信。

题目就是remove invalid parentheses, 但是只需要返回最少删除括号的个数。我第一反应是用stack，但是不确定怎么证明正确性（很怕他问到了没办

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

不说一上来就给最优解法，还得是各方面最优的花式解法。题目不难，怪自己那时候刷题刷的不到位，跪的心服口服。

sq6ra · 2017-10-19 22:33:51

lz其实用BFS是可以的，要求删除最少的括号，那么BFS时在树某一层找到合适解了，那么应该在此层，停止判读此层以下的子树层

hello_ · 2017-10-20 00:57:42

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

SXY123 · 2017-10-20 02:47:37

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

sq6ra · 2017-10-20 21:29:49

SXY123 发表于 2017-10-20 02:47
public int method(String s) {
char [] temp = s.toCharArray();
int count1 = 0, cou ...

这个是个什么解？返回的int是？

SXY123 · 2017-10-20 22:43:07

sq6ra 发表于 2017-10-20 21:29
这个是个什么解？返回的int是？

最少需要删除多少个括号

sixuan1991 · 2017-10-22 05:35:55

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

lightwindy

sixuan1991 发表于 2017-10-22 05:35
public int calculateMaxRemoval(String s) {
int removeL = 0;
int removeR = 0;

是的，这个解法好。

lyyy7537721825

今天onsite也面了这题。最后写的是先计算开括号需要删除的个数，然后在计算比括号需要删除的个数，然后往前扫去掉闭括号，往后再扫一次去掉开括号。
感觉不是很好。
目测挂了，大家加油。