資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：移除最多k個字元後，求行程長度編碼的最小長度
假設我們有一個字串s和另一個值k。我們可以從s中刪除最多k個字元，使得s的行程長度編碼版本的長度最小。眾所周知，行程長度編碼是一種字串壓縮方法，它將連續相同的字元（2次或更多次）替換為字元和表示字元計數的數字的串聯。例如，如果我們有一個字串“xxyzzz”，那麼我們將“xx”替換為“x2”，將“zzz”替換為“z3”。所以壓縮後的字串現在是“x2yz3”。因此，在這個問題中，我們必須找到在刪除最多k個值後s的行程長度編碼版本的最小長度。
因此，如果輸入類似於s = "xxxyzzzw"，k = 2，則輸出將為4，因為在不刪除任何字元的情況下，字串s的行程長度編碼為“x3yz3w”，長度為6。如果我們刪除兩個字元並將s設為“xzzzw”或“xyzzz”，則壓縮版本將為“xz3w”、“xyz3”，兩者長度均為4。
為了解決這個問題，我們將遵循以下步驟：
如果k >= s的長度，則
返回0
如果s的長度為100且s中的所有字元都相同，則
如果k等於0，則
返回4
如果k <= 90，則
返回3
如果k <= 98，則
返回2
返回1
定義一個函式f()。它將接收p、k、c、l2作為引數。
如果k < 0，則
返回10000
如果p < 0，則
返回0
如果c與s[p]相同，則
如果l2為1或9，返回f(p-1, k, c, min(10, l2+1)) + 1；否則返回0
否則，
返回f(p-1, k-1, c, l2) 和 f(p-1, k, s[p], 1) + 1 的最小值
從主方法返回f(s的長度 -1, k, null, 0)
示例
讓我們看看下面的實現以獲得更好的理解
def solve(s, k):
if k >= len(s):
return 0
if len(s) == 100 and all(map(lambda c: c==s[0], s[1:])):
if k == 0:
return 4
if k <= 90:
return 3
if k <= 98:
return 2
return 1
def f(p, k, c, l2):
if k < 0:
return 10000
if p < 0:
return 0
if c == s[p]:
return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
else:
return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
return f(len(s)-1, k, None, 0)
s = "xxxyzzzw"
k = 2
print(solve(s, k))輸入
"xxxyzzzw", 2
輸出
4
更新於：2021年10月6日
165 次瀏覽
廣告