用 Python 编写程序，查找最小删除成本以避免重复字母
pythonserver side programmingprogramming更新于 2025/11/26 10:20:17
假设我们有一个字符串 s 和另一个名为 cost 的整数数组，其中 cost[i] 表示删除 s 中第 i 个字符的成本。我们必须找到最小的删除成本，使得没有两个相同的字母相邻。我们必须记住，我们将同时删除选定的字符。因此，删除一个字符后，删除其他字符的成本不会改变。
因此，如果输入为 s = "pptpp", cost = [2,3,4,5,2]，则输出将为 4，因为如果我们以成本 2+2 = 4 删除第一个和最后一个 p，则字符串将为 "ptp"这里没有两个相同的字符一个接一个地出现
为了解决这个问题，我们将遵循以下步骤−
- cost_f := 0
- i := 1
- ind := 0
- 对于 i 在 1 到 s - 1 的大小范围内，执行
- cur := s[i], c_cost := cost[i]
- prev := s[i-1], p_cost := cost[i-1]
- 如果 ind 与 1 相同，则
- prev := prev_i, p_cost := cost_i
- 如果 cur 与 prev 相同，则
- 如果c_cost >= p_cost，则
- cost_f := cost_f + p_cost
- prev_i := 0，cost_i := 0
- ind := 0
- 如果 c_cost < p_cost，则
- cost_f := cost_f + c_cost
- ind := 1
- prev_i := prev，cost_i := p_cost
- 否则，
- prev_i := 0，cost_i := 0
- ind := 0
- 如果c_cost >= p_cost，则
- 返回 cost_f
示例
让我们看看以下实现以便更好地理解:
def solve(s, cost): cost_f = 0 i = 1 ind = 0 for i in range(1, len(s)): cur, c_cost = s[i], cost[i] prev, p_cost = s[i-1], cost[i-1] if ind == 1: prev, p_cost = prev_i, cost_i if cur == prev: if c_cost >= p_cost: cost_f += p_cost prev_i, cost_i = 0,0 ind = 0 if c_cost < p_cost: cost_f += c_cost ind = 1 prev_i, cost_i = prev, p_cost else: prev_i, cost_i = 0,0 ind = 0 return cost_f s = "pptpp" cost = [2,3,4,5,2] print(solve(s, cost))
输入
"pptpp", [2,3,4,5,2]
输出
4
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
