查找Python中有损运行长度编码的最小长度的程序

Z时代
2024-01-10
分类：综合

假设我们有一个小写的字符串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))