NG 🐶 OA 不是地里原题？？

匿名者 发表于 2021-9-15 21:38
写了一个解放 根据前面一个大佬的思路 测了一些testcase 都能过， 大家觉得有用或者正确的赏点米吧， 最近 ...

亲，你一开始建立的arr是用来做什么的呀

波风水门 发表于 2021-9-14 22:55
O(n^2) 的方法容易想，因为最后删除的方式一定是【删除一个前缀】+【删除一个后缀】+【中间部分删除所有的  ...

分析得太棒了！一看就懂了

mattJK 发表于 2021-9-16 14:49
周二做的 拿到了一样的题...= =

请问层主是什么时候收到OA的？

匿名者 发表于 2021-9-14 19:37
aababbbaaaaaaaa 这个case貌似不行

请问这个case的答案是多少呢

o(n) python版本

1. def find_min_cost(s: str):
   
2.     n = len(s)
   
3.     res = n  # worst case cost
   
4.     count_b = [0] * (n + 1)  # index from 1 to n
   
5.     for i in range(n):
   
6.         count_b[i + 1] = count_b[i] + (1 if s[i] == "b" else 0)
   
7. 
   
8.     # delete until i, j  from left and right side
   
9.     # not including i, j
   
10.     # ans will be i + n - 1 - j + (count_b[j+1] - count_b[i]) * 2
    
11.     # easy to have O(n*n) algorithm
    
12.     # for i in range(n):
    
13.     #     for j in range(i, n):
    
14.     #         res = min(res, i + n - 1 - j + (count_b[j + 1] - count_b[i]) * 2)
    
15.     # as we find it's like preSum, for each j we only need to find minimum f[i] = i - count_b[i] * 2
    
16.     min_i = 1 << 31
    
17.     for j in range(n):
    
18.         min_i = min(min_i, j - count_b[j] * 2)
    
19.         res = min(res, n - 1 - j + count_b[j + 1] * 2 + min_i)
    
20.     return res

复制代码

匿名者 发表于 2021-9-16 19:16
亲，你一开始建立的arr是用来做什么的呀

ignore  那个吧。没用的 忘记删了

DAI_KINMind 发表于 2021-9-17 02:25
请问层主是什么时候收到OA的？

也是周二当天收到的

DAI_KINMind 发表于 2021-9-17 02:40
请问这个case的答案是多少呢

答案是7吗啊啊啊啊

匿名者 发表于 2021-9-17 13:41
ignore  那个吧。没用的 忘记删了

朋友你后来能过所有testcase嘛

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

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