本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
Q1. 到达每个位置的最小费用
解题思路
贪心算法，每次选择最小的花费即可
示例代码
python
class Solution:
def minCosts(self, cost: List[int]) -> List[int]:
for i in range(len(cost) - 1):
cost[i + 1] = min(cost[i], cost[i + 1])
return costQ2. 子字符串连接后的最长回文串 I
解题思路
枚举所有子串组合，判断是否是回文串
示例代码
python
class Solution:
def longestPalindrome(self, s: str, t: str) -> int:
ans = 0
n, m = len(s), len(t)
for i in range(n + 1):
for j in range(n - i + 1):
for k in range(m + 1):
for l in range(m - k + 1):
tmp = s[j: j + i] + t[l: l + k]
if tmp == tmp[::-1]:
ans = max(ans, len(tmp))
return ansQ3. 子字符串连接后的最长回文串 II
解题思路
最长公共前缀，加上最长回文子串的后缀最大值
示例代码
python
class Solution:
def zFunction(self, t: str) -> List[int]:
z = [0] * len(t)
l = r = 0
for i in range(1, len(t)):
if i <= r:
z[i] = min(z[i - l], r - i + 1)
while i + z[i] < len(t) and t[z[i]] == t[i + z[i]]:
l, r = i, i + z[i]
z[i] += 1
return z
def helper(self, s):
n = len(s)
ans = [0] * (n + 1)
valid = [[False] * n for _ in range(n)]
for i in range(n):
valid[i][i] = True
for i in range(n - 1):
if s[i] == s[i + 1]:
valid[i][i + 1] = True
for k in range(3, n + 1):
for l in range(n - k + 1):
r = l + k - 1
if s[l] == s[r] and valid[l + 1][r - 1]:
valid[l][r] = True
for l in range(n):
for r in range(l, n):
if valid[l][r]:
ans[l] = max(ans[l], r - l + 1)
return ans
def longestPalindrome(self, s: str, t: str) -> int:
n, m = len(s), len(t)
ans = 0
hs = self.helper(s)
ht = self.helper(t[::-1])
ns = s + '#' + t[::-1]
for i in range(n + 1):
z = self.zFunction(ns[i:])
for j in range(m):
v = z[n - i + j + 1]
ans = max(ans, v * 2 + hs[i + v])
ans = max(ans, v * 2 + ht[j + v])
return ansQ4. 使 K 个子数组内元素相等的最少操作数
解题思路
示例代码
python
class Solution:
def minOperations(self, nums: List[int], x: int, k: int) -> int:
n = len(nums)
cost = [inf] * n
dh = DualHeap(x // 2)
lsize = x // 2
rsize = x - lsize
s = 0
l = 0
for r, v in enumerate(nums):
dh.add(v)
s += v
if r - l + 1 > x:
dh.remove(nums[l])
s -= nums[l]
l += 1
if r - l + 1 == x:
mid = dh.large[0]
cost[r] = s - dh.sum_kth - mid * rsize + mid * lsize - dh.sum_kth
f = [0] * (n + 1)
for i in range(1, k + 1):
g = [inf] * (n + 1)
for j in range(x * i - 1, n):
g[j + 1] = min(g[j], f[j - x + 1] + cost[j])
f = g
return f[-1]py
from collections import Counter
from heapq import heappop, heappush
class DualHeap:
def __init__(self, k=0):
"""对顶堆，实时计算当前集合前k小的元素和(如果k设0,则保持平衡，0<=small-large<=1)。每个操作均摊时间复杂度O(lgn)，总体O(nlgn)。682ms"""
self.k = k # 如果k=0，表示保持两个堆一样大（0<=small-large<=1），此时-small[0]就是中位数
self.small = [] # 大顶堆存较小的k个数，注意py默认小顶堆，因此需要取反
self.large = [] # 小顶堆存较大的剩余数
self.delay_rm = Counter() # 延时删除标记
self.sum_kth = 0 # 前k小数字的和
self.small_size = 0
self.large_size = 0
def prune(self, h):
"""修剪h，使h堆顶的已标记删除元素全部弹出"""
delay_rm = self.delay_rm
p = -1 if h is self.small else 1
while h:
v = h[0] * p
if v in delay_rm:
delay_rm[v] -= 1
if not delay_rm[v]:
del delay_rm[v]
heappop(h)
else:
break
def make_balance(self):
"""调整small和large的大小，使small中达到k个（或清空large）"""
k = self.k or (self.small_size + self.large_size + 1) // 2 # 如果self.k是0，表示前后要balance
if self.small_size > k:
heappush(self.large, -self.small[0])
self.sum_kth += heappop(self.small) # 其实是-=负数
self.large_size += 1
self.small_size -= 1
self.prune(self.small)
elif self.small_size < k and self.large:
heappush(self.small, -self.large[0])
self.sum_kth += heappop(self.large)
self.small_size += 1
self.large_size -= 1
self.prune(self.large)
def add(self, v):
"""添加值v，判断需要加到哪个堆"""
small = self.small
if not small or v <= -small[0]:
heappush(small, -v)
self.sum_kth += v
self.small_size += 1
else:
heappush(self.large, v)
self.large_size += 1
self.make_balance()
def remove(self, v):
"""移除v，延时删除，但可以实时判断是否贡献了前k和"""
small, large = self.small, self.large
self.delay_rm[v] += 1
if large and v >= large[0]:
self.large_size -= 1
if v == large[0]:
self.prune(large)
else:
self.small_size -= 1
self.sum_kth -= v
if v == -small[0]:
self.prune(small)
self.make_balance()