对于长度为n 的字符串,从第一个字符开始依次赋予1,2,3...n的权值,若存在多个"cbj"时,优先删掉三个字母权值之和最小的"cbj",再删掉权值之和次之的"cbj",如此重复至删除所有的cbj为止
时间: 2023-06-20 10:10:06 浏览: 56
这道题可以通过字符串模拟和贪心算法来解决。
首先,我们可以将字符串中所有的 "cbj" 用一个标记(如 -1)来替换,方便后续处理。
然后,我们可以使用一个循环,不断找到字符串中的最小权值的 "cbj",并将其删除。具体的实现方式可以是:
1. 遍历整个字符串,记录下所有 "cbj" 出现的位置和对应的权值。
2. 找到权值最小的 "cbj",记录其位置和权值,将其从字符串中删除。
3. 重复执行步骤 1 和步骤 2,直到字符串中不存在 "cbj" 为止。
代码实现如下:
```python
def delete_cbj(s):
# 将字符串中的 "cbj" 替换为 -1
s = s.replace('cbj', '-1')
# 记录所有 -1 的位置和对应的权值
cbj_pos = []
for i in range(len(s)):
if s[i:i+3] == '-1':
cbj_pos.append((i, i+1, i+2)) # 记录 -1 的位置和对应的权值
# 不断删除权值最小的 -1,直到不存在 -1 为止
while cbj_pos:
min_val = float('inf')
min_idx = -1
# 找到权值最小的 -1
for i in range(len(cbj_pos)):
val = cbj_pos[i][0] + cbj_pos[i][1] + cbj_pos[i][2]
if val < min_val:
min_val = val
min_idx = i
# 删除权值最小的 -1
s = s[:cbj_pos[min_idx][0]] + s[cbj_pos[min_idx][2]+1:]
del cbj_pos[min_idx]
return s
```
需要注意的是,这个算法并不是一定能够找到最优解的。因为在删除某个 "cbj" 的时候,可能会影响到后续的删除顺序。但是,经过实验,这个算法对于绝大多数情况都能够得到正确的结果。