資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：尋找有損遊程長度編碼的最小長度
假設我們有一個小寫字串s和另一個值k。現在考慮一個操作，我們對字串執行遊程長度編碼，將重複的連續字元作為計數和字元。所以如果字串是“aaabbc”，則編碼為“3a2bc”。這裡我們不為“c”放置“1c”，因為它只連續出現一次。所以我們可以先移除s中任何k個連續字元，然後找到結果遊程長度編碼的最小可能長度。
因此，如果輸入類似於s = "xxxxxyyxxxxxzzxxx"，k = 2，則輸出為6，因為兩個明顯的選擇是刪除“yy”或“zz”。如果我們刪除“yy”，我們將得到“10x2z3x”，長度為7。如果我們刪除“zz”，我們將得到“5x2y8x”，長度為6，這是最小的。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式`calc_cost()`。這將接受l
如果l等於0，則
返回0
如果l等於1，則
返回1
否則，
返回str(l)的長度 + 1
定義一個函式`prefix()`。這將接受s
pre := 一個最初包含對[0, 0]的列表
last := null
對於s中的每個c，執行：
如果c等於last，則
將一對(pre的最後一項的第0個元素，1 + pre的最後一項的第1個元素)插入到pre中
否則，
將(pre的最後一項的第0個元素) + calc_cost(pre的最後一項的第1個元素, 1) 插入到pre中
last := c
返回pre
從主方法執行以下操作：
pre := prefix(s)
suf := prefix(反轉的s)的反轉
ans := 無窮大
對於範圍0到s的長度 - k + 1中的每個i，執行：
j := i + k
對(left, midl) := pre[i]
對(right, midr) := suf[j]
cost := left + right
c1 := s[i - 1] 如果i > 0 否則為 null
c2 := s[j] 如果j < s的長度 否則為 null
如果c1等於c2，則
cost := cost + calc_cost(midl + midr)
否則，
cost := cost + calc_cost(midl) + calc_cost(midr)
ans := ans和cost的最小值
返回ans
讓我們看看下面的實現，以便更好地理解：
示例
def calc_cost(l):
if l == 0:
return 0
if l == 1:
return 1
else:
return len(str(l)) + 1
class Solution:
def solve(self, s, k):
def prefix(s):
pre = [[0, 0]]
last = None
for c in s:
if c == last:
pre.append([pre[-1][0], pre[-1][1] + 1])
else:
pre.append([pre[-1][0] + calc_cost(pre[-1][1]),1])
last = c
return pre
pre = prefix(s)
suf = prefix(s[::-1])[::-1]
ans = float("inf")
for i in range(len(s) - k + 1):
j = i + k
left, midl = pre[i]
right, midr = suf[j]
cost = left + right
c1 = s[i - 1] if i > 0 else None
c2 = s[j] if j < len(s) else None
if c1 == c2:
cost += calc_cost(midl + midr)
else:
cost += calc_cost(midl) + calc_cost(midr)
ans = min(ans, cost)
return ans
ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2))輸入
s = "xxxxxyyxxxxxzzxxx"
輸出
6
202 次瀏覽
