LeetCode 第416场周赛个人题解

目录

Q1. 举报垃圾信息

原题链接

思路分析

AC代码

Q2. 移山所需的最少秒数

原题链接

思路分析

AC代码

Q3. 统计重新排列后包含另一个字符串的子字符串数目 I

原题链接

思路分析

AC代码

Q4. 统计重新排列后包含另一个字符串的子字符串数目 II

原题链接

思路分析

AC代码

Q1. 举报垃圾信息

原题链接

Q1. 举报垃圾信息

思路分析

直接模拟

AC代码

class Solution:
    def reportSpam(self, message: List[str], bannedWords: List[str]) -> bool:
        st = set(bannedWords)
        res = 0
        for s in message:
            if s in st:
                res += 1
        return res >= 2

Q2. 移山所需的最少秒数

原题链接

Q2. 移山所需的最少秒数

思路分析

二分

显然具有单调性，给的时间越多，干的活越多

我们二分秒数

如何check？

通过二分能够得到每个人在 x 秒时限下能干的活

时间复杂度：O(logU n logU)

AC代码

st = [0]
N = 100_000
for i in range(1, N + 1):
    st.append(st[-1] + i)

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        workerTimes.sort()

        def check(m: int) -> bool:
            t = mountainHeight
            for x in workerTimes:
                b = m // x
                delta = bisect_right(st, b) - 1
                t -= delta
                if t <= 0:
                    return True
            return False

        lo, hi = 0, 10**18
        while lo < hi:
            x = (lo + hi) // 2
            if check(x): hi = x
            else: lo = x + 1
        return hi

Q3. 统计重新排列后包含另一个字符串的子字符串数目 I

原题链接

Q3. 统计重新排列后包含另一个字符串的子字符串数目 I

思路分析

见Q4

AC代码

class Solution:
    def validSubstringCount(self, s1: str, s2: str) -> int:
        cnt1 = [0] * 26
        cnt2 = [0] * 26
        b = ord('a')
        s1 = list(map(ord, s1))
        s2 = list(map(ord, s2))
        for x in s2:
            cnt2[x - b] += 1
        res = 0
        n = len(s1)
        i = j = 0
        m = sum(1 for x in cnt2 if x)
        while i < n:
            cnt1[s1[i] - b] += 1
            if cnt1[s1[i] - b] == cnt2[s1[i] - b]:
                m -= 1
            while m == 0:
                # res += 1
                if cnt1[s1[j] - b] == cnt2[s1[j] - b]:
                    m += 1
                cnt1[s1[j] - b] -= 1
                j += 1
            res += j
            i += 1
        return res

Q4. 统计重新排列后包含另一个字符串的子字符串数目 II

原题链接

Q4. 统计重新排列后包含另一个字符串的子字符串数目 II

思路分析

滑动窗口

单调性显然，固定右端点，合法左端点越靠左

维护一个滑窗[j, i]

当我们发现滑窗内包含了s2 的字符集合，我们右收缩 j

保证 [0, j - 1] - i  都 包含s2字符集合，那么每个 i 的贡献就是 j - 1 + 1 = j

AC代码

comb = cache(comb)
class Solution:
    def validSubstringCount(self, s1: str, s2: str) -> int:
        cnt1 = [0] * 26
        cnt2 = [0] * 26
        b = ord('a')
        s1 = list(map(ord, s1))
        s2 = list(map(ord, s2))
        for x in s2:
            cnt2[x - b] += 1
        res = 0
        n = len(s1)
        i = j = 0
        m = sum(1 for x in cnt2 if x)
        while i < n:
            cnt1[s1[i] - b] += 1
            if cnt1[s1[i] - b] == cnt2[s1[i] - b]:
                m -= 1
            while m == 0:
                # res += 1
                if cnt1[s1[j] - b] == cnt2[s1[j] - b]:
                    m += 1
                cnt1[s1[j] - b] -= 1
                j += 1
            res += j
            i += 1
        return res