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);elsenotVowel++;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]++;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>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)。