LeetCode282周赛复盘

第一题

统计包含给定前缀的字符串

给你一个字符串数组 words 和一个字符串 pref 。

返回 words 中以 pref 作为 前缀 的字符串的数目。

字符串 s 的 前缀 就是 s 的任一前导连续字符串。

示例 1：

输入：words = [“pay”,“attention”,“practice”,“attend”], pref = “at” 输出：2

解释：以 “at” 作为前缀的字符串有两个，分别是：“attention” 和 “attend” 。

思路：

本题就是一个简单的for循环遍历，具体的流程博主也是相信各位小伙伴都是掌握的。

代码：

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        res = 0
        x = len(pref)
        for i in words:
            if len(i) >= x:
                if i[:x] == pref:
                    res += 1
        return res

第二题

使用两字符串互为字母异位词的最少步骤数

题目：

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5

输出：3

解释：

时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。

已完成的总旅途数为 1 + 0 + 0 = 1 。

时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。

已完成的总旅途数为 2 + 1 + 0 = 3 。

时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。

已完成的总旅途数为 3 + 1 + 1 = 5 。

所以总共完成至少 5 趟旅途的最少时间为 3 。

思路：

本题其实就是一个简单的hash表的问题，就是把两个字符中不同的字符个数和相同字符不同数量的字符个数相加即可求出本题。

由于时间问题本题博主没有优化，直接ac的也能过的。

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        res = 0
        dit1 = {}
        dit2 = {}
        for i in s:
            if i not in dit1:
                dit1[i] = 1
            else:
                dit1[i] += 1
        for j in t:
            if j not  in dit2:
                dit2[j] = 1
            else:
                dit2[j] += 1
        for i in dit1:
            if i not in dit2:
                res += dit1[i]
            elif dit1[i] != dit2[i]:
                res += abs(dit1[i] - dit2[i])
        for i in dit2:
            if i not in dit1:
                res += dit2[i]
        return  res

第三题

完成旅途的最少时间

题目：

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5

输出：3

解释：

时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。

已完成的总旅途数为 1 + 0 + 0 = 1 。

时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。

已完成的总旅途数为 2 + 1 + 0 = 3 。

时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。

已完成的总旅途数为 3 + 1 + 1 = 5 。

所以总共完成至少 5 趟旅途的最少时间为 3

思路：

本题是比较经典的二分查找。因为花费时间是不会超过min（time）*totalTrips，所以我们可以以其为右边界，以0为左边界，然后使用二分查找判断mid时间时完成的次数是大于还是小于totalTrips进行搜索。如果小于则会让左边界等于mid+1，反之右边界等于mid - 1。具体流程我们能看具体代码。

代码：

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        time.sort()
        l,r=0,time[0]*totalTrips
        while l<r:
            mid=1+(l+r)//2
            tmp=0
            for i in time:
                tmp+=mid//i
            if tmp<totalTrips:
                l=mid
            else:
                r=mid-1
        return l+1

总结

每次通过力扣的周赛都能对自己近一段的算法水平进行检验，通过这次周赛博主也能发现自己的查找算法是一个十分大的弱项。所以下一段时间准备去复习复习查找和排序这些经典算法了哈哈哈（毕竟这些都是面试常考的问题哦）。