【LeetCode周赛】第 390 场周赛

3090. 每个字符最多出现两次的最长子字符串 简单

3090. 每个字符最多出现两次的最长子字符串

分析：
数据量，按照题意模拟即可。
这里我是用了 前缀和 记录了 0~i 的所有字母出现的次数。

代码：

C++

class Solution {
public:int maximumLengthSubstring(string s) {int n=s.length();vector<vector<int>> cnt(n+1,vector<int>(26,0));for(int i=0;i<n;i++){cnt[i+1][s[i]-'a']++;for(int j=0;j<26;j++) cnt[i+1][j]+=cnt[i][j];}for(int i=n;i>1;i--){for(int j=0;j+i<=n;j++){int k=0;for(;k<26;k++){if(cnt[j+i][k]-cnt[j][k]>2) break;}if(k==26) return i;}}return 1;}
};

---

python

class Solution:def maximumLengthSubstring(self, s: str) -> int:cnt = [[0] * 216 for i in range(len(s)+1)]for i in range(len(s)):cnt[i+1][ord(s[i]) - ord('a')]+=1for j in range(26):cnt[i+1][j] += cnt[i][j]for i in range(len(s),1,-1):for j in range(0,len(s)-i+1):flag = Truefor k in range(26):if cnt[i+j][k] - cnt[j][k]>2:flag=Falsebreakif flag:return ireturn 1

3091. 执行操作使数据元素之和大于等于 K 中等

3091. 执行操作使数据元素之和大于等于 K

分析：

法一：
贪心+找规律
在固定的操作次数 $l$ 下，先进行 $\lfloor l/2\rfloor$ 次操作一，再进行 $l-\lfloor l/2\rfloor$ 操作二，即可得到最大的元素之和。
规律如下：

操作次数 l	最大元素之和
$1$	$1\ast 2=2$
$2$	$2\ast 2=4$
$3$	$2\ast 3=6$
$4$	$3\ast 3=9$
$5$	$3\ast 4=12$
$6$	$4\ast 4=16$
…	…

最终依照此规律，寻找最小的大于 k 的操作次数。

法二：
贪心+枚举
先加，后复制得到的数更大。
最多进行 k-1 次加法，此时是操作次数最大的情况，枚举 1~k-1 次加法，再计算后续还需要多少次复制，维护最小操作数即可。

代码：

法一
C++

class Solution {
public:int minOperations(int k) {if(k==0||k==1) return 0;int cnt=1,a=1,b=2;while(a*b<k){if(a<b) a++;else b++;cnt++;}return cnt;}
};

python

class Solution:def minOperations(self, k: int) -> int:if k==1 or k==0:return 0cnt,a,b=1,1,2while a*b<k:if a<b:a+=1else:b+=1cnt+=1return cnt

法二：法二

3092. 最高频率的 ID 中等

3092. 最高频率的 ID

分析：
寻找每次操作后，出现频率最高的数即可。
题目难点在于，在每次操作之后怎么寻找当前出现频率最高的数。

• 遍历的话，数据量大一定超时。
• 利用语言自带的工具
  • 哈希表 + 可重复的有序集合：c++中的 multiset ，python中的 SortedList
  • 哈希表 + 优先队列 + 懒删除堆

懒删除堆：因为优先队列不能查找，因此对于并非队首或队尾的元素，我们无法操作。可以使用 哈希表 维护当前的ID出现的次数，并将修改后的ID即其出现次数放入优先队列。同时对比优先队列队首的ID出现次数，与当前不符，就弹出。

代码：

哈希表 + 可重复的有序集合
C++

class Solution {
public:vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {unordered_map<int ,long long> m;multiset<long long> s;vector<long long> ans;m[nums[0]]+=1LL*freq[0];s.emplace(1LL*freq[0]);ans.push_back(1LL*freq[0]);for(int i=1;i<nums.size();i++){long long t = m[nums[i]];m[nums[i]]+=1LL*freq[i];auto it = s.find(t);if(it != s.end()){s.erase(it); // 删除集合中的一个 t}s.insert(m[nums[i]]);ans.push_back(*s.rbegin()); // 有序集合，s.rbegin() 即为最大的出现次数}return ans;}
};

python

from sortedcontainers import SortedList
class Solution:def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:cnt = Counter()s = SortedList()ans = []for x,f in zip(nums, freq):t = cnt[x]s.discard(t)cnt[x]+=fs.add(cnt[x])ans.append(s[-1])return ans

哈希表 + 优先队列 + 懒删除堆
C++

class Solution {
public:vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {unordered_map<int ,long long> m;priority_queue<pair<long long, int>> q;vector<long long> ans;m[nums[0]]+=1LL*freq[0];q.emplace(m[nums[0]], nums[0]);ans.push_back(1LL*freq[0]);for(int i=1;i<nums.size();i++){long long t = m[nums[i]];m[nums[i]]+=1LL*freq[i];q.emplace(m[nums[i]], nums[i]); // 不断的将修改后的 ID 及其 对应的出现次数 加入优先队列// 如下循环 实现 懒删除堆while(m[q.top().second] != q.top().first) q.pop(); // 与当前 ID 的出现次数不符合，弹出优先队列ans.push_back(q.top().first);}return ans;}
};

python

class Solution:def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:cnt = Counter()h = []ans = []for x,f in zip(nums, freq):cnt[x]+=fheapq.heappush(h, (-cnt[x], x))while -h[0][0] != cnt[h[0][1]]:heapq.heappop(h)ans.append(-h[0][0])return ans

3093. 最长公共后缀查询 困难

3093. 最长公共后缀查询

分析：
构建基于字符串后缀的字典树，并且不断维护对应下标，后续不断在字典树上查找即可。
注意数组的使用，容易内存超限。
同时注意当没有后缀与其匹配是，需要填入最短字符串的下标、

构建字典树模板：CPP
构建字典树模板：Python

代码：

C++

class Node{
public:int index=-1;Node* next[26]{};
};class Solution {
public:vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {int n=wordsContainer.size(),m=wordsQuery.size(),d=1e4+5,dindex=-1;vector<int> ans;Node* root = new Node();for(int i=0;i<n;i++){int l=wordsContainer[i].length();if(d>l) d=l,dindex=i;Node* node = root;for(int j=l-1;j>=0;j--){int k = wordsContainer[i][j]-'a';if(!node->next[k]) node->next[k] = new Node();node = node->next[k];if(node->index==-1) node->index=i;else{if(wordsContainer[node->index].length()>l) node->index=i;}}}for(int i=0;i<m;i++){Node* node = root;int l=wordsQuery[i].length();int index=-1;for(int j=l-1;j>=0;j--){int k = wordsQuery[i][j]-'a';if(!node->next[k])break;node=node->next[k];index=node->index;}ans.push_back(index!=-1?index:dindex);}return ans;}
};

python

class Node:def __init__(self) -> None:self.children = [None] * 26self.index = -1class Solution:def stringIndices(self, wordsContainer: List[str], wordsQuery: List[str]) -> List[int]:n,m = len(wordsContainer), len(wordsQuery)d,d_index = len(wordsContainer[0]),0ans = []def build_trie() -> Node: # 构建字典树nonlocal wordsContainer,d,d_indexroot = Node()for i in range(n):l=len(wordsContainer[i])if d>l:d=ld_index=inode = rootfor j in range(l-1, -1, -1):k = ord(wordsContainer[i][j]) - ord('a') # 字母转换成下标if node.children[k] == None:node.children[k] = Node()node = node.children[k]if node.index == -1: # 更新更优下标node.index = ielse:node.index = i if len(wordsContainer[node.index]) > l else node.indexreturn rootroot = build_trie()def find_word(s: str):nonlocal rootnode = rootindex = -1for i in range(len(s)-1,-1,-1):k = ord(s[i]) - ord('a')if node.children[k]==None:breaknode = node.children[k]index = node.indexreturn indexfor i in range(m):t = find_word(wordsQuery[i])ans.append(t if t!=-1 else d_index)return ans