算法题记录 27

3305.元音辅音字符串计数1（1564）

给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（’a’、’e’、’i’、’o’、’u’）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

涉及知识点

滑动窗口

解决思路

一看难度1564，默认送分题，结果做着发现不对劲，是要求子字符串的总数，这就涉及到滑动窗口了。实际该题难度为2200，但是抄答案提交的人太多，变成了1564。总的思路跟经典的滑动窗口相似，但是我们注意有个k，在滑动窗口中我们令辅音字母出现次数大于等于k，方便滑动。事后用f(k)减去f(k+1)即可。

class Solution:
    def f(self, word: str, k: int) -> int:
        cnt1 = defaultdict(int)  # 每种元音的个数
        ans = cnt2 = left = 0  # cnt2 维护辅音个数
        for b in word:
            if b in "aeiou":
                cnt1[b] += 1
            else:
                cnt2 += 1
            while len(cnt1) == 5 and cnt2 >= k:
                out = word[left]
                if out in "aeiou":
                    cnt1[out] -= 1
                    if cnt1[out] == 0:
                        del cnt1[out]
                else:
                    cnt2 -= 1
                left += 1
            ans += left
        return ans

    def countOfSubstrings(self, word: str, k: int) -> int:
        return self.f(word, k) - self.f(word, k + 1)

3165.不包含相邻元素的子序列的最大和（2698）

给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi]。

对于每个查询 i，首先将 nums[posi] 设置为 xi，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素 的 子序列 的 最大 和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 109 + 7 取余 的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

涉及知识点

线段树、分治

解决思路

相当有难度，原本打算用传统的动态规划不停更新做的，但是发现情况很复杂要分类讨论。具体问题在于，我们对nums下标i更新时，会更新答案数组i之后的所有值。我们把前面的记为a，后面要更新的记为b，如果我们选了a的最后一个数，b的第一个就不能选了，反之亦然。这里要分类讨论计算一次，而a和b怎么算呢？又要分开讨论，第一个选不选、最后一个选不选，一直迭代下去便完成了分治。该题需要多看看、多做做。

class Solution:
    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        # 4 个数分别保存 f00, f01, f10, f11
        t = [[0] * 4 for _ in range(2 << n.bit_length())]

        # 手写 max，效率更高
        def max(a: int, b: int) -> int:
            return b if b > a else a

        # 合并左右儿子
        def maintain(o: int):
            a, b = t[o * 2], t[o * 2 + 1]
            t[o][0] = max(a[0] + b[2], a[1] + b[0])
            t[o][1] = max(a[0] + b[3], a[1] + b[1])
            t[o][2] = max(a[2] + b[2], a[3] + b[0])
            t[o][3] = max(a[2] + b[3], a[3] + b[1])

        # 用 nums 初始化线段树
        def build(o: int, l: int, r: int) -> None:
            if l == r:
                t[o][3] = max(nums[l], 0)
                return
            m = (l + r) // 2
            build(o * 2, l, m)
            build(o * 2 + 1, m + 1, r)
            maintain(o)

        # 把 nums[i] 改成 val
        def update(o: int, l: int, r: int, i: int, val: int) -> None:
            if l == r:
                t[o][3] = max(val, 0)
                return
            m = (l + r) // 2
            if i <= m:
                update(o * 2, l, m, i, val)
            else:
                update(o * 2 + 1, m + 1, r, i, val)
            maintain(o)

        build(1, 0, n - 1)

        ans = 0
        for i, x in queries:
            update(1, 0, n - 1, i, x)
            ans += t[1][3]  # 注意 f11 没有任何限制，也就是整个数组的打家劫舍
        return ans % 1_000_000_007

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。