【LeetCode周赛】第 416 场

3295. 举报垃圾信息

给你一个字符串数组 message 和一个字符串数组 bannedWords。
如果数组中至少存在两个单词与 bannedWords 中的任一单词完全相同，则该数组被视为垃圾信息。
如果数组 message 是垃圾信息，则返回 true；否则返回 false。

思路：空间换时间，使用集合set存储bannedWords。
复杂度：O(n)

class Solution {public boolean reportSpam(String[] message, String[] bannedWords) {Set<String> set = new HashSet();for(String ban:bannedWords) {set.add(ban);}int cnt = 0;for(String msg:message) {if(set.contains(msg)) {cnt ++;if(cnt>=2) return true;}}return false;}
}

3296. 移山所需的最少秒数

给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要同时进行工作以降低山的高度。对于工人 i :
山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] * 2 + … + workerTimes[i] * x 秒。例如：
山的高度降低 1，需要 workerTimes[i] 秒。
山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。
返回一个整数，表示工人们使山的高度降低到 0 所需的最少秒数。

思想：使用PriorityQueue。具体来说，PriorityQueue存储一个长度为3的数组nums[3]，其中nums[0]存储下一次该位需要的时间，nums[1]存储workTimes[i]，nums[2]存储下一次需要几个workTimes[i]。每次选取PriorityQueue最小的的nums[0]，ans为其中最大的，然后将nums[0]更新。
复杂度：O(n)。

class Solution {public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {Queue<Long[]> q = new PriorityQueue<>((a, b)->Long.compare(a[0], b[0]));// Arrays.sort(workerTimes);long ans = 0;for(int i=0; i<workerTimes.length; i++) {// 在下降一米所用， 速度， 用时q.offer(new Long[]{Long.valueOf(workerTimes[i]), Long.valueOf(workerTimes[i]), Long.valueOf(2)});}for(int i=0; i<mountainHeight; i++) {Long[] nd = q.poll();ans = Math.max(ans, nd[0]);nd[0] = nd[0] + nd[1]*nd[2];nd[2] ++;q.offer(nd);            }return ans;}
}

3297. 统计重新排列后包含另一个字符串的子字符串数目 I

给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新排列后，word2 是重排字符串的
前缀，那么我们称字符串 x 是合法的。
请你返回 word1 中合法
子字符串的数目。

思路：滑动窗口，划出可以满足条件的窗口，然后窗口左端左移得到此刻最小的窗口，将left加入到答案。
复杂度：O(n).

class Solution {public long validSubstringCount(String word1, String word2) {// 滑动窗口，每一种符合条件的最小子串可以衍生出left个// w1和w2中每种字符数量int[] acnts = new int[128];int[] bcnts = new int[128];for(char c:word2.toCharArray()) {bcnts[c] ++;}int n = word1.length();long ans = 0;int l=0;// 以右端点为起点for(int r=0; r<n; r++) {acnts[word1.charAt(r)] ++;// w2中每个字符w1中都有时，尝试左移窗口变小，成为目前最短的子串while(check(acnts, bcnts)) {acnts[word1.charAt(l)] --;l ++;}ans += l;}return ans;}public boolean check(int[] acnts, int[] bcnts) {for(int i=0; i<128; i++) {if(acnts[i]<bcnts[i]) return false;}return true;}
}

优化：将两个统计字符的数组优化为一个。具体来说，cnts只记录word2中的字符，less记录不同字符的数量。窗口右移，对应的cnts的字符减一，注意words中没有的字符此时会减为负数，有的字符的cnts减为0时，less减一。less为0说明，是满足条件的窗口，尝试左移窗口左端，注意此时left对应的cnts为0，表明为word2中有的字符，less要加一，将left对应的字符加一。

class Solution {public long validSubstringCount(String word1, String word2) {// 滑动窗口，每一种符合条件的最小子串可以衍生出left个// w1和w2中每种字符数量int[] bcnts = new int[26];for(char c:word2.toCharArray()) {bcnts[c-'a'] ++;}int n = word1.length();long ans = 0;int l=0;// less表示w2中有多少个不同的字符int less = 0;for(int c:bcnts) {if(c>0) less ++;}// 以右端点为起点for(int r=0; r<n; r++) {// 未出现的字符的次数会变为负数if(--bcnts[word1.charAt(r)-'a'] == 0 ) {less --;}// w2中每个字符w1中都有时，尝试左移窗口变小，成为目前最短的子串while(less == 0) {// 当前次数为0，必是需要的if(bcnts[word1.charAt(l++)-'a']++ == 0) {less ++;} }ans += l;}return ans;}}