周赛250922

小号第一次AK， 题比较简单。

3295. 举报垃圾信息

题目大意

给定两个字符串数组 message 和 bannedWords，你需要判断 message 是否属于“垃圾信息”。如果 message 中至少有两个单词出现在 bannedWords 中，则该数组被视为垃圾信息，返回 true；否则返回 false。

实现思路

  1. 集合操作优化：为了快速判断 message 中的单词是否在 bannedWords 中，将 bannedWords 转换为一个 set 集合，利用集合的 O(1) 时间复杂度来快速查找单词是否存在。
  2. 统计匹配次数：遍历 message 数组，对每个单词检查它是否在 bannedWords 集合中，记录出现在 bannedWords 中的单词数。
  3. 判断垃圾信息：若匹配到的单词数量大于等于 2，则返回 true（即认为 message 是垃圾信息）；否则返回 false。
class Solution:
    def reportSpam(self, message: List[str], bannedWords: List[str]) -> bool:
        bannedWords = set(bannedWords)
        return sum(m in bannedWords for m in message) >= 2

Q2. 移山所需的最少秒数

题目大意

给定一个整数 mountainHeight 表示山的高度和一个数组 workerTimes，表示工人们降低山高度所需的工作时间。工人们可以同时工作，每个工人 i 在降低山的过程中，其降低 1 个高度需要 workerTimes[i] 秒，降低 2 个高度需要 workerTimes[i] + 2 * workerTimes[i] 秒，以此类推。题目要求返回工人们将山的高度降低到 0 所需的最少秒数。

实现思路

  1. 工人的工作能力：工人 i 降低 x 的高度需要的时间是 workerTimes[i] * (1 + 2 + ... + x)，即等差数列求和公式。根据时间 t，工人 i 能降低的最大高度可以通过二分查找确定。
  2. 二分查找最小时间：我们可以通过二分法来确定最少需要的时间，设定一个时间范围 [0, 10^16]，每次取中间值 mid 作为当前时间，判断在这段时间内，所有工人能否把山降低到 0。我们使用一个 work 函数来计算工人在给定时间内可以降低的最大高度。
  3. 计算每个工人能降低的高度：对于每个工人，我们通过二分查找计算出当前时间内该工人能降低的最大高度，如果所有工人的总降低高度超过了山的高度，则说明当前时间 mid 可以满足需求，继续向更小的时间查找，否则向更大的时间查找。
  4. 最终结果：在二分法中找到的最小时间即为答案。
class Solution:
    def minNumberOfSeconds(self, m: int, w: List[int]) -> int:
        # 找到 当前的工作最大时间内 此工人能降低的最大高度
        def work(wt, t):
            lo, hi = 0, t
            while lo < hi:
                mid = (lo + hi + 1) // 2
                if wt * mid * (mid + 1) // 2 <= t:
                    lo = mid
                else:
                    hi = mid - 1
            return lo
        
        # 10^5 * (1 + 10^5) // 2 * 10 ^ 4 = 
        l, r = 0, 10**16
        # 二分答案
        while l < r:
            mid = (l + r) // 2
            tot = 0
            for wt in w:
                tot += work(wt, mid)
                if tot >= m:
                    break
            if tot >= m:
                r = mid
            else:
                l = mid + 1
        return l

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

题目大意

给定两个字符串 word1 和 word2，如果某个子字符串 x 的重新排列能够包含 word2 作为其前缀，那么这个子字符串是合法的。问题要求返回 word1 中合法子字符串的数目。

为了满足问题中的内存限制，要求实现一个线性复杂度的解法。

实现思路

  1. 前缀匹配和字符计数：
    • 为了判断一个子字符串的重新排列是否可以包含 word2 作为前缀，需要对 word2 中的字符进行统计。
    • 使用 Counter 对 word2 中每个字符出现的次数进行记录，并使用滑动窗口技术遍历 word1 的子字符串。
  2. 滑动窗口法：
    • 维护一个窗口，用来记录当前窗口内的字符计数，并在窗口移动的过程中检查当前窗口能否重新排列成 word2 的前缀。
    • 窗口通过左右指针扩展和收缩，每次遇到合法情况时，记录当前窗口能产生的合法子字符串的数量。
  3. 窗口内匹配字符数：
    • 定义变量 m，用于记录当前窗口内有多少字符已经完全匹配了 word2 中对应字符的数量。当 m 等于 word2 中不同字符的总数时，意味着当前窗口可以重新排列出 word2 的前缀。
  4. 具体步骤：
    • 初始化 word2 中字符的计数器 w2_cnt。
    • 使用滑动窗口遍历 word1，对每个窗口内的字符进行计数。如果某个字符的计数达到 word2 中相应字符的数量，增加匹配字符数 m。
    • 当 m 达到 word2 不同字符数的总数时，表示窗口中的子字符串可以包含 word2 作为前缀。
    • 每当窗口合法时，计算从当前窗口右边界开始到 word1 末尾的所有子字符串都可以被重新排列成合法子字符串。
class Solution:
    def validSubstringCount(self, w1: str, w2: str) -> int:
        w2_cnt = Counter(w2)
        res = 0
        win = Counter()
        
        m = 0 # the number of matched char
        
        l = 0
        for r in range(len(w1)):
            if w1[r] in w2_cnt:
                win[w1[r]] += 1
                if win[w1[r]] == w2_cnt[w1[r]]:
                    m += 1
            
            while m == len(w2_cnt):
                res += len(w1) - r # (len(w1) - (r + 1) + 1) 因为r是下标
                if w1[l] in w2_cnt:
                    if win[w1[l]] == w2_cnt[w1[l]]:
                        m -= 1
                    win[w1[l]] -= 1
                l += 1
        
        return res