第二题是301, hard,店面也这么难?
哦对,经典题了,很高频的。dfs扫两遍。从左到右,然后从右往左。bfs的不让过的。
这题面FB必须准备到的。感觉标题换了就有点认不出来了, 直接说是 Remove Invalid Parentheses 估计马上反应过来了。
您好,想请问一下,为什么 “(()))sdf”会转变成 “sdf”呀? 不应该是(())sdf吗?ps:祝顺利,加油!
应该是搞错了
ok thx~
这题只要找到一个解,用bfs似乎好一些
public static String balanceParens(String s) {
StringBuffer res = new StringBuffer();
int l = 0, r = 0;//num of invalid left and right
for (char c : s.toCharArray()) {
l += c == '(' ? 1 : 0;
if (l == 0) {
r += c == ')' ? 1 : 0;
} else {
l -= c == ')' ? 1 : 0;
}
}
Queue<ParenWraper> q = new LinkedList<>();
Set<String> used = new HashSet<>();
q.offer(new ParenWraper(s, l, r));
while (!q.isEmpty()) {
ParenWraper cur = q.poll();
if (isValid(cur.str)) {
return cur.str;
}
for (int i = 0; i < cur.str.length(); i++) {
if (cur.str.charAt(i) != '(' && cur.str.charAt(i) != ')') continue;
if (cur.str.charAt(i) == '(' && cur.left > 0) {
String temp = cur.str.substring(0, i) + cur.str.substring(i + 1);
if (!used.contains(temp)) {
used.add(temp);
q.offer(new ParenWraper(temp, cur.left - 1, cur.right));
}
}
if (cur.str.charAt(i) == ')' && cur.right > 0) {
String temp = cur.str.substring(0, i) + cur.str.substring(i + 1);
if (!used.contains(temp)) {
used.add(temp);
q.offer(new ParenWraper(temp, cur.left, cur.right - 1));
}
}
}
}
return "";
}
private static boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') count++;
else if (c == ')') count--;
if (count < 0) return false;
}
return count == 0;
}
1 Like
哦,只要一个解啊,那bfs可行
bfs 的效率还是没有dfs 高的,无论runtime还是space
dfs能不能找到一个解就退出呢?
我bfs稍微优化了一下,不过复杂度也是没有dfs好
嗯,还是dfs吧。面试的时间有限
当然可以
对 其实有点变种 主要还是以我写的为主 不是leetcode原题
但是代码没有写完 会不会是个大问题?
是大问题
现在看第二题其实是原题,而且是高频题,叫法改了下有点坑爹(check a string to see if it’s balanced) 。这么看第二题没准备到是准备不充分啊。另外你是否用了dfs。没用的话确实凉凉了。
这第二题几乎是考FB必须要准备的高频题之一。
楼主有结果吗?
反正我只需要把他给我的test case给写过就可以了呗,其他的一时半会也想不全
想出多个test case也是面试的考察点,这个很重要
remove invalid 括号的问题,能不能用stack遍历一遍,标记出有问题的括号(孤独的右括号或者最后栈里的左括号) 然后移除他们?
目测可行,你写个代码测一下就知道了