欢迎大家加QQ群：623375442，可以方便群里面交流。久违的手速场，最近周赛老坐牢。
100400. Report Spam Message
给你一个字符串数组 message 和一个字符串数组 bannedWords。
如果数组中 至少 存在两个单词与 bannedWords 中的任一单词 完全相同，则该数组被视为 垃圾信息。
如果数组 message 是垃圾信息，则返回 true；否则返回 false。
测试样例：
输入：message = ["hello","world","leetcode"], bannedWords = ["world","hello"]
输出：true
解释：数组 message 中的 "hello" 和 "world" 都出现在数组 bannedWords 中。
解答：直接利用HashSet统计一下hit到的message是否超过2个。
class Solution {
public boolean reportSpam(String[] message, String[] bannedWords) {
Set<String> set = new HashSet<>();
for (String w : bannedWords) {
set.add(w);
}
int count = 0;
for (String ms : message) {
if (set.contains(ms)) {
++count;
if (count >= 2) {
return true;
}
}
}
return false;
}
}100363. Minimum Number of Seconds to Make Mountain Height Zero
给你一个整数 mountainHeight 表示山的高度。
同时给你一个整数数组 workerTimes，表示工人们的工作时间（单位：秒）。
工人们需要 同时 进行工作以 降低 山的高度。对于工人 i :
- 山的高度降低 x，需要花费 workerTimes[i] + workerTimes[i] 2 + ... + workerTimes[i] x 秒。例如：
- 山的高度降低 1，需要 workerTimes[i] 秒。
- 山的高度降低 2，需要 workerTimes[i] + workerTimes[i] * 2 秒，依此类推。
返回一个整数，表示工人们使山的高度降低到 0 所需的 最少 秒数。
测试样例：
输入：mountainHeight = 4, workerTimes = [2,1,1]
输出：3
解释：将山的高度降低到 0 的一种方式是：
- 工人 0 将高度降低 1，花费 workerTimes[0] = 2 秒。
- 工人 1 将高度降低 2，花费 workerTimes[1] + workerTimes[1] * 2 = 3 秒。
- 工人 2 将高度降低 1，花费 workerTimes[2] = 1 秒。
因为工人同时工作，所需的最少时间为 max(2, 3, 1) = 3 秒。
解答：工人是同时工作，所以我们优先队列记录一下当前最小时间完成所有移山任务。
class Solution {
public long minNumberOfSeconds(int mountainHeight, int[] workerTimes) {
long[] workerTimesInLong = new long[workerTimes.length];
long[] mul = new long[workerTimes.length];
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (Long.compare(workerTimesInLong[a], workerTimesInLong[b])));
for (int i = 0; i < workerTimesInLong.length; ++i) {
workerTimesInLong[i] = workerTimes[i];
mul[i] = 1;
queue.add(i);
}
long res = 0;
while (mountainHeight > 0 && !queue.isEmpty()) {
int tmp = queue.poll();
res = Math.max(res, workerTimesInLong[tmp]);
mul[tmp] += 1;
workerTimesInLong[tmp] = workerTimesInLong[tmp] + mul[tmp] * workerTimes[tmp];
queue.add(tmp);
--mountainHeight;
}
return res;
}
}100427. Count Substrings That Can Be Rearranged to Contain a String II
给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀 ，那么我们称字符串 x 是 合法的 。
请你返回 word1 中 合法 子字符串 的数目。
注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。
测试样例：
输入：word1 = "bcca", word2 = "abc"
输出：1
解释：唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。
解答：经典双指针的题目。右指针的移动来确定满足要求的最小范围。
class Solution {
public long validSubstringCount(String word1, String word2) {
int distinct = 0;
long res = 0;
boolean[] isUsed = new boolean[26];
int[] count = new int[26];
for (int i = 0; i < word2.length(); ++i) {
int o = word2.charAt(i) - 'a';
if (!isUsed[o]) {
isUsed[o] = true;
++distinct;
}
count[o] += 1;
}
int left = 0, right = 0;
while (left < word1.length()) {
while (distinct > 0 && right < word1.length()) {
distinct += distinctDiff(isUsed, count, word1.charAt(right) - 'a', -1);
++right;
}
if (distinct == 0) {
res += word1.length() - right + 1;
}
distinct += distinctDiff(isUsed, count, word1.charAt(left) - 'a', 1);
++left;
}
return res;
}
private int distinctDiff(boolean[] isUsed, int[] count, int offset, int dir) {
if (isUsed[offset]) {
if (dir == -1) {
count[offset] -= 1;
if (count[offset] == 0) {
return -1;
}
} else {
count[offset] += 1;
if (count[offset] == 1) {
return 1;
}
}
}
return 0;
}
}