目录

一，3295. 举报垃圾信息

二，3296. 移山所需的最少秒数

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

四，3298. 统计重新排列后包含另一个字符串的子字符串数目 II

---

一，3295. 举报垃圾信息

本题就是求message中是否至少存在2两个单词在banndedWord中，我们可以直接使用hash记录banndedWord中的字符串，再枚举message，使用cnt记录有几个单词在哈希表中，最后返回 cnt > 1.

代码如下：

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

二，3296. 移山所需的最少秒数

本题有两种做法：

1.最小堆

维护每个工人降低山的高度 x 所花费的时间，直到山的高度为0，返回堆顶的元素。

class Solution {public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {PriorityQueue<long[]> que = new PriorityQueue<>((x,y)->Long.compare(x[0], y[0]));for(long x : workerTimes){que.offer(new long[]{x, 1L, x});//时间，降低h，倍率}long ans = 0;while(mountainHeight-- > 0){long[] t = que.poll();long x = t[0], h = t[1], base = t[2];ans = x;que.offer(new long[]{x+(h+1)*base, h+1, base});}return ans;}
}

2.二分答案

给的时间越长，工人就越可能完成移山，具有单调性，可以二分，接下来就是如何判断二分的时间 t 是否能完成移山，假设 x = workertimes[i]，能减低的山的高度为 h，我们可以得到这个方程 （h+1)*h/2*x = t，化简得到 h^2 + h - 2*t/x = 0，通过一元二次方程求根公式x = -b+sqrt(b^2-4ac)/2a 或者-b-sqrt(b^2-4ac)/2a（由于答案为正整数，舍去）， 求解 h = -1 + sqrt(1+8*t/x))/2，然后将所有工人在 t 时间内所能降低的山的高度加起来，如果 < mountainHeight，l = mid + 1，否则 r = mid - 1.

class Solution {public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {long ans = 0;long l = 1, r = (long)(mountainHeight+1)*mountainHeight / 2 * workerTimes[0]; while(l <= r){long mid = (l + r) / 2;if(check(mid, mountainHeight, workerTimes))r = mid - 1;elsel = mid + 1;}return r + 1;}boolean check(long t, int h, int[] w){int ans = 0;for(int x : w){ans += Math.max(0, (int)(-1 + (int)Math.sqrt(1+8*t/x))/2);}return ans >= h;}
}

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

本题题意就是找word1中有多少个子字符串，且都要包含word2中的每个字符。直接使用滑动窗口来做。先使用一个数组cnt记录word2中每个字符出现的次数。枚举word1中子字符串的右端点，如果[L，R]的字符串中包含word2中的每个字符，我们就可以移动左端点，直到不满足条件为止，也就是说以L为左端点时，右端点[R，n)都满足条件，这时将 ans += n - R，代码如下：

class Solution {public long validSubstringCount(String word1, String word2) {char[] w1 = word1.toCharArray();char[] w2 = word2.toCharArray();int[] cnt = new int[26];for(char c : w2){cnt[c-'a']++;}long ans = 0;for(int l=0, r=0; r<w1.length; r++){boolean flg = false;char c = w1[r];cnt[c-'a']--;for(int i=0; i<26; i++){if(cnt[i] > 0) flg = true; }if(flg) continue;while(cnt[w1[l]-'a'] <= 0){ans += w1.length - r;if(++cnt[w1[l++]-'a'] > 0) break;}}return ans;}
}

四，3298. 统计重新排列后包含另一个字符串的子字符串数目 II

本题与T3相同，不过数据范围更大，这里我们再讲一个O(n)做法，T3的做法是O(26n)，也就是判断子字符串是否包含所有word2需要枚举cnt数组，其实我们可以额外添加一个变量less，记录word2中几个不同的字符。当word1子字符串中包含了n个x字符（word2中存在n个x字符）时，即cnt[x-'a']=0时，less--，那么 less = 0 说明该字符串满足条件。

代码如下：

class Solution {public long validSubstringCount(String word1, String word2) {char[] w1 = word1.toCharArray();char[] w2 = word2.toCharArray();int[] cnt = new int[26];for(char c : w2){cnt[c-'a']++;}int less = 0;for(int x : cnt){if(x > 0){less++;}}long ans = 0;for(int l=0, r=0; r<w1.length; r++){char c = w1[r];if(--cnt[c-'a'] == 0) less--;//只有原来cnt[x]>0（即删去的全是word2中存在的字符时）,less--while(less == 0){  ans += w1.length - r; if(++cnt[w1[l++]-'a'] > 0){less++;}   }}return ans;}
}