本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3597. 分割字符串 - 力扣（LeetCode）
解题思路
哈希表实现，按题意进行模拟即可
示例代码
python
class Solution:
def partitionString(self, s: str) -> List[str]:
vis = set()
tmp = ''
ans = []
for c in s:
tmp += c
if tmp not in vis:
vis.add(tmp)
ans.append(tmp)
tmp = ''
return ans3598. 相邻字符串之间的最长公共前缀 - 力扣（LeetCode）
解题思路
前后缀分解，随后枚举每个字符串，然后计算前一字符串和后一字符串的 lcp 即可
示例代码
python
class Solution:
def longestCommonPrefix(self, words: List[str]) -> List[int]:
n = len(words)
pre = [0] * (n + 1)
suf = [0] * (n + 1)
def cal(s, t):
for i in range(min(len(s), len(t))):
if s[i] != t[i]:
return i
return min(len(s), len(t))
memo = {}
for i in range(n - 1):
s, t = words[i], words[i + 1]
tmp = cal(s, t)
pre[i + 1] = max(pre[i], tmp)
memo[(s, t)] = tmp
for i in range(n - 2, -1, -1):
s, t = words[i], words[i + 1]
tmp = cal(s, t) if (s, t) not in memo else memo[(s, t)]
suf[i] = max(suf[i + 1], tmp)
ans = [0] * n
for i, word in enumerate(words):
tmp = 0
if i and i < n - 1:
tmp = cal(words[i - 1], words[i + 1])
ans[i] = max(tmp, pre[i - 1], suf[i + 1])
return ans3599. 划分数组得到最小 XOR - 力扣（LeetCode）
解题思路
二分查找，通过 dfs 判断是否能够构成 k 段异或和小于 m 的区间段
示例代码
python
class Solution:
def minXor(self, nums: List[int], k: int) -> int:
n = len(nums)
pre = [0] * (n + 1)
for i, x in enumerate(nums):
pre[i + 1] = pre[i] ^ x
@cache
def dfs(i, t, x):
if i == n or t == 0:
return True if i == n and t == 0 else False
for j in range(i, n - t + 1):
if pre[j + 1] ^ pre[i] <= x and dfs(j + 1, t - 1, x):
return True
return False
l = 0
r = (1 < max(nums).bit_length()) - 1
while l <= r:
m = (l + r) >> 1
flag = dfs(0, k, m)
if flag:
r = m - 1
else:
l = m + 1
return lpython
min = lambda a, b: b if b < a else a
max = lambda a, b: b if b > a else a
class Solution:
def minXor(self, nums: List[int], k: int) -> int:
n = len(nums)
f = [[inf] * (n + 1) for _ in range(k + 1)]
f[0][0] = 0
for i in range(1, k + 1):
for j in range(i, n - (k - i) + 1):
s = 0
for l in range(j - 1, i - 2, -1):
s ^= nums[l]
f[i][j] = min(f[i][j], max(f[i - 1][l], s))
return f[k][n]3600. 升级后最大生成树稳定性 - 力扣（LeetCode）
解题思路
贪心，并查集，用并查集保存生成树，然后用堆选择最适强度，进行增强
注意联通块判断，可以写在板子里，懒得改板子了，直接用 cnt 进行统计
示例代码
python
class Solution:
def maxStability(self, n: int, edges: List[List[int]], k: int) -> int:
uf = UnionFind(n)
h = []
res = []
ans = inf
cnt = n
for u, v, s, ms in edges:
if ms:
if uf.connected(u, v):
return -1
uf.union_rank(u, v)
ans = min(ans, s)
cnt -= 1
else:
heappush(h, (-s, u, v))
while h:
s, u, v = heappop(h)
s = -s
if uf.connected(u, v):
continue
uf.union_rank(u, v)
if s < ans:
res.append(s)
cnt -= 1
if cnt != 1:
return -1
if res:
res.sort()
for i in range(min(k, len(res))):
res[i] *= 2
return min(ans, min(res))
return anspy
class UnionFind:
def __init__(self, n: int) -> None:
self.n = n
self.parent = list(range(n))
self.rank = [1] * n
self.size = [1] * n
def find(self, x: int) -> int:
if self.parent[x] == x:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union_by_size(self, x: int, y: int) -> None:
x_root, y_root = self.find(x), self.find(y)
if x_root != y_root:
if self.size[y_root] <= self.size[x_root]:
self.parent[y_root] = x_root
self.size[x_root] += self.size[y_root]
else:
self.parent[x_root] = y_root
self.size[y_root] += self.size[x_root]
def union_rank(self, x: int, y: int) -> None:
x_root, y_root = self.find(x), self.find(y)
if x_root != y_root:
if self.rank[y_root] <= self.rank[x_root]:
self.parent[y_root] = x_root
else:
self.parent[x_root] = y_root
if self.rank[x_root] == self.rank[y_root]:
self.rank[x_root] += 1
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)