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);elsenotVowel++;if (foundVowels.size() == 5 && notVowel == k)count++;}}return count;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n²)，其中 n 是字符串 word 的长度。

空间复杂度：O(1)。

题目3：3306. 元音辅音字符串计数 II

思路

问题等价于如下两个问题：

• 每个元音字母至少出现一次，并且至少包含 k 个辅音字母的子串个数。记作 f_k。
• 每个元音字母至少出现一次，并且至少包含 k+1 个辅音字母的子串个数。记作 f_k+1。

二者相减，所表达的含义就是恰好包含 k 个辅音字母了，所以答案为 f_k - f_k+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]++;elsecnt2++;while (cnt1.size() == 5 && cnt2 >= k){char out = word[left];if (vowels.count(out)){if (--cnt1[out] == 0)cnt1.erase(out);}elsecnt2--;left++;}ans += left;}return ans;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 word 的长度。

空间复杂度：O(1) 或者 O(∣Σ∣)，其中 ∣Σ∣=21。

题目4：3307. 找出第 K 个字符 II

思路

倒序遍历 operations。当 k 在字符串的右半边，也就是 k>2ⁱ 时，把 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)。