数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：寻找有损游程长度编码的最小长度
假设我们有一个小写字符串s和另一个值k。现在考虑一个操作，我们对字符串执行游程长度编码，将重复的连续字符作为计数和字符。所以如果字符串是“aaabbc”，则编码为“3a2bc”。这里我们不为“c”放置“1c”，因为它只连续出现一次。所以我们可以先移除s中任何k个连续字符，然后找到结果游程长度编码的最小可能长度。
因此，如果输入类似于s = "xxxxxyyxxxxxzzxxx"，k = 2，则输出为6，因为两个明显的选择是删除“yy”或“zz”。如果我们删除“yy”，我们将得到“10x2z3x”，长度为7。如果我们删除“zz”，我们将得到“5x2y8x”，长度为6，这是最小的。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数`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 := prefix(反转的s)的反转
ans := 无穷大
对于范围0到s的长度 - k + 1中的每个i，执行：
j := i + k
对(left, midl) := pre[i]
对(right, midr) := suf[j]
cost := left + right
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))输入
s = "xxxxxyyxxxxxzzxxx"
输出
6
202 次浏览
