第390场 LeetCode 周赛题解

滑动窗口：枚举窗口的左边界，尽可能右移窗口的右边界。 (当然也可以暴力枚举)

class Solution {
public:int maximumLengthSubstring(string s) {vector<int> cnt(26);int res = 0;for (int l = 0, r = -1, n = s.size();; cnt[s[l++] - 'a']--) {while (r + 1 < n && cnt[s[r + 1] - 'a'] + 1 <= 2)cnt[s[++r] - 'a']++;res = max(res, r - l + 1);if (r == n - 1)break;}return res;}
};

枚举：容易知道存在一种方案：“先通过第一种操作将数组从 $[1]$ 变为 $[i]$ ,再通过第二种操作让数组和不小于 $k$” 可以让操作数最少。枚举 $i$ 以计算最小操作数

class Solution {
public:int minOperations(int k) {int res = INT32_MAX;for (int i = 1; i <= k; i++)res = min(res, i - 1 + (k - 1) / i);return res;}
};

最大堆+哈希：用最大堆维护当前频率最高的ID，用哈希表记录各ID的最新频率

class Solution {
public:using ll = long long;vector<long long> mostFrequentIDs(vector<int> &nums, vector<int> &freq) {priority_queue<pair<ll, int>> heap;//(freq,id)unordered_map<int, ll> f;vector<ll> res;for (int i = 0; i < nums.size(); i++) {f[nums[i]] += freq[i];heap.emplace(f[nums[i]], nums[i]);while (f[heap.top().second] != heap.top().first)heap.pop();res.push_back(heap.top().first);}return res;}
};

字典树：遍历 wordsContainer 中的字符串，并将其按后缀插入字典树，同时更新字典树插入路径上的标记。然后遍历 wordsQuery ，在字典树上查询匹配的最长后缀的标记

class Solution {
public:vector<int> stringIndices(vector<string> &wordsContainer, vector<string> &wordsQuery) {trie tree;for (int i = 0; i < wordsContainer.size(); i++)tree.insert(wordsContainer[i], i, wordsContainer[i].size());vector<int> res;for (auto &q: wordsQuery) res.push_back(tree.find(q));return res;}class trie {//字典树public:trie *next[26];int ind;//标记int mn;//wordsContainer[ind]的长度trie() {for (int i = 0; i < 26; i++)next[i] = nullptr;ind = -1;mn = 0;}void insert(string &s, int id, int len_i) {trie *cur = this;if (cur->ind == -1 || cur->mn > len_i) {//公共后缀为空的情况cur->ind = id;cur->mn = len_i;}for (auto i = s.rbegin(); i != s.rend(); i++) {if (!cur->next[*i - 'a'])cur->next[*i - 'a'] = new trie();cur = cur->next[*i - 'a'];if (cur->ind == -1 || cur->mn > len_i) {//更新标记cur->ind = id;cur->mn = len_i;}}}int find(string &s) {trie *cur = this;for (auto i = s.rbegin(); i != s.rend(); i++) {if (!cur->next[*i - 'a'])break;cur = cur->next[*i - 'a'];}return cur->ind;}};
};