Leetcode 第 417 场周赛题解
Leetcode 第 417 场周赛题解
- Leetcode 第 417 场周赛题解
- 题目1:3304. 找出第 K 个字符 I
- 思路
- 代码
- 复杂度分析
- 题目2:3305. 元音辅音字符串计数 I
- 思路
- 代码
- 复杂度分析
- 题目3:3306. 元音辅音字符串计数 II
- 思路
- 代码
- 复杂度分析
- 题目4:3307. 找出第 K 个字符 II
- 思路
- 代码
- 复杂度分析
Leetcode 第 417 场周赛题解
题目1:3304. 找出第 K 个字符 I
思路
模拟字符串的构造。在执行足够多的操作后, word 中 至少 存在 k 个字符,此时返回 word 中第 k 个字符的值。
代码
/*
* @lc app=leetcode.cn id=3304 lang=cpp
*
* [3304] 找出第 K 个字符 I
*/
// @lc code=start
class Solution
{
public:
char kthCharacter(int k)
{
string s = "a";
while (s.length() < k)
{
int len = s.length();
for (int i = 0; i < len; i++)
s += s[i] + 1;
}
return s[k - 1];
}
};
// @lc code=end
复杂度分析
时间复杂度:O(logk)。
空间复杂度:O(1)。
题目2:3305. 元音辅音字符串计数 I
思路
利用滑动窗口取区间为 [left, right] 的 word 的子字符串,判断其是否每个元音字母(‘a’、‘e’、‘i’、‘o’、‘u’)至少出现一次,并且恰好包含 k 个辅音字母。
代码
/*
* @lc app=leetcode.cn id=3305 lang=cpp
*
* [3305] 元音辅音字符串计数 I
*/
// @lc code=start
class Solution
{
public:
int countOfSubstrings(string word, int k)
{
int n = word.length();
unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
int count = 0;
for (int left = 0; left + 5 + k <= n; left++)
{
int notVowel = 0;
unordered_set<char> foundVowels; // 存放当前找到的元音字母
for (int right = left; right < n; right++)
{
char c = word[right];
if (vowels.count(c))
foundVowels.insert(c);
else
notVowel++;
if (foundVowels.size() == 5 && notVowel == k)
count++;
}
}
return count;
}
};
// @lc code=end
复杂度分析
时间复杂度:O(n2),其中 n 是字符串 word 的长度。
空间复杂度:O(1)。
题目3:3306. 元音辅音字符串计数 II
思路
问题等价于如下两个问题:
- 每个元音字母至少出现一次,并且至少包含 k 个辅音字母的子串个数。记作 fk。
- 每个元音字母至少出现一次,并且至少包含 k+1 个辅音字母的子串个数。记作 fk+1。
二者相减,所表达的含义就是恰好包含 k 个辅音字母了,所以答案为 fk - fk+1。
代码
/*
* @lc app=leetcode.cn id=3306 lang=cpp
*
* [3306] 元音辅音字符串计数 II
*/
// @lc code=start
class Solution
{
private:
const unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
public:
long long countOfSubstrings(string word, int k)
{
return f(word, k) - f(word, k + 1);
}
// 辅函数
long long f(string &word, int k)
{
long long ans = 0;
// 这里用哈希表实现,替换成数组会更快
unordered_map<char, int> cnt1; // 每种元音的个数
int cnt2 = 0; // 辅音个数
int left = 0;
for (char &c : word)
{
if (vowels.count(c))
cnt1[c]++;
else
cnt2++;
while (cnt1.size() == 5 && cnt2 >= k)
{
char out = word[left];
if (vowels.count(out))
{
if (--cnt1[out] == 0)
cnt1.erase(out);
}
else
cnt2--;
left++;
}
ans += left;
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度:O(n),其中 n 是字符串 word 的长度。
空间复杂度:O(1) 或者 O(∣Σ∣),其中 ∣Σ∣=21。
题目4:3307. 找出第 K 个字符 II
思路
倒序遍历 operations。当 k 在字符串的右半边,也就是 k>2i 时,把 inc 增加 operations[i]。
代码
/*
* @lc app=leetcode.cn id=3307 lang=cpp
*
* [3307] 找出第 K 个字符 II
*/
// @lc code=start
class Solution
{
public:
char kthCharacter(long long k, vector<int> &operations)
{
int inc = 0;
for (int i = __lg(k - 1); i >= 0; i--)
{
if (k > (1LL << i))
{
// k 在右半边
inc += operations[i];
k -= (1LL << i);
}
}
return 'a' + inc % 26;
}
};
// @lc code=end
复杂度分析
时间复杂度:O(logk)。
空间复杂度:O(1)。