leetcode 周赛 491

零、背景

这次比赛最后一题其实不难，但我敲错了一个地方，调试半天，没能进入前百名，有点遗憾。

本场题型概览如下。
A 题：模拟。
B 题：动态规划。
C 题：二进制贪心。
D 题：最大最小滑动窗口。

最终排名：109。
代码仓库：详见 https://github.com/tiankonguse/leetcode-solutions。

一、移除尾部元音字母

题意：给一个字符串，移除尾部元音字母。

思路：按题意从后到前判断即可。

二、拆分到 1 的最小总代价

题意：给一个整数，求拆分为 n 个 1 的最小总代价。
拆分规则：如果一个数 n 可以拆分为 a 和 b，使得 n=a+b，则拆分代价为 a*b。

思路：动态规划。

一个整数 n 共有 n/2 种拆分方式（a 从 1 到 n/2，b=n-a）。
由于拆分是递归的，不知道哪种拆分方式最优，所以需要枚举所有拆分方式。
显然，拆分方式包含子问题，故可以使用动态规划，记录计算过的子问题答案，避免重复运算。

复杂度：O(n^2)

三、按位或的最小值

题意：给一个 n*m 的矩阵，每一行恰好选择一个数字，使得所有选择的数字按位或的值最小。

思路：二进制贪心。

显然，如果可以使得最高位为 0，就不可能选择那些最高位为 1 的数字。
因此，可以从高到低枚举每一位，判断是否能让当前位为 0。
若可以，就将当前位为 1 的数字都删除。
否则，不管怎么选择这一位都是 1，不需要删除任何数字。

小技巧 1：可以将要删除的数字移动到数组末尾，然后 pop_back 删除。
小技巧 2：可以将要删除的数字改为特殊值，不删除，读取时做特殊判断。

复杂度：O(n*m log(n*m))

四、统计包含 K 个不同整数的子数组

题意：给一个数组，统计包含 K 个不同整数且每个数字至少出现 m 次的子数组数量。

思路：最大最小滑动窗口。

对于统计子数组数量的问题，通常枚举一个边界，然后统计另一个边界满足要求的数量。
因此，枚举左边界后，需要找到满足条件的最小右边界与最大右边界，二者之差就是子数组数量。

对某个固定边界的计算，复杂度显然是 O(n) 的。
但可以利用滑动窗口复用上一个位置的计算结果，从而使得每个边界的复杂度均摊为 O(1)。

由于需要维护两个滑动窗口，可以封装为一个类。

对于最小滑动窗口：当不同数字不足 K，或不同数字恰好为 K 但出现次数达到 m 的数字个数不足 K 时，才能继续移动右边界。
对于最大滑动窗口：直接移动到不同数字首次超过 K 的位置。

但有一个特殊情况：可能以当前左端点为起点的所有后缀都满足条件，此时不存在“不同数字超过 K”的位置，需要额外做一次特殊判断。

五、最后

这次比赛最后一题挺有意思的，使用两个滑动窗口来解决子数组数量问题，又学到新知识了。

《完》。

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code