查找Python中有损运行长度编码的最小长度的程序
假设我们有一个小写的字符串s和另一个值k。现在考虑一个操作，在该操作中，我们通过将重复的连续字符作为计数和字符对字符串执行行程编码。因此，如果字符串像“aaabbc”，则将被编码为“3a2bc”。这里我们不将“1c”替换为“c”，因为它仅连续出现一次。因此，我们可以先删除s中的任何k个连续字符，然后找到结果游程长度编码的最小可能长度。
因此，如果输入像s=“xxxxxyyxxxxxzzxxx”，k=2，则输出将为6，因为两个明显的选择是删除“yy”或“zz”。如果删除“yy”，则将得到长度为7的“10x2z3x”。如果删除“zz”，则将得到长度为6的“5x2y8x”，这是最小的。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数calc_cost()。这需要l
如果l等于0，则
返回0
如果l与1相同
返回1
除此以外，
str(l)+1的返回大小
定义一个功能prefix()。这将花费
如果c与最后一个相同，则
除此以外，
最后：=c
在pre中插入一个对（pre的最后一项的第0个元素，1+pre的最后一项的第1元素）
将（pre的最后一项的第0个元素）+calc_cost（pre的最后一项的第1元素，1）插入pre
pre：=最初带有对[0，0]的列表
最后：=null
对于s中的每个c
返回预
从主要方法执行以下操作：
pre：=前缀
suf：=前缀的反向（以相反的顺序）
ans：=无限
对于范围0到s-k+1的i
成本：=成本+calc_cost(midl)+calc_cost(midr)
成本：=成本+calc_cost（midl+midr）
j：=i+k
对（左，中）：=pre[i]
对（右，中）：=suf[j]
费用：=左+右
c1：=s[i-1]如果i>0否则为null
c2：=s[j]如果j<s的大小，否则为null
如果c1与c2相同，则
除此以外，
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