Google 电面挂

倒序浏览 · 2022-7-11 08:00:44

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

x

分享一个狗家店面挂经

给一个字符串，只包含'(', ')'，要求1

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

出来>_<求分享思路
求米看帖谢谢

Falldawn

本帖最后由 Falldawn 于 2022-7-11 16:38 编辑

输出最小步数得到的String，但是如果包涵其他字符则需要在else 上加上if
else if (c == ')' ){

else if( c == '('){

public String minToMakeValid(String S) {
int n = S.length();
int[] change = new int[n];
int openRight = 0, openLeft = 0;
char[] input = S.toCharArray();
int lastOpenRight = 0;
int firstOpenLeft = 0;
for (int i = 0; i < n; i++) {
char c = input[i];
if (c == '(') {
openLeft++;
}else {
openLeft--;
}
if (openLeft < 0) {
openLeft = 0;
openRight++;
if (openRight % 2 == 1) {
change[i] = 1; // change to "(
}
lastOpenRight = i;
}
}
if (openRight % 2 != 0) {
change[lastOpenRight] = 2; // mark for delete
}
int minSteps = openLeft / 2 + openRight /2 + (openLeft % 2 == 0 ? 0 : 1) + (openRight % 2 == 0 ? 0 : 1);
openLeft = openRight = 0;
for (int i = n - 1; i >= 0; i--) {
char c = input[i];
if (c == ')') {
openRight++;
}else {
openRight--;
}
if (openRight < 0) {
openRight = 0;
openLeft++;
if (openLeft % 2 == 1) {
change[i] = -1; // change to ")
}
firstOpenLeft = i;
}
}
if (openLeft% 2 != 0) {
change[firstOpenLeft] = 2; // mark for delete
}
StringBuilder res = new StringBuilder();
for(int i = 0,j = 0, k = 0; i < n; i++) {
if (change[i] == 0) {
res.append(S.charAt(i));
}else if (change[i] == 1 ) {
res.append("(");
} else if (change[i] == -1){
res.append(")");
}
}
return res.toString();
}

复制代码

ND0406

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

5222464

感觉有点像301啊不过不是完全一样 BFS应该可以的不知道有没有greedy的算法

5222464

可以不可以计算多少个invalid "(" 和invalid ")"，每两个")"或者两个"(" 都可以flip一次解决，最后最多剩下一个 ")" 和一个"("

ND0406

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

5222464

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

5222464

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

匿名用户-DGEAG *2022-7-11 11:59:09* · 2022-7-11 11:59:09

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

Falldawn

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

Falldawn

可以同时做一下921， 1249以及20，32，

Google 电面 挂