周末高烧鸽了一周的双周赛和周赛。现在流感和新冠高发季节，都保重。
2956. Find Common Elements Between Two Arrays
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们分别含有 n 和 m 个元素。
请你计算以下两个数值：
- 统计 0 <= i < n 中的下标 i ，满足 nums1[i] 在 nums2 中 至少 出现了一次。
- 统计 0 <= i < m 中的下标 i ，满足 nums2[i] 在 nums1 中 至少 出现了一次。
请你返回一个长度为 2 的整数数组 answer ，按顺序 分别为以上两个数
测试样例：
输入：nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
输出：[3,4]
解释：
- nums1 中下标为 1 ，2 和 3 的元素在 nums2 中至少出现了一次，所以第一个值为 3 。
- nums2 中下标为 0 ，1 ，3 和 4 的元素在 nums1 中至少出现了一次，所以第二个值为 4 。
解答：利用HashSet寻找共同出现的元素。
class Solution {
public int[] findIntersectionValues(int[] nums1, int[] nums2) {
return new int[]{common(nums1, nums2), common(nums2, nums1)};
}
private int common(int[] n1, int[] n2) {
Set<Integer> set = new HashSet<>();
for (int n : n2) {
set.add(n);
}
int res = 0;
for (int n : n1) {
if (set.contains(n)) ++res;
}
return res;
}
}2957. Remove Adjacent Almost-Equal Characters
给你一个下标从 0 开始的字符串 word 。
一次操作中，你可以选择 word 中任意一个下标 i ，将 word[i] 修改成任意一个小写英文字母。
请你返回消除 word 中所有相邻 近似相等 字符的 最少 操作次数。
两个字符 a 和 b 如果满足 a == b 或者 a 和 b 在字母表中是相邻的，那么我们称它们是 近似相等 字符。
测试样例：
输入：word = "aaaaa"
输出：2
解释：我们将 word 变为 "acaca" ，该字符串没有相邻近似相等字符。消除 word 中所有相邻近似相等字符最少需要 2 次操作。
解答：这题可以利用贪婪算法，自己做的时候我就偷懒用了动态规划。动态规划的重点在于记录更新/不更新当前字符，所需要的最少满足要求的修改数。贪婪的话，就是修改最后的字符永远是最优的。
class Solution {
public int removeAlmostEqualCharacters(String word) {
int len = word.length();
int[][] dp = new int[len][2];
dp[0][1] = 1;
for (int i = 1; i < word.length(); ++i) {
if (Math.abs(word.charAt(i) - word.charAt(i - 1)) <= 1) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
} else {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][0]);
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
}
}
return Math.min(dp[len - 1][0], dp[len - 1][1]);
}
}2958. Length of Longest Subarray With at Most K Frequency
给你一个整数数组 nums 和一个整数 k 。
一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。
如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。
请你返回 nums 中 最长好 子数组的长度。
子数组 指的是一个数组中一段连续非空的元素序列。
测试样例：
输入：nums = [1,2,3,1,2,3,1,2], k = 2
输出：6
解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。最长好子数组的长度为 6 。
解答：最长的好子数组，它的子数组一定是好数组。这样我们可以利用折半搜索来定位最优数组。
class Solution {
public int maxSubarrayLength(int[] nums, int k) {
int st = k, ed = nums.length;
while (st < ed) {
int mid = (st + ed + 1) / 2;
if (isValid(nums, mid, k)) {
st = mid;
} else {
ed = mid - 1;
}
}
return st;
}
private boolean isValid(int[] nums, int len, int k) {
HashMap<Integer, Integer> numCount = new HashMap<>();
int exceed = 0;
for (int i = 0; i < nums.length; ++i) {
int ori = numCount.getOrDefault(nums[i], 0);
numCount.put(nums[i], ori + 1);
if (ori == k) {
++exceed;
}
if (i >= len - 1) {
if (exceed == 0) {
return true;
}
int r = nums[i - len + 1];
int freq = removeKey(numCount, r);
if (freq - 1 == k) {
--exceed;
}
}
}
return false;
}
private int removeKey(Map<Integer, Integer> map, int key) {
if (map.containsKey(key)) {
int c = map.get(key);
if (c == 1) {
map.remove(key);
} else {
map.put(key, c - 1);
}
return c;
}
return -1;
}
}2959. Number of Possible Sets of Closing Branches
一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。
公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。
两个分部之间的 距离 是通过道路长度之和的 最小值 。
给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的 无向 道路。
请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。
注意，关闭一个分部后，与之相连的所有道路不可通行。
注意，两个分部之间可能会有多条道路。
测试样例：
输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
输出：5
解释：可行的关闭分部方案有：
- 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 5 种可行的关闭方案。
解答：这题搜索范围相当小，n <= 10。可以用状态压缩来记录可以完成的方案。利用佛洛依德算法可以计算出任意两点的最短距离。
class Solution {
public int numberOfSets(int n, int maxDistance, int[][] roads) {
int[][] dis = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) dis[i][j] = Integer.MAX_VALUE / 2;
}
}
for (int[] r : roads) {
dis[r[0]][r[1]] = Math.min(dis[r[0]][r[1]], r[2]);
dis[r[1]][r[0]] = Math.min(dis[r[1]][r[0]], r[2]);
}
int res = 0;
for (int i = 0; i < (1 << n); ++i) {
int[][] distance = flyodAlgorithm(n, dis, i);
boolean isValid = true;
out:
for (int a = 0; a < n; ++a) {
for (int b = 0; b < n; ++b) {
if (isMark(i, a, b) && distance[a][b] > maxDistance) {
isValid = false;
break out;
}
}
}
if (isValid) {
++res;
}
}
return res;
}
private int[][] flyodAlgorithm(int n, int[][] edges, int key) {
int[][] res = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i != j) {
if (isMark(key, i, j)) {
res[i][j] = edges[i][j];
} else {
res[i][j] = Integer.MAX_VALUE / 2;
}
}
}
}
for(int k = 0; k < n; k++) {
if (isMark(key, k)) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isMark(key, i, j)) {
res[i][j] = res[j][i] = Math.min(res[i][j], res[i][k] + res[j][k]);
}
}
}
}
}
return res;
}
private boolean isMark(int key, int x, int y) {
return isMark(key, x) && isMark(key, y);
}
private boolean isMark(int key, int x) {
int m = (key >> x) & 1;
return m == 1;
}
}2960. Count Tested Devices After Test Operations
给你一个长度为 n 、下标从 0 开始的整数数组 batteryPercentages ，表示 n 个设备的电池百分比。
你的任务是按照顺序测试每个设备 i，执行以下测试操作：
- 如果 batteryPercentages[i] 大于 0：
- 增加 已测试设备的计数。
- 将下标在 [i + 1, n - 1] 的所有设备的电池百分比减少 1，确保它们的电池百分比 不会低于 0 ，即 batteryPercentages[j] = max(0, batteryPercentages[j] - 1)。
- 移动到下一个设备。
- 否则，移动到下一个设备而不执行任何测试。
返回一个整数，表示按顺序执行测试操作后 已测试设备 的数量。
测试样例：
输入：batteryPercentages = [1,1,2,1,3]
输出：3
解释：按顺序从设备 0 开始执行测试操作：
- 在设备 0 上，batteryPercentages[0] > 0 ，现在有 1 个已测试设备，batteryPercentages 变为 [1,0,1,0,2] 。
- 在设备 1 上，batteryPercentages[1] == 0 ，移动到下一个设备而不进行测试。
- 在设备 2 上，batteryPercentages[2] > 0 ，现在有 2 个已测试设备，batteryPercentages 变为 [1,0,1,0,1] 。
- 在设备 3 上，batteryPercentages[3] == 0 ，移动到下一个设备而不进行测试。
- 在设备 4 上，batteryPercentages[4] > 0 ，现在有 3 个已测试设备，batteryPercentages 保持不变。
因此，答案是 3 。
解答：范围很小，直接按照题目暴力运算。
class Solution {
public int countTestedDevices(int[] batteryPercentages) {
int res = 0;
for (int i = 0; i < batteryPercentages.length; ++i) {
if (batteryPercentages[i] > 0) {
++res;
for (int j = i + 1; j < batteryPercentages.length; ++j) {
batteryPercentages[j] = Math.max(0, batteryPercentages[j] - 1);
}
}
}
return res;
}
}
2961. Double Modular Exponentiation
给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。
如果满足以下公式，则下标 i 是 好下标：
- 0 <= i < variables.length
- ((ai^bi % 10)^ci) % mi == target
返回一个由 好下标 组成的数组，顺序不限 。
测试样例：
输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
输出：[0,2]
解释：
对于 variables 数组中的每个下标 i ：
1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。因此，返回 [0,2] 作为答案。
解答：这题主要考了快速幂（也是类似分治的逻辑），注意计算过程中不要忘记取模，安全起见用long不太容易爆范围。
class Solution {
public List<Integer> getGoodIndices(int[][] variables, int target) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < variables.length; ++i) {
long f = quickMul(variables[i][0], variables[i][1], 10);
long result = quickMul(f, variables[i][2], variables[i][3]);
if (result == target) {
list.add(i);
}
}
return list;
}
private long quickMul(long x, int y, int mod) {
if (y == 0) {
return 1;
} else {
long tmp = quickMul(x, y / 2, mod);
tmp = (tmp * tmp) % mod;
if (y % 2 == 1) {
tmp = (tmp * x) % mod;
}
return tmp;
}
}
}2962. Count Subarrays Where Max Element Appears at Least K Times
给你一个整数数组 nums 和一个 正整数 k 。
请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。
子数组是数组中的一个连续元素序列。
测试样例：
输入：nums = [1,3,2,3,3], k = 2
输出：6
解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
解答：这道题目有点双指针的味道。首先寻找到最大值，并且把最大值的位置记录下来。然后计算每个最大值位置，可以贡献出多少个合法的连续元素序列（利用乘法就能快速计算）。
class Solution {
public long countSubarrays(int[] nums, int k) {
int max = -1;
for (int n : nums) {
max = Math.max(max, n);
}
List<Integer> pos = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == max) {
pos.add(i);
}
}
if (pos.size() < k) {
return 0;
}
long res = 0;
for (int i = k - 1; i < pos.size(); ++i) {
int right = (i + 1) < pos.size() ? pos.get(i + 1) : nums.length;
int left = pos.get(i - k + 1);
long d1 = right - pos.get(i), d2 = left + 1;
res += d1 * d2;
}
return res;
}
}2963. Count the Number of Good Partitions
给你一个下标从 0 开始、由 正整数 组成的数组 nums。
将数组分割成一个或多个 连续 子数组，如果不存在包含了相同数字的两个子数组，则认为是一种 好分割方案 。
返回 nums 的 好分割方案 的 数目。
由于答案可能很大，请返回答案对 10^9 + 7 取余 的结果。
测试样例：
输入：nums = [1,2,3,4]
输出：8
解释：有 8 种 好分割方案 ：([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]) 和 ([1,2,3,4]) 。
解答：这题应该是最近最简单的第四题了。首先寻找可以切割的位置。因为题目问的是切割方案，那么每个好的切割位置都存在切割与不切割两种状态，一共是2^(切割位)可能。
class Solution {
private static final int mod = 1_000_000_007;
public int numberOfGoodPartitions(int[] nums) {
HashMap<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
pos.put(nums[i], i);
}
int split = -1, lastPos = 0;
for (int i = 0; i < nums.length; ++i) {
lastPos = Math.max(lastPos, pos.get(nums[i]));
if (lastPos == i) {
++split;
}
}
int res = 1;
for (int i = 0; i < split; ++i) {
res *= 2;
res %= mod;
}
return res;
}
}