2022 亚麻 OA1 新题最全截图

谢谢楼主分享，祝好运！

请问楼主是ng吗？ 谢谢

坂口鱼 发表于 2022-1-27 23:49
请问楼主是ng吗？ 谢谢

是new grad的

第二题确实是最简单的bfs,但发现自己一时竟然写不出来

求问一下，第一题是什么思路啊

这个题目跟做题网二十有点像，但是string可以rearrange， 所以只需要记录各种字符的数量就可以了。
用这种方法可以在O(n)时间算出来从左到右，当前位置为止，是不是balanced。然后从右到左再算一次，最后合并一下。

代码没有优化，也没有足够的测试样例，不知道对不对，欢迎讨论

1. def balancedCount(s: str) -> int:
   
2.     inbalances = [0] * 2
   
3.     questions = 0
   
4.     lbalance = [False] * len(s)
   
5.     values = dict()
   
6.     values['['] = 1
   
7.     values[']'] = -1
   
8.     values['('] = 1
   
9.     values[')'] = -1
   
10.     for i in range(len(s)):
    
11.         c = s[i]
    
12.         if c in '[]':
    
13.             inbalances[0] += values[c]
    
14.         elif c in '()':
    
15.             inbalances[1] -= values[c]
    
16.         else:
    
17.             questions += 1
    
18.         lbalance[i] = True if abs(inbalances[0]) + abs(inbalances[1]) - questions == 0 else False
    
19. 
    
20.     questions = 0
    
21.     inbalances = [0] * 2
    
22.     rbalance = [False] * len(s)
    
23.     for i in range(len(s) - 1, -1, -1):
    
24. 
    
25.         c = s[i]
    
26.         if c in '[]':
    
27.             inbalances[0] += values[c]
    
28.         elif c in '()':
    
29.             inbalances[1] -= values[c]
    
30.         else:
    
31.             questions += 1
    
32.         rbalance[i] = True if abs(inbalances[0]) + abs(inbalances[1]) - questions == 0 else False
    
33. 
    
34.     ans = 0
    
35.     for i in range(len(s) - 1):
    
36.         if lbalance[i] and rbalance[i + 1]:
    
37.             ans += 1
    
38.     return ans

复制代码

PengChen0692 发表于 2022-4-9 07:56
这个题目跟做题网二十有点像，但是string可以rearrange， 所以只需要记录各种字符的数量就可以了。
用这种 ...

这个解法厉害了
我没想到要左右分别扫一次