用 Python 编写程序，查找有损游程编码的最小长度

pythonserver side programmingprogramming更新于 2026/1/24 1:48:17

假设我们有一个小写字符串 s 和另一个值 k。现在考虑一个操作，我们通过将重复的连续字符作为计数和字符对字符串执行游程编码。因此，如果字符串类似于"aaabbc"，则将被编码为"3a2bc"。这里我们不将"1c"替换为"c"，因为它只连续出现一次。因此，我们可以先删除 s 中的任何 k 个连续字符，然后找到生成的游程编码的最小可能长度。

因此，如果输入类似于 s = "xxxxyyxxxxxxzzxxx"，k = 2，则输出将为 6，因为两个明显的选择是删除"yy"或"zz"。如果我们删除"yy"，那么我们将得到长度为 7 的"10x2z3x"。如果我们删除"zz"，那么将得到长度为 6 的"5x2y8x"，这是最小的。

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 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 := reverse of prefix(s in reverse order)
ans := infinity
对于 i 在 0 到 s - k + 1 的大小范围内，执行
- j := i + k
- pair (left, midl) := pre[i]
- pair (right, midr) := suf[j]
- cost := left +正确
- 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))