查找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