Leetcode 第 390 场周赛题解
Leetcode 第 390 场周赛题解
题目1：3090. 每个字符最多出现两次的最长子字符串
思路
哈希 + 滑动窗口。
代码
/*
* @lc app=leetcode.cn id=3090 lang=cpp
*
* [3090] 每个字符最多出现两次的最长子字符串
*/
// @lc code=start
class Solution
{
public:
int maximumLengthSubstring(string s)
{
int n = s.length();
vector<int> cnt(26, 0);
int maxLen = 0;
bool flag = true;
for (int i = 0, j = 0; i < n; i++)
{
if (++cnt[s[i] - 'a'] >= 3)
flag = false;
while (j <= i && flag == false)
{
if (--cnt[s[j] - 'a'] == 2)
flag = true;
j++;
}
maxLen = max(maxLen, i - j + 1);
}
return maxLen;
}
};
// @lc code=end
复杂度分析
时间复杂度：O()。
空间复杂度：O()。
题目2：3091. 执行操作使数据元素之和大于等于 K
思路
假如有一个数 num，我们分别对它进行一次加一操作和复制操作：
- 先加一，再复制：总和为 2 * (num + 1) = 2 * num + 2
- 先复制，再加一：总和为 2 * num + 1
所以，相同操作次数下，先加一再复制能使总和最大。加一操作都应当在复制操作之前。
因为是先加一再复制，所以最终数组的数都相同。我们枚举这个数字 num（[1, k]）：
- 加一操作 add 进行了 num - 1 次。
- 复制操作 copy 进行了 ceil(1.0 * k / num) - 1 次。
最终答案为 min(add + copy)。
代码
/*
* @lc app=leetcode.cn id=3091 lang=cpp
*
* [3091] 执行操作使数据元素之和大于等于 K
*/
// @lc code=start
class Solution
{
public:
int minOperations(int k)
{
// 特判
if (k <= 1)
return 0;
int minOps = INT_MAX;
for (int num = 1; num <= k; num++)
{
int add = num - 1;
int copy = ceil(1.0 * k / num) - 1;
minOps = min(minOps, add + copy);
}
return minOps;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(k)。
空间复杂度：O(1)。
题目3：3092. 最高频率的 ID
思路
用哈希表 cnt 记录 x=nums[i] 的出现次数 cnt[x]（用 freq 更新出现次数）。
用有序集合 multiset 记录 cnt[x]，从而可以 O(logn) 知道最大的 cnt[x] 是多少。
代码
/*
* @lc app=leetcode.cn id=3092 lang=cpp
*
* [3092] 最高频率的 ID
*/
// @lc code=start
class Solution
{
public:
vector<long long> mostFrequentIDs(vector<int> &nums, vector<int> &freq)
{
int n = nums.size();
unordered_map<int, long long> cnt;
multiset<long long> ms;
vector<long long> ans(n);
for (int i = 0; i < n; i++)
{
auto it = ms.find(cnt[nums[i]]);
if (it != ms.end())
ms.erase(it);
cnt[nums[i]] += freq[i];
ms.insert(cnt[nums[i]]);
ans[i] = *(ms.rbegin());
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。
题目4：3093. 最长公共后缀查询
思路
从左到右遍历 wordsContainer，设 s=wordsContainer[i]。
倒着遍历 s，插入字典树。插入时，对于每个经过的节点，更新节点对应的最小字符串长度及其下标。
对于查询 s=wordsQuery[i]，仍然倒着遍历 s。在字典树上找到最后一个匹配的节点，那么该节点保存的下标就是答案。
代码
/*
* @lc app=leetcode.cn id=3093 lang=cpp
*
* [3093] 最长公共后缀查询
*/
// @lc code=start
// 字典树
struct Trie
{
Trie *child[26]{};
int minLen = INT_MAX; // 匹配字符串的最小长度
int index = 0; // 匹配字符串在 wordsContainer 里的下标
};
class Solution
{
public:
vector<int> stringIndices(vector<string> &wordsContainer, vector<string> &wordsQuery)
{
Trie *root = new Trie();
for (int i = 0; i < wordsContainer.size(); i++)
{
string &s = wordsContainer[i];
int len = s.length();
auto cur = root;
// 如果当前字符串长度小于当前节点记录的最小长度，更新最小长度和下标
if (len < cur->minLen)
{
cur->minLen = len;
cur->index = i;
}
// 逆序建立字典树
for (int j = len - 1; j >= 0; j--)
{
int idx = s[j] - 'a';
if (!cur->child[idx])
cur->child[idx] = new Trie();
cur = cur->child[idx];
// 如果当前字符串长度小于当前节点记录的最小长度，更新最小长度和下标
if (len < cur->minLen)
{
cur->minLen = len;
cur->index = i;
}
}
}
vector<int> ans;
for (string &word : wordsQuery)
{
auto cur = root;
for (int i = word.length() - 1; i >= 0 && cur->child[word[i] - 'a']; i--)
cur = cur->child[word[i] - 'a'];
ans.push_back(cur->index);
}
return ans;
}
};
// @lc code=end
复杂度分析
