LeetCode Weekly Contest 173 题解
2020 年的开头没有那么美好。因为众所周知的原因，这几天只能在家待着，躺尸几天后感觉实在太无聊了，因此是时候开始更新博客了。目前的计划是每天更新一下做题记录和古典音乐推荐，那么今天就从做题记录开始吧。
这是 LeetCode 上的第 173 场周赛（链接）。
1332. 删除回文子序列（Remove Palindromic Subsequences）
题目大意是，给出一个只包含 a 和 b 的字符串，每次可以删除一个回文子序列，问最少需要删除多少次可以删完整个字符串。题目中的两个关键概念如下：
- 「回文」我们都知道，即一个字符串向后和向前读是一致的。
- 「子序列」则指的是：通过删除原字符串某些字符而不改变原字符顺序得到的字符串。注意，和「子串」的区别是，子串必须是连起来的，而子序列则不必。
这道题看似是一道字符串处理题，其实是一道有趣的智力题。注意到，字符串只包含 a 和 b，那我们可以断定任何一个串都最多只需要 2 步就能删完。因此只需判断输入是否是回文串即可。
class Solution:
def removePalindromeSub(self, s: str) -> int:
if len(s) == 0:
return 0
if s == s[::-1]: # 原字符串为回文串
return 1
return 2
1333. 餐厅过滤器（Filter Restaurants by Vegan-Friendly, Price and Distance）
思路很简单的一道题，根据给的过滤条件筛选出符合条件的餐厅 id，并按照评分和 id 排序。
这道题让我想起了 n 年前在网吧做过的一道题，和这道题的解法完全相同，基本上难点就在于自己写一个 cmp 函数。
class Solution:
def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]:
ans = []
if veganFriendly == 1: # 判断素食友好
for r in restaurants:
if r[2] == veganFriendly:
ans.append(r)
else:
ans = restaurants[:]
ans = [i for i in ans if i[3] <= maxPrice and i[4] <= maxDistance] # 根据价格和距离过滤
ans.sort(key=lambda x: (x[1], x[0]), reverse=True) # 按照评分和id降序排序
return [i[0] for i in ans]
1334. 阈值距离内邻居最少的城市（Find the City With the Smallest Number of Neighbors at a Threshold Distance）
已知一张图，给定一个阈值，统计每个结点的距离不超过阈值的邻居数，找出拥有最小数值的结点。
这是一道裸的 Dijkstra 算法的题，对于一个月前刚刚考完图论的我，本应该是小菜一碟……然而真实情况好像并非如此。理解算法和能熟练用代码实现确实还是不一样，这算是一次很好的实践。
简单复习一下用来求单源最短路的 Dijkstra 算法：
已知包含每两个结点之间的权重的整个图的权重矩阵 cost，我们想要知道其余结点到结点 i 的最短路径长度。使用 shortestPath 代表距离结点 i 的最短距离数组，即 shortestPath[j] 代表结点 j 与结点 i 的最短距离（j 不等于 i）。算法如下：
- 开始时设置 shortestPath[j] = float(‘inf’) （j 不等于i），shortestPath[i] = 0。用数组 visited 记录是否已经找到了从结点 i 到结点 k 的最短路径。即如果 visited[k] == 1，则表示已经找到了从结点 i 到结点 k 的最短路径；如果 visted[k] == 0 则表示还没有。
- 开始循环，在每一次迭代中，我们从没有得到最短路径（即 not visted）的结点中找 shortestPath[v] 最小的，设置 visited[v] = 1。然后，对每一个结点的最短距离进行更新，即「松弛」操作。继续循环。
- 如果所有结点都已经 visted，跳出循环。数组 shortestPath 就是 Dijkstra 算法的结果, shortestPath[v] 代表从城市 i 到城市 v 的最短距离。
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
G = [[float('inf') for _ in range(n)] for _ in range(n)]
min_count = n
ans = -1
for e in edges:
G[e[0]][e[1]] = e[2]
G[e[1]][e[0]] = e[2]
for i in range(n):
path = self.Dijkstra(G, i, n)
temp = 0
for p in path:
if p <= distanceThreshold:
temp += 1
if temp <= min_count:
min_count = temp
ans = i
return ans
def Dijkstra(self, cost, start_point, n):
shortestPath = [float('inf') for _ in range(n)]
shortestPath[start_point] = 0
visited = [0 for _ in range(n)]
while True:
v = -1
for i in range(n): # 找到目前最短距离结点
if visited[i] == 0 and (v == -1 or shortestPath[i] < shortestPath[v]):
v = i
if v == -1: # 所有结点都已访问，跳出循环
break
visited[v] = 1
for i in range(n):
shortestPath[i] = min(shortestPath[i], shortestPath[v] + cost[v][i]) # 松弛
return shortestPath
1335. 工作计划的最低难度（Minimum Difficulty of a Job Schedule）
问题是，将一个数组划分为 d 段，使得每段（即每段中数字最大值）之和最小。（后文称这个最小和为代价）
这道题的解法是动态规划，动态规划的难点在于构造初始条件和转移方程。
-
使用 dp[i][j] 来表示到「将数组下表为从 0..j 的部分划分为 i+1 段的代价」（i 和 j 都从0开始，即 i+1 天内完成 j+1 个任务）。
-
为了计算 dp[i][j] （即前 i+1 天完成前 j+1 项任务所需的代价），我们把问题分解，变为前 i 天（下标为0, …, i-1）完成前 k 项任务（下标为0, …, k-1），和第 i+1 天（下标为i）完成下标为 k, …, j 的任务。显然这里 k >= i，因为每天至少要完成一个任务。于是，我们只要遍历所有可能的 k，取最小值能得到 dp[i][j]，转移方程为：
(i <= k <= j)
- 最后，初始条件是，第一天处理下标为 0..k 的任务（0 <= k < n-d+1）时的代价 dp[0][k]。
代码如下：
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if n < d:
return -1
dp = [[float('inf') for _ in range(n)] for _ in range(d)]
premax = 0
# 初始化，计算第一天的代价
for i in range(0, n-d+1):
premax = max(premax, jobDifficulty[i])
dp[0][i] = premax
for i in range(1, d): # 第下标i天
for j in range(i, n): # 处理到下标为j的任务
premax = 0
for k in range(j, i-1, -1): # 遍历所有可能的k
premax = max(premax, jobDifficulty[k]) # 计算下表k..j段的任务最大值
dp[i][j] = min(dp[i][j], dp[i-1][k-1] + premax)
return dp[d-1][n-1]
有什么想法，留个评论吧：