目录

一，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));elsetree.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;}
}