上岸算法LeetCode Weekly Contest 282解题报告

【 NO.1 统计包含给定前缀的字符串】

解题思路

签到题,枚举即可。

代码展示

【 NO.2 使两字符串互为字母异位词的最少步骤数】

解题思路

字母异位词 (anagram) 只需要满足各种字符的数量一致即可,所以统计两个字符串中,每种字母的出现次数,将少的补充直到达到数量相同即可。

代码展示

【 NO.3 完成旅途的最少时间】

解题思路

典型的二分答案题目。

代码展示

【 NO.4 完成比赛的最少时间】

解题思路

动态规划问题。

先预处理求出 g[i] 表示不换轮胎完成 i 圈的最短时间,枚举所有的轮胎即可。

然后定义状态 f[i] 表示完成 i 圈的最短时间,状态转移方程即 f[i] = min{ f[i - j] + g[j] + changeTime }

注意最终答案要减去多加的一次 changeTime, 以及运算过程中的溢出问题。

由数据范围可知,最终答案一定不会超过 1e5 * 1000 * 2 (每次都换胎),该数值未超过 int 最大值,所以运算过程溢出的状态可以直接丢弃。