6273. Maximum Enemy Forts That Can Be Captured
给你一个长度为 n ，下标从 0 开始的整数数组 forts ，表示一些城堡。forts[i] 可以是 -1 ，0 或者 1 ，其中：
- -1 表示第 i 个位置 没有 城堡。
- 0 表示第 i 个位置有一个 敌人 的城堡。
- 1 表示第 i 个位置有一个你控制的城堡。
现在，你需要决定，将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j ，满足：
- 0 <= i, j <= n - 1
- 军队经过的位置 只有 敌人的城堡。正式的，对于所有 min(i,j) < k < max(i,j) 的 k ，都满足 forts[k] == 0 。
当军队移动时，所有途中经过的敌人城堡都会被 摧毁 。
请你返回 最多 可以摧毁的敌人城堡数目。如果 无法 移动你的军队，或者没有你控制的城堡，请返回 0 。
测试样例
输入：forts = [1,0,0,-1,0,0,0,0,1]
输出：4
解释：
- 将军队从位置 0 移动到位置 3 ，摧毁 2 个敌人城堡，位置分别在 1 和 2 。
- 将军队从位置 8 移动到位置 3 ，摧毁 4 个敌人城堡。
4 是最多可以摧毁的敌人城堡数目，所以我们返回 4 。
解答：这周做题略不顺利，起手就挂了一次。。。这题其实只要求计算1，-1对最大距离。偷懒，我就直接使用TreeSet配合ArrayList来计算对距离。
class Solution {
public int captureForts(int[] forts) {
TreeSet<Integer> empty = new TreeSet<>();
List<Integer> myFort = new ArrayList<>();
for (int i = 0; i < forts.length; ++i) {
if (forts[i] == -1) {
empty.add(i);
} else if (forts[i] == 1) {
myFort.add(i);
}
}
int max = 0;
for (int i = 0; i < myFort.size(); ++i) {
int lower = (i == 0 ? -1 : myFort.get(i - 1));
int right = (i + 1 < myFort.size() ? myFort.get(i + 1) : forts.length);
Integer leftEmpty = empty.lower(myFort.get(i));
if (leftEmpty != null && leftEmpty > lower) {
max = Math.max(max, myFort.get(i) - leftEmpty - 1);
}
Integer rightEmpty = empty.higher(myFort.get(i));
if (rightEmpty != null && rightEmpty < right) {
max = Math.max(rightEmpty - myFort.get(i) - 1, max);
}
}
return max;
}
}
6274. Reward Top K Students
给你两个字符串数组 positive_feedback 和 negative_feedback ，分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。
一开始，每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分，每个负面的词会给学生的分数 减 1 分。
给你 n 个学生的评语，用一个下标从 0 开始的字符串数组 report 和一个下标从 0 开始的整数数组 student_id 表示，其中 student_id[i] 表示这名学生的 ID ，这名学生的评语是 report[i] 。每名学生的 ID 互不相同。
给你一个整数 k ，请你返回按照得分 从高到低 最顶尖的 k 名学生。如果有多名学生分数相同，ID 越小排名越前。
测试样例
输入：positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2
输出：[2,1]
解释：
- ID 为 1 的学生有 1 个正面词汇和 1 个负面词汇，所以得分为 3-1=2 分。
- ID 为 2 的学生有 1 个正面词汇，得分为 3 分。
学生 2 分数更高，所以返回 [2,1] 。
解答：这道题主要考察阅读能力。按照题意，计算每个学生的成绩，并利用优先队列寻找最佳的K个学生即可。
class Solution {
public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
Set<String> pos = new HashSet<>(), neg = new HashSet<>();
for (String w : positive_feedback) {
pos.add(w);
}
for (String w : negative_feedback) {
neg.add(w);
}
int studentCount = student_id.length;
int[] score = new int[studentCount];
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (score[a] != score[b] ? (score[a] - score[b]) : (student_id[b] - student_id[a])));
for (int i = 0; i < studentCount; ++i) {
String[] strs = report[i].split(" ");
for (String w : strs) {
if (pos.contains(w)) {
score[i] += 3;
} else if (neg.contains(w)) {
score[i] -= 1;
}
}
queue.add(i);
if (queue.size() > k) {
queue.poll();
}
}
LinkedList<Integer> res = new LinkedList<>();
while (!queue.isEmpty()) {
res.addFirst(student_id[queue.poll()]);
}
return res;
}
}6295. Minimize the Maximum of Two Arrays
给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：
- arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都 不能 被 divisor1 整除 。
- arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都 不能 被 divisor2 整除 。
- arr1 和 arr2 中的元素 互不相同 。
给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。测试样例：
输入：divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3输出：4
解释：
我们可以把前 4 个自然数划分到 arr1 和 arr2 中。arr1 = [1] 和 arr2 = [2,3,4] 。
可以看出两个数组都满足条件。
最大值是 4 ，所以返回 4 。
解答: 这题需要使用二分查找和少量数学计算。首先需要想到，数值越大，能够加入2个数组的数字只会越多，不会越少，对数值存在单调性，所以二分查找是我们需要的算法。其次我们需要知道，给出一个数字N是否可以满足要求。
如果最大值是N，则
- 可以加入数组1的数字，最多有：l1 = N - N / div1
- 可以加入数组2的数字，最多有：l2 = N - N / div2
- 至少可以加入某个数组的数字，有：l3 = N - N / LCM(div1, div2)
- 则同时可以加入2个数组的数(共享数)，最多有：l1 + l2 - l3
拥有这些条件后，我们假设分配X个共享数给数组1，Y个共享数给数组2。那么满足：
- l1 - Y >= un1
- l2 - X >= un2
- X + Y = l1 + l2 - l3
这个N就能满足以上条件，就可以满足要求。我们利用单调性，二分查找即可。
class Solution {
public int minimizeSet(long divisor1, long divisor2, int uniqueCnt1, int uniqueCnt2) {
long gcd = gcd(divisor1, divisor2);
long m = divisor1 * divisor2 / gcd;
long min = 1, max = Integer.MAX_VALUE;
while (min < max) {
long mid = (min + max) / 2;
if (isValid(divisor1, divisor2, m, uniqueCnt1, uniqueCnt2, mid)) {
max = mid;
} else {
min = mid + 1;
}
}
return (int)min;
}
private long gcd(long x, long y) {
while (y != 0) {
long tmp = x % y;
x = y;
y = tmp;
}
return x;
}
private boolean isValid(long divisor1, long divisor2, long com, int uniqueCnt1, int uniqueCnt2, long cur) {
long l1 = cur - cur / divisor1, l2 = cur - cur / divisor2, l3 = cur - cur / com;
long dup = (l1 + l2) - l3;
if (l1 >= uniqueCnt1 && l2 >= uniqueCnt2) {
if ((l1 - uniqueCnt1) + (l2 - uniqueCnt2) >= dup) {
return true;
}
}
return false;
}
}6276. Count Anagrams
给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。
如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。
- 比方说，"acb dfe" 是 "abc def" 的同位异构字符串，但是 "def cab" 和 "adc bef" 不是。
请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 109 + 7 取余 后返回。
测试样例：
输入：s = "too hot"
输出：18
解释：
输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。
解答：我只能想到，这题利用了排列组合公式，计算一个词的同位异构字符串数。由于数字可能比较大，且存在除法。我也没想到什么好办法，就直接利用了乘法逆元。有什么正确的好做法，我会之后在更新一下。
class Solution {
private static final int mod = 1_000_000_007;
public int countAnagrams(String s) {
long[] invs = new long[1_00_001];
for (int i = 2; i < invs.length; ++i) {
invs[i] = inv(i);
}
long res = 1;
String[] arr = s.split(" ");
for (String w : arr) {
int[] count = new int[26];
for (int i = 0; i < w.length(); ++i) {
count[w.charAt(i) - 'a'] += 1;
}
long tmp = 1;
for (int i = 1; i <= w.length(); ++i) {
tmp = (tmp * i) % mod;
}
for (int i : count) {
if (i >= 2) {
for (int j = 2; j <= i; ++j) {
tmp = (tmp * invs[j]) % mod;
}
}
}
res = (res * tmp) % mod;
}
return (int)res;
}
private long inv(int x) {
return quickMul(x, mod - 2);
}
private long quickMul(int x, int y) {
long res = 1, cur = x;
while (y > 0) {
if (y % 2 == 1) {
res = res * cur % mod;
}
cur = cur * cur % mod;
y /= 2;
}
return res;
}
}本周双周赛，我觉得还挺难的。。。老年人看到数学题着实有点苦手。