脸家店面(来一个小众的地方，坐标欧洲)

坐标爱尔兰都柏林，new grad职位真的少的可怜。。一共内推了三个岗位，参加了两轮技术电面。

Timeline:
2.20 内推 Enterprise Engineer 简历没过
3.1 内推 Solution Engineer
3

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

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

用timeO(N)+space为O(1)的复杂度解出
4.27 拒信。。。整整两个周


求加米！！！！大米真的不够用

ddcfv 发表于 2020-5-26 15:07
衣耳丝就 怎么满足 O(1) space啊？

1. class Solution {
   
2.     public String minRemoveToMakeValid(String s) {
   
3.         char[] c=s.toCharArray();
   
4.         
   
5.         int left=0;//count 表示现在有多少个(多出来了
   
6.         for(int i=0;i<c.length;i++){
   
7.             if(c[i]=='(') left++;
   
8.             if(c[i]==')'){
   
9.                 if(left>0) left--;
   
10.                 else c[i]='*';
    
11.             }
    
12.         }
    
13.         int right=0;//count 表示现在有多少个(多出来了
    
14.         for(int i=c.length-1;i>=0;i--){
    
15.             if(c[i]==')') right++;
    
16.             if(c[i]=='('){
    
17.                 if(right>0) right--;
    
18.                 else c[i]='*';
    
19.             }
    
20.         }
    
21.         StringBuffer result=new StringBuffer();
    
22.         for(int i=0;i<c.length;i++){
    
23.             if(c[i]!='*')
    
24.                 result.append(c[i]);
    
25.         }
    
26.         return result.toString();
    
27.     }
    
28. }

复制代码

这是我当时写的答案，在原字符串上面修改，额外的空间只需要O(1), 面试官说可以。

空间O1的话这样行吗?

1. left, right = 0, 0
   
2. for c in s:
   
3.     if c == '(':
   
4.         left += 1
   
5.     elif c == ')':
   
6.         if left == 0:
   
7.             right += 1
   
8.         else:
   
9.             left -= 1
   
10. return left + right

复制代码

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

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

xie xie fen xiang

衣伞久不是用dp做的吗？为啥复杂度变2**n了？

兄弟你咋跑爱尔兰去了。

请问楼主~申爱尔兰cs硕士 留欧洲找工作不打算回国了 可行性高么？本来是想去美国的 不知道要不要改变计划

衣耳丝就 怎么满足 O(1) space啊？

关于时间复杂度的解释：        
N是s的字符个数， O(2^N) 时间复杂度分析
T(N)=T(N-1)+T(N-2)+..+T(1)+T(0)=O(2^N)
详细见：https://leetcode.com/problems/wo ... -Method-Should-Be-O(2n)-and-Prove-It-Below

manmande 发表于 2020/05/18 02:08:51
请问楼主~申爱尔兰cs硕士 留欧洲找工作不打算回国了 可行性高么？本来是想去美国的 不知道要不要改变计划

请看我最新的帖子，里面分析了很多。