Google 电面 挂

5222464 发表于 2022-07-10 20:53:55
------------------------------
实战例子
（（）））（（）（（）

哈哈哈哈 对哦 那改一下 case

）（（（
这类的 按照全部（处理一下 flip+删除

ND0406 发表于 2022-7-10 22:00
哈哈哈哈 对哦 那改一下 case

）（（（

所以按照我写的逻辑，左右2个删掉，最后flip一个，共3步

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

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

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

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

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

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

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

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

这题和Pramp上那个括号题很像， stack 是正常思路，可以用，但是其实应该不需要 stack来浪费这个O（N）的空间。直接result = 0， “（” 就  + 1， “）”就 - 1，主要思路差不多这路数，细节可以再去扣。

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

else if( c == '('){

1. public String minToMakeValid(String S) {
   
2.         int n = S.length();
   
3.         int[] change = new int[n];
   
4.         int openRight = 0, openLeft = 0;
   
5.         char[] input = S.toCharArray();
   
6.         int lastOpenRight = 0;
   
7.         int firstOpenLeft = 0;
   
8.         for (int i = 0; i < n; i++) {
   
9.             char c = input[i];
   
10.             if (c == '(') {
    
11.                 openLeft++;
    
12.             }else {
    
13.                 openLeft--;
    
14.             }
    
15.             if (openLeft < 0) {
    
16.                 openLeft = 0;
    
17.                 openRight++;
    
18.                 if (openRight % 2 == 1) {
    
19.                     change[i] = 1; // change to "(
    
20.                 }
    
21.                 lastOpenRight = i;
    
22.             }
    
23.         }
    
24.         if (openRight % 2 != 0) {
    
25.             change[lastOpenRight] = 2; // mark for delete
    
26.         }
    
27.         int minSteps = openLeft / 2 + openRight /2 + (openLeft % 2 == 0 ? 0 : 1) + (openRight % 2 == 0 ? 0 : 1);
    
28.         openLeft = openRight = 0;
    
29.         for (int i = n - 1; i >= 0; i--) {
    
30.             char c = input[i];
    
31.             if (c == ')') {
    
32.                 openRight++;
    
33.             }else {
    
34.                 openRight--;
    
35.             }
    
36.             if (openRight < 0) {
    
37.                 openRight = 0;
    
38.                 openLeft++;
    
39.                 if (openLeft % 2 == 1) {
    
40.                     change[i] = -1; // change to ")
    
41.                 }
    
42.                 firstOpenLeft = i;
    
43.             }
    
44.         }
    
45.         if (openLeft% 2 != 0) {
    
46.             change[firstOpenLeft] = 2; // mark for delete
    
47.         }
    
48. 
    
49.         StringBuilder res = new StringBuilder();
    
50.         for(int i = 0,j = 0, k = 0; i < n; i++) {
    
51.             if (change[i] == 0) {
    
52.                 res.append(S.charAt(i));
    
53.             }else if (change[i] == 1 ) {
    
54.                 res.append("(");
    
55.             } else if (change[i] == -1){
    
56.                 res.append(")");
    
57.             }
    
58.         }
    
59.         return res.toString();
    
60.     }

复制代码

已米，请问下delete add 和flip都算一次操作吗？还是flip算2次操作？

neverlate 发表于 2022-7-11 23:25
已米，请问下delete add 和flip都算一次操作吗？还是flip算2次操作？

算一次，最后要返回valid结果