資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢避免重複字母的最小刪除成本
假設我們有一個字串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
- 對於範圍從1到s大小減1的i，執行：
- 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
- 如果c_cost >= p_cost，則：
- 否則：
- prev_i := 0, cost_i := 0
- ind := 0
- 返回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
更新於：2021年10月4日
614 次瀏覽
廣告