阳江优化网站排名,怎么给自己网站做搜索框,seo搜索如何优化,网站推广目标关键词怎么选本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件则称其为 美丽字符串
vowels consonants即元音字母和辅音字母的数量相等。(vowels * consonants) % k 0即元音字母和辅音字母的数量的乘积能被 k 整除。
返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 a、e、i、o 和 u 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
示例 1
输入s baeyh, k 2
输出2
解释字符串 s 中有 2 个美丽子字符串。
- 子字符串 b_aeyh_vowels 2[a,e]consonants 2[y,h]。
可以看出字符串 aeyh 是美丽字符串因为 vowels consonants 且 vowels * consonants % k 0 。
- 子字符串 _baey_hvowels 2[a,e]consonants 2[b,y]。
可以看出字符串 baey 是美丽字符串因为 vowels consonants 且 vowels * consonants % k 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。示例 2
输入s abba, k 1
输出3
解释字符串 s 中有 3 个美丽子字符串。
- 子字符串 _ab_bavowels 1[a]consonants 1[b]。
- 子字符串 ab_ba_vowels 1[a]consonants 1[b]。
- 子字符串 _abba_vowels 2[a,a]consonants 2[b,b]。
可以证明字符串 s 中只有 3 个美丽子字符串。示例 3
输入s bcdf, k 1
输出0
解释字符串 s 中没有美丽子字符串。提示
1 s.length 5 * 10^41 k 1$0$s 仅由小写英文字母组成。 解法 分解质因子前缀和哈希表
把元音视作 1 1 1辅音视作 − 1 -1 −1 。「元音字母和辅音字母的数量相等」就等价于找到一个和为 0 0 0 的连续子数组。注意这种子数组的长度一定是偶数因为元音辅音数量相等。
设子数组的长度为 L L L 。由于元音辅音数量相等所以元音辅音数量都等于 L 2 \dfrac{L}{2} 2L 所以「元音字母和辅音字母的数量的乘积能被 k k k 整除」等价于 ( L 2 ) 2 m o d k 0 \left(\dfrac{L}{2}\right)^2 \bmod k 0 (2L)2modk0 这等价于 L 2 m o d ( 4 k ) 0 L^2 \bmod (4k) 0 L2mod(4k)0 这个平方很烦人如果能去掉平方就好做了。
这里得来点数学。我们来研究下如果一个数 L L L 的平方能被 n n n 整除意味着什么
假设 n n n 是一个质数例如 3 3 3那么 L L L 必须包含质因子 3 3 3 此时问题就变成了判断 L L L 能不能被 3 3 3 整除。我们把平方去掉了如果 n n n 是一个质数 $p 的 e e e 次幂呢分类讨论 如果 e e e是偶数比如 n 3 4 n3^4 n34 那么 L L L 必须包含因子 3 2 3^2 32 才能使得 L 2 L^2 L2 能被 n n n 整除。此时问题就变成了判断 L L L 能不能被 3 2 3^2 32 整除。如果 e e e 是奇数比如 n 3 5 n3^5 n35 那么 L L L 必须包含因子 3 3 3^3 33 才能使得 L 2 L^2 L2 能被 n n n 整除。此时问题就变成了判断 L L L 能不能被 3 3 3^3 33 整除。 所以 L L L 必须包含因子 p r p^r pr 其中 r ⌈ e 2 ⌉ ⌊ e 1 2 ⌋ r\left\lceil\dfrac{e}{2}\right\rceil \left\lfloor\dfrac{e1}{2}\right\rfloor r⌈2e⌉⌊2e1⌋ 。 如果 n n n 可以分解出多个质因子只需要把每个质因子及其幂次按照上面的方法处理然后再相乘就得到 L L L 必须包含什么因子。
继续 把 4 4 4 按照上述方法计算设 L L L 必须包含因子 k ′ k k′ 。现在问题变成有多少个和为 0 0 0 的子数组其长度是 k ′ k k′ 的倍数
设子数组的下标范围为 [ j , i ) [j,i) [j,i) 那么其长度 L i − j Li-j Li−j 则有 ( i − j ) m o d k ′ 0 (i-j)\bmod k 0 (i−j)modk′0 等价于 i m o d k ′ j m o d k ′ i \bmod k j\bmod k imodk′jmodk′ 对于元素和来说相当于 s [ i ] − s [ j ] 0 s[i]-s[j] 0 s[i]−s[j]0 即 s [ i ] s [ j ] s[i] s[j] s[i]s[j] 我们需要同时满足这两个条件下标模 k ′ k k′ 相等 s s s 值相等这可以一并用哈希表解决。哈希表的 k e y key key 是一个 p a i r pair pair ( i m o d k ′ , s [ i ] ) (i\bmod k, s[i]) (imodk′,s[i]) 哈希表的 v a l u e value value 是这个 p a i r pair pair 的出现次数。
代码实现时前缀和数组可以用一个变量表示。
代码实现时可以把 aeiou 压缩成一个二进制数从而快速判断字母是否为元音。 问为什么哈希表要在一开始插入一个 ( k ′ − 1 , 0 ) (k-1, 0) (k′−1,0) 答前缀和的第一项是 0 0 0由于代码中是从下标 0 0 0 开始算第二个前缀和所以相当于 s [ − 1 ] 0 s[−1]0 s[−1]0 而 k ′ − 1 k-1 k′−1 和 − 1 -1 −1 关于 k ′ k k′ 同余所以插入 ( k ′ − 1 , 0 ) (k′−1,0) (k′−1,0) 。 class Solution {
private:int pSqrt(int n) {int ans 1;for (int i 2; i * i n; i) {int i2 i * i;while (n % i2 0) { // 质因数分解ans * i; // L必须包含一个i^1n / i2;}if (n % i 0) { // 如果n包含某个质数的奇次幂ans * i;n / i;}}if (n 1) ans * n; // 剩下的最后1个质因子return ans;}struct PairHash {templatetypename T1, typename T2size_t operator() (const pairT1, T2 p) const {auto v1 std::hashT1{}(p.first);auto v2 std::hashT2{}(p.second);return v1 ^ v2;}};unordered_mappairint, int, int, PairHash cnt; //ok
public:int beautifulSubstrings(string s, int k) {k pSqrt(k * 4); // 4k的质因数分解求出L必须包含的因子值多个质因子的幂次的乘积const int aeiouMask 1065233;cnt[ pairint, int{ k - 1, 0} ] 1; // k-1和1同余int sum 0;int ans 0;for (int i 0; i s.size(); i) {char c s[i];int bit aeiouMask (c - a) 1;sum bit * 2 - 1; // 1-1, 0--1auto p pair{i % k, sum};ans (long long)cnt[p];cnt[p];}return ans;}
};复杂度分析
时间复杂度 O ( n k ) \mathcal{O}(n \sqrt k) O(nk ) 其中 n n n 为 nums \textit{nums} nums 的长度。空间复杂度 O ( n ) \mathcal{O}(n) O(n) 。
