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]