【 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 最大值,所以运算过程溢出的状态可以直接丢弃。