目录
一，3090. 每个字符最多出现两次的最长子字符串
二，3091. 执行操作使数据元素之和大于等于 K
三，3092. 最高频率的 ID
四，3093. 最长公共后缀查询
一，3090. 每个字符最多出现两次的最长子字符串
本题是一道标准的滑动窗口问题，代码如下：
class Solution {
public int maximumLengthSubstring(String s) {
char[] ch = s.toCharArray();
int[] cnt = new int[26];
int ans = 0;
for(int l=0, r=0; r<ch.length; r++){
cnt[ch[r]-'a']++;
while(cnt[ch[r]-'a']>2){
cnt[ch[l]-'a']--;
l++;
}
ans = Math.max(ans, r-l+1);
}
return ans;
}
}二，3091. 执行操作使数据元素之和大于等于 K
本题是一道贪心题，由题可知，只有先执行+1操作，再执行复制操作，它的操作次数才是最少的，又因为本题的数据范围不大，所以可以使用枚举的方式来求最小值，代码如下：
class Solution {
public int minOperations(int k) {
int ans = Integer.MAX_VALUE;
for(int i=1; i<50000; i++){
// i-1 表示 i 执行 +1 操作的次数
// (k-i-1)/i+1 表示执行 复制 操作的次数
ans = Math.min(ans, (i-1)+(k-i-1)/i+1);
}
return ans;
}
}上述的公式可以化简成 i + (k-1)/i - 1，从数学的角度来看，这就是 y = x + (k-1)/x + c 函数，所以由函数特点可知，要使 y 最小，x = k-1开根号，又因为题目中的 x 必须为正整数，所以需要求 x 左右两侧的正整数。函数图像：
代码如下：
class Solution {
public int minOperations(int k) {
int rt = Math.max((int)Math.sqrt(k-1),1);
return Math.min(rt-1+(k-1)/rt, rt+(k-1)/(rt+1));
}
}三，3092. 最高频率的 ID
本题求的是ID出现次数最多的出现次数，注意返回的是出现次数，不是ID，这里有两种写法：
1）哈希表 + 有序集合
使用哈希表存储 < ID，ID出现次数 >，使用有序集合存储 < ID出现次数，ID出现次数的次数>，根据题目要求进行模拟，代码如下：
class Solution {
public long[] mostFrequentIDs(int[] nums, int[] freq) {
int n = nums.length;
Map<Integer, Long> map = new HashMap<>();
TreeMap<Long, Integer> tree = new TreeMap<>();
long[] ans = new long[n];
for(int i=0; i<n; i++){
int x = nums[i];
if(map.containsKey(x) && tree.containsKey(map.get(x))){
if(tree.get(map.get(x))-1 == 0)
tree.remove(map.get(x));
else
tree.put(map.get(x), tree.get(map.get(x))-1);
}
map.put(x, map.getOrDefault(x,0L)+freq[i]);
tree.put(map.get(x), tree.getOrDefault(map.get(x),0)+1);
ans[i] = tree.lastKey();
}
return ans;
}
}2）哈希表 + 懒删除堆
和上面那种方法一样，只不过这里使用堆来维护最大的出现次数，此外堆里存储的内容和上文不同，堆里存储的是 < ID出现的次数，ID >，（注：这里使用最大堆，可以通过pop直接得到最大值，如果使用最小堆可能会超时）代码如下：
class Solution {
public long[] mostFrequentIDs(int[] nums, int[] freq) {
int n = nums.length;
long[] ans = new long[n];
Map<Long, Long> map = new HashMap<>();
PriorityQueue<Long[]> que = new PriorityQueue<>((x,y)->Long.compare(y[0],x[0]));
for(int i=0; i<n; i++){
long x = nums[i];
map.put(x, map.getOrDefault(x,0L)+freq[i]);
que.offer(new Long[]{map.get(x), x});
while(!map.get(que.peek()[1]).equals(que.peek()[0])){
que.poll();
}
ans[i] = que.peek()[0];
}
return ans;
}
}四，3093. 最长公共后缀查询
本题求最长公共后缀的数组下标，是一道典型的字典树题，不懂的可以看Leetcode - 周赛385那篇博客，节点中需要存储的内容需要变一下，存储一下数组长度及其下标，代码如下：
class Solution {
static class Node{
Node[] node = new Node[26];
int len;//最短长度
int idx;//下标
}
public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
int n = wordsContainer.length;
Node root = new Node();
int min = wordsContainer[0].length();
int k = 0;//求如果没有公共后缀时，它的结果为最短长度&最靠前的数组下标
//后缀字典树
for(int i=0; i<n; i++){
String s = wordsContainer[i];
if(min > s.length()){
min = s.length();
k = i;
}
char[] ch = s.toCharArray();
Node cur = root;
for(int j=ch.length-1; j>=0; j--){
int index = ch[j]-'a';
if(cur.node[index]==null){
cur.node[index] = new Node();
cur.node[index].len = s.length();
cur.node[index].idx = i;
}
if(cur.node[index].len > s.length()){
cur.node[index].len = s.length();
cur.node[index].idx = i;
}
cur = cur.node[index];
}
}
int m = wordsQuery.length;
int[] ans = new int[m];
Arrays.fill(ans, -1);
for(int i=0; i<m; i++){
Node cur = root;
String s = wordsQuery[i];
char[] ch = s.toCharArray();
for(int j=ch.length-1; j>=0; j--){
int index = ch[j]-'a';
if(cur.node[index]==null){
if(ans[i] == -1)
ans[i] = k;
break;
}else{
ans[i] = cur.node[index].idx;
cur = cur.node[index];
}
}
}
return ans;
}
}
