阅读 304

前端工程师的 LeetCode 之旅 -- 173周赛



01
1332.删除回文子序列



题目描述【Easy】


给你一个字符串 s,它仅由字符 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文子序列。
返回删除给定字符串所有字符(字符串为空)的最小删除次数。
【子序列】定义:如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到,那么这个字符串就是原字符串的一个子序列。
【回文】定义:如果一个字符串向后和向前读是一致的,那么这个字符串就是回文。



首先当 s 为回文字符串时,最少删除次数自然是1。

当 s 不为回文字符串时,这时就需要好好审题了,题目中对于【子序列】的定义是可以删除原字符串中的某些字符,那么对于任意长度的 s ,都可以通过删除所有 b,得到一个全是 a 的回文子序列。

那么 s 不为回文字符串时的最小删除次数就是2。




02
1333.餐厅过滤器




题目描述【Medium】


给你一个餐馆信息数组 restaurants,其中 restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。
其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false,如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆,为 false 则意味着可以包括任何餐馆。此外,我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器,它们分别考虑餐厅的价格因素和距离因素的最大值。
过滤后返回餐馆的 id,按照 rating 从高到低排序。如果 rating 相同,那么按 id 从高到底排序。简单起见, veganFriendlyi 和 veganFriendly 为 true 时取值为 1,为 false 时,取值为 0。



本道题主要考察以下两个知识点:

  • 数组的基本操作。

  • 多条件排序。

题目描述比较详细,仔细阅读即可得解。




03
阈值距离之内邻居最少的城市




题目描述【Medium】


有 n 个城市,按从 0 到 n-1 编号。给你一个边数组 edges,其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边,距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离最大为 distanceThreshold 的城市。如果有多个这样的城市,则返回编号最大的城市。
注意连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。



本道题主要考察图论相关的知识,题目中要求解出邻居最少的城市,那么就需要求出一个城市最多可以到达几个城市,最终转化为求解各个城市之间最短距离的问题。

本道题中的城市图结构属于无向正权图,所以可以选择弗洛伊德算法(Floyd-Warshall),也可以选择迪杰斯特拉算法(Dijkstra)。

这里选择实现相对比较简单的弗洛伊德算法。

首先需要利用一个二维数组来记录各个顶点之间的距离:

然后需要对该数组进行 i 次更新,找出 [j, k] 是否存在一条从 [j, i] 到 [i, k] 的最短路径:

最后再筛选出邻居最少的城市:




04
1335.工作计划的最低难度




题目描述【Hard】


你需要制定一份 d 天的工作计划表。工作之间存在依赖,要想执行第 i 项工作,你必须完成全部 j 项工作(0 <= j < i)。
你每天至少需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和,而这一天的工作难度是当天应该完成的工作的最大难度。给你一个整数数组 jobDifficulty 和一个整数 d ,分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的最小难度。如果无法制定工作计划,则返回-1。



解决本道题的重点在于理清楚 i 和 d 的关系。

第一种情况:i < d,无法制定工作计划,返回 -1。

第二种情况:i == d,只能每一天完成一项工作,那么最低难度为 i 项工作的难度之和。

第三种情况:i > d,以 i = [6,5,4,3,2,1],d = 2 为例,一共有以下5种安排方式。

  • [6],[5, 4, 3, 1]

  • [6, 5],[4, 3, 2, 1]

  • [6, 5, 4],[3, 2, 1]

  • [6, 5, 4, 3],[2, 1]

  • [6, 5, 4, 3, 2], [1]

那么对于任意 d 和 i (i > d),实际就是比较 d - 1 天的最小难度加上当前天的最大难度,一共有 i - d + 1 种可能(每天至少完成一项任务),那么递推公式为:

所以,本题是一道标准的动态规划题型,具体解题代码如下: