比赛详情
- 题目一很简单
- 题目二主要是题目长了点，其实解法很常规(比赛后才意识到)
- 题目三套用Dijkstra算法
- 题目四没时间解答水平还有待提升(其实就是需要灵活组合运用已知的算法，有点类似大模型的Agent)
题解和思路
第一题：最小数字游戏
class Solution:
def numberGame(self, nums: List[int]) -> List[int]:
nums.sort()
arr = []
# 每一轮中，Alice 先移除最小元素，然后 Bob 移除最小元素
while nums:
# Alice 移除最小元素
alice_num = nums.pop(0) if nums else None
# Bob 移除最小元素
bob_num = nums.pop(0) if nums else None
# Bob 先将他的元素添加到 arr
if bob_num is not None:
arr.append(bob_num)
# 然后 Alice 添加她的元素
if alice_num is not None:
arr.append(alice_num)
return arr第二题：移除栅栏得到的正方形田地的最大面积
把横纵所有的长度存进set，再遍历两个set，相等的话再和之前的最大面积比较
from typing import List
class Solution:
def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
mod = 10 ** 9 + 7
def getGaps(fences, size):
fences = sorted([1] + fences + [size]) # Include start and end fence positions.
combinations = set()
for i in range(len(fences)):
for j in range(i):
combinations.add(fences[i] - fences[j]) # Calculate gaps directly.
return combinations
hGaps = getGaps(hFences, m)
vGaps = getGaps(vFences, n)
ans = -1
for gap in hGaps:
if gap in vGaps:
ans = max(ans, gap ** 2)
return -1 if ans == -1 else ans % mod第三题：转换字符串的最小成本 I
import heapq
from typing import List
from collections import defaultdict
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
# 构建图
graph = defaultdict(dict)
for o, c, co in zip(original, changed, cost):
if c not in graph[o] or graph[o][c] > co:
graph[o][c] = co
# 缓存用于存储已计算的转换成本
cost_cache = {}
# Dijkstra 算法
def dijkstra(src, tgt):
if src == tgt:
return 0
if (src, tgt) in cost_cache:
return cost_cache[(src, tgt)]
visited = set()
min_heap = [(0, src)] # (cost, node)
while min_heap:
curr_cost, curr_node = heapq.heappop(min_heap)
if curr_node in visited:
continue
visited.add(curr_node)
if curr_node == tgt:
cost_cache[(src, tgt)] = curr_cost
return curr_cost
for neighbor, edge_cost in graph[curr_node].items():
if neighbor not in visited:
heapq.heappush(min_heap, (curr_cost + edge_cost, neighbor))
cost_cache[(src, tgt)] = float('inf')
return float('inf')
# 计算总成本
total_cost = 0
for s, t in zip(source, target):
cost = dijkstra(s, t)
if cost == float('inf'):
return -1
total_cost += cost
return total_cost
第四题：转换字符串的最小成本 II
这道题目的总体思路是解决一个字符串替换问题，其中目标是找出将给定的源字符串 source 转换为目标字符串 target 的最小成本。解决这个问题的方法涉及几个关键步骤：
-
字符串编码：使用 Trie 树来处理字符串集合。Trie 树是一种有效的数据结构，用于存储和检索字符串集合。在这个场景中，每个节点代表一个字符，路径从根到特定节点表示一个字符串。通过这种方式，可以为
original和changed数组中的每个字符串分配一个唯一的数字标识符。 -
构建图并计算最短路径：在 Trie 树的帮助下，为每一对原始和更改后的字符串建立一个有向图，并将转换成本作为边的权重。使用 Dijkstra 算法来计算图中任意两点之间的最短路径，这是为了找出将任意
original字符串替换为任意changed字符串的最小成本。 -
动态规划（DFS）：通过动态规划来确定将
source转换为target的最小总成本。这一步涉及到递归地检查每个字符和每个可能的字符串替换，来计算不同替换方案的累积成本。动态规划通过记忆化（缓存中间结果）来提高效率，避免重复计算相同的子问题。 -
处理特殊情况：代码中还需要处理一些特殊情况，如当
source和target在某个位置上的字符已经相等时，无需进行替换。
总体而言，这个问题的解决方案是一个综合应用 Trie 树、图论（特别是最短路径算法）和动态规划的复杂算法。它需要精确地处理字符串之间的关系和转换成本，以找出将一个字符串转换为另一个字符串的最小成本路径。
import heapq
from typing import List
# TrieNode 是 Trie 树的节点，每个节点存储了指向其子节点的引用和该节点所表示字符串的唯一标识符（sid）
class TrieNode:
def __init__(self):
# 存储 26 个字母的子节
self.children = [None] * 26
# 字符串的唯一标识符
self.sid = -1
# Trie 类是用于存储字符串集合的 Trie 树的实现。它提供了 put 方法来将字符串添加到 Trie 树中，并分配或检索字符串的唯一标识符。
class Trie:
def __init__(self):
# Trie 树的根节点
self.root = TrieNode()
# 用于给新字符串分配唯一标识符
self.sid = 0
def put(self, s):
# 将字符串 `s` 添加到 Trie 树中，并返回其唯一标识符
# 如果字符串已存在，则返回其现有标识符
node = self.root
for ch in s:
index = ord(ch) - ord('a')
if not node.children[index]:
node.children[index] = TrieNode()
node = node.children[index]
if node.sid < 0:
node.sid = self.sid
self.sid += 1
return node.sid
class Dijkstra:
def __init__(self, size):
# 图中节点的数量
self.size = size
# 图的邻接表表示
self.graph = [[] for _ in range(size)]
def add_edge(self, u, v, weight):
# 向图中添加一条边从 `u` 到 `v`，权重为 `weight`
self.graph[u].append((v, weight))
def shortest_path(self, start):
distances = [float('inf')] * self.size
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in self.graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
class Solution:
# 计算将字符串 `source` 转换为 `target` 的最小成本
# 使用 Trie 树来存储 `original` 和 `changed` 中的字符串及其唯一标识符
# 使用 Dijkstra 算法计算字符串之间的最短转换路径
# 使用动态规划（通过 `dfs` 函数）来寻找最小成本的转换序列
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
inf = 1e13
trie = Trie()
m = len(cost)
# 初始化 Dijkstra 算法
dijkstra_solver = Dijkstra(m * 2)
for i, c in enumerate(cost):
x = trie.put(original[i])
y = trie.put(changed[i])
dijkstra_solver.add_edge(x, y,
min(c, dijkstra_solver.graph[x][y] if y in dijkstra_solver.graph[x] else inf))
# 计算最短路径
shortest_paths = [dijkstra_solver.shortest_path(i) for i in range(trie.sid)]
# 动态规划
n = len(source)
memo = [-1] * n
# dfs 是一个辅助递归函数，用于动态规划。它计算从当前索引 i 开始，
# 将 source 的剩余部分转换为 target 的最小成本。
def dfs(i):
# 递归函数，用于计算将 source[i:] 转换为 target[i:] 的最小成本
if i >= n:
return 0 # 递归边界：当 i 超过 source 的长度时，返回 0
if memo[i] != -1:
return memo[i] # 如果当前索引的结果已经被计算过，则直接返回
res = inf # 初始化当前索引的最小成本为无穷大
if source[i] == target[i]:
res = dfs(i + 1) # 如果当前字符相同，无需替换，直接计算下一个字符的成本
p, q = trie.root, trie.root # 初始化两个 Trie 指针，分别用于遍历 source 和 target
# 尝试替换 source 中从索引 i 开始的所有可能的子串
for j in range(i, n):
index_p = ord(source[j]) - ord('a') # 计算 source[j] 在 Trie 中的索引
index_q = ord(target[j]) - ord('a') # 计算 target[j] 在 Trie 中的索引
p = p.children[index_p] if p else None # 获取source[j] 在 Trie 中的节点
q = q.children[index_q] if q else None # 获取target[j] 在 Trie 中的节点
if p is None or q is None:
break # 如果任一指针到达 Trie 的末端，表示前缀树中无法找到于source[i:j]或target[i:j]相匹配的字符串终止接下来的寻找
if p.sid >= 0 and q.sid >= 0:
# 如果当前子串在 original 和 changed 中都存在，则计算替换成本
# 将当前子串替换成目标子串的成本加上剩余子串转换的成本
res = min(res, shortest_paths[p.sid][q.sid] + dfs(j + 1))
memo[i] = res # 将结果存储在 memo 中，避免重复计算
return res
ans = dfs(0)
return -1 if ans >= inf else int(ans)
# 示例使用
sol = Solution()
print(sol.minimumCost("abcd", "acbe", ["a", "b", "c", "c", "e", "d"], ["b", "c", "b", "e", "b", "e"],
[2, 5, 5, 1, 2, 20]))
下面展示了不用前缀树的写法会超时：
import heapq
from typing import List
class Dijkstra:
def __init__(self, size):
self.size = size
self.graph = [[] for _ in range(size)]
def add_edge(self, u, v, weight):
self.graph[u].append((v, weight))
def shortest_path(self, start):
distances = [float('inf')] * self.size
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in self.graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
class Solution:
def minimumCost(self, source: str, target: str, original: List[str], changed: List[str], cost: List[int]) -> int:
inf = 1e13
string_to_id = {}
id_counter = 0
def get_id(s: str) -> int:
nonlocal id_counter
if s not in string_to_id:
string_to_id[s] = id_counter
id_counter += 1
return string_to_id[s]
m = len(original)
dijkstra_solver = Dijkstra(m * 2)
for i, c in enumerate(cost):
x = get_id(original[i])
y = get_id(changed[i])
dijkstra_solver.add_edge(x, y, min(c, dijkstra_solver.graph[x][y] if y in dijkstra_solver.graph[x] else inf))
shortest_paths = [dijkstra_solver.shortest_path(i) for i in range(id_counter)]
n = len(source)
memo = [-1] * n
def dfs(i):
if i >= n:
return 0
if memo[i] != -1:
return memo[i]
res = inf
if source[i] == target[i]:
res = dfs(i + 1)
for j in range(i, n):
src_substring = source[i:j+1]
tgt_substring = target[i:j+1]
if src_substring in string_to_id and tgt_substring in string_to_id:
src_id = string_to_id[src_substring]
tgt_id = string_to_id[tgt_substring]
res = min(res, shortest_paths[src_id][tgt_id] + dfs(j + 1))
memo[i] = res
return res
ans = dfs(0)
return -1 if ans >= inf else int(ans)