NG 🐶 OA 不是地里原题？？

倒序浏览 · 2021-9-15 05:40:54

看地理都说是原题

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

55

波风水门

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

匿名用户-NSC48 *2021-9-16 10:10:45* · 2021-9-16 10:10:45

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

july2020

o(n) python版本

def find_min_cost(s: str):
n = len(s)
res = n # worst case cost
count_b = [0] * (n + 1) # index from 1 to n
for i in range(n):
count_b[i + 1] = count_b[i] + (1 if s[i] == "b" else 0)
# delete until i, j from left and right side
# not including i, j
# ans will be i + n - 1 - j + (count_b[j+1] - count_b[i]) * 2
# easy to have O(n*n) algorithm
# for i in range(n):
# for j in range(i, n):
# res = min(res, i + n - 1 - j + (count_b[j + 1] - count_b[i]) * 2)
# as we find it's like preSum, for each j we only need to find minimum f[i] = i - count_b[i] * 2
min_i = 1 << 31
for j in range(n):
min_i = min(min_i, j - count_b[j] * 2)
res = min(res, n - 1 - j + count_b[j + 1] * 2 + min_i)
return res

复制代码

voidgear

提示: 作者被禁止或删除内容自动屏蔽

crdbuddy

这题怎么解？
想了好久没头绪。
有点像greedy，但是具体怎么做

焦浮

求思路555

onerhao

暴力bfs可行？

hellokk404

我觉得可以从左边开始数第一次b连续出现几个，然后计算从头移除和插入移除的损耗。

一直循环到没有b为止

匿名用户-YINVT *2021-9-15 10:14:58* · 2021-9-15 10:14:58

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

匿名用户-RWLGI *2021-9-15 10:19:10* · 2021-9-15 10:19:10

cccccBECX 发表于 2021-9-14 22:14
dp 去做
dp 表示 remove i j 的最小值
求 dp时 Iterate over k from i to j.

N是10的5次方

jwkilltheshit

昨晚上还是原题今天刚换的吗==

匿名用户-YINVT *2021-9-15 10:22:28* · 2021-9-15 10:22:28

匿名者发表于 2021-9-14 22:19
N是10的5次方

那感觉必是linear?