🌟欢迎来到 我的博客 —— 探索技术的无限可能！
20.找出最长的超赞子字符串
题目链接：1542. 找出最长的超赞子字符串
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件：
该字符串是 s 的一个非空子字符串
进行任意次数的字符交换后，该字符串可以变成一个回文字符串
示例 1：
输入：s = "3242415"
输出：5
解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"
示例 2：
输入：s = "12345678"
输出：1
示例 3：
输入：s = "213123"
输出：6
解释："213123" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "231132"
示例 4：
输入：s = "00"
输出：2
提示：
1 <= s.length <= 10^5
s 仅由数字组成
题解：
方法：前缀异或和
要实现的方法是要接收一个字符串参数 s，并返回该字符串中最长的“好子串”的长度。
所谓“好子串”，是指满足以下条件的子串：
- 子串中每个字符的出现次数都是偶数；
- or子串中恰好有一个字符出现奇数次。
为了实现这个功能，使用了前缀异或和。先初始化了一个长度为 $2^D$ 的数组 pos，用于存储前缀异或和的位置。然后遍历字符串 s，计算当前前缀异或和 pre，并根据 pre 的值更新答案 ans。最后返回最长子串的长度 ans。
==需要注意的是==，由于题目中的字符种类只有 10 种（即 '0' 到 '9'），因此可以使用位运算来表示前缀异或和。（eg：对于字符 c，其对应的二进制位为 $(c - '0')，因此可以通过将 1 左移 $(c - '0') 位来得到该字符的二进制位。）
class Solution {
private static final int D = 10; // s 中的字符种类数
public int longestAwesome(String s) {
int n = s.length(); // 获取字符串长度
int[] pos = new int[1 << D]; // 初始化一个长度为 2^D 的数组，用于存储前缀异或和的位置
Arrays.fill(pos, n); // 将数组填充为 n，表示没有找到异或前缀和
pos[0] = -1; // pre[-1] = 0，表示初始状态的前缀异或和为 0
int ans = 0; // 初始化答案为 0
int pre = 0; // 初始化当前前缀异或和为 0
for (int i = 0; i < n; i++) {
// 遍历字符串
pre ^= 1 << (s.charAt(i) - '0'); // 更新当前前缀异或和
for (int d = 0; d < D; d++) {
// 遍历所有可能的字符种类
ans = Math.max(ans, i - pos[pre ^ (1 << d)]); // 计算奇数长度的子串的最大长度
}
ans = Math.max(ans, i - pos[pre]); // 计算偶数长度的子串的最大长度
if (pos[pre] == n) {
// 如果首次遇到值为 pre 的前缀异或和，记录其下标 i
pos[pre] = i;
}
}
return ans; // 返回最长子串的长度
}
}
==题单：前缀异或和==
1310. 子数组异或查询
1177. 构建回文串检测
1371. 每个元音包含偶数次的最长子字符串
1542. 找出最长的超赞子字符串
1915. 最美子字符串的数目
2791. 树中可以形成回文的路径数
21.找出最大的可达成数字
题目链接：2769. 找出最大的可达成数字
给你两个整数 num 和 t 。
如果整数 x 可以在执行下述操作不超过 t 次的情况下变为与 num 相等，则称其为 可达成数字 ：
每次操作将 x 的值增加或减少 1 ，同时可以选择将 num 的值增加或减少 1 。
返回所有可达成数字中的最大值。可以证明至少存在一个可达成数字。
示例 1：
输入：num = 4, t = 1
输出：6
解释：最大可达成数字是 x = 6 ，执行下述操作可以使其等于 num ：
- x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。
可以证明不存在大于 6 的可达成数字。
示例 2：
输入：num = 3, t = 2
输出：7
解释：最大的可达成数字是 x = 7 ，执行下述操作可以使其等于 num ：
- x 减少 1 ，同时 num 增加 1 。此时，x = 6 且 num = 4 。
- x 减少 1 ，同时 num 增加 1 。此时，x = 5 且 num = 5 。
可以证明不存在大于 7 的可达成数字。
提示：
1 <= num, t <= 50
题解：
方法：数学
每次操作可以将 x 减少 1，同时将 num 增加 1，这样 x 和 num 的差值就会减少 2，而最多可以操作 t 次，所以最大可达成数字为 num+t×2。
class Solution {
public int theMaximumAchievableX(int num, int t) {
return num + t * 2;
}
}
22.找出输掉零场或一场比赛的玩家
题目链接：2225. 找出输掉零场或一场比赛的玩家
给你一个整数数组 matches 其中 matches[i] = [winneri, loseri] 表示在一场比赛中 winneri 击败了 loseri 。
返回一个长度为 2 的列表 answer ：
answer[0] 是所有 没有 输掉任何比赛的玩家列表。
answer[1] 是所有恰好输掉 一场 比赛的玩家列表。
两个列表中的值都应该按 递增 顺序返回。
注意：
只考虑那些参与 至少一场 比赛的玩家。
生成的测试用例保证 不存在 两场比赛结果 相同 。
示例 1：
输入：matches =
[[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]输出：[[1,2,10],[4,5,7,8]]
解释：
玩家 1、2 和 10 都没有输掉任何比赛。
玩家 4、5、7 和 8 每个都输掉一场比赛。
玩家 3、6 和 9 每个都输掉两场比赛。
因此，answer[0] = [1,2,10] 和 answer[1] = [4,5,7,8] 。
示例 2：
输入：matches = [[2,3],[1,3],[5,4],[6,4]]
输出：[[1,2,5,6],[]]
解释：
玩家 1、2、5 和 6 都没有输掉任何比赛。
玩家 3 和 4 每个都输掉两场比赛。
因此，answer[0] = [1,2,5,6] 和 answer[1] = [] 。
提示：
1 <= matches.length <= 105
matches[i].length == 2
1 <= winneri, loseri <= 105
winneri != loseri
所有 matches[i] 互不相同
题解：
方法：哈希表
哈希表 cnt 用来记录每个玩家输掉的比赛场次。
遍历哈希表，将输掉 0 场比赛的玩家放入 ans[0]，将输掉 1 场比赛的玩家放入 ans[1]。
最后将 ans[0] 和 ans[1] 按照升序排序，返回结果。
// 定义一个名为Solution的类
class Solution {
// 定义一个名为findWinners的方法，接收一个二维整数数组matches作为参数
public List<List<Integer>> findWinners(int[][] matches) {
// 创建一个HashMap用于存储每个选手的比赛次数
Map<Integer, Integer> cnt = new HashMap<>();
// 遍历matches数组
for (var e : matches) {
// 如果e[0]不在cnt中，则将其值设为0
cnt.putIfAbsent(e[0], 0);
// 将e[1]的比赛次数加1，如果e[1]不存在，则将其值设为1
cnt.merge(e[1], 1, Integer::sum);
}
// 创建一个包含两个ArrayList的List，分别用于存储未输过和输过一次的选手编号
List<List<Integer>> ans = List.of(new ArrayList<>(), new ArrayList<>());
// 遍历cnt中的键值对
for (var e : cnt.entrySet()) {
// 如果比赛次数小于2，则将选手编号添加到对应的列表中
if (e.getValue() < 2) {
ans.get(e.getValue()).add(e.getKey());
}
}
// 对未输过和输过一次的选手编号列表进行排序
Collections.sort(ans.get(0));
Collections.sort(ans.get(1));
// 返回包含两个列表的结果
return ans;
}
}
23.找出最长等值子数组
题目链接：2831. 找出最长等值子数组
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。
示例 1：
输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优的方案是删除下标 2 和下标 4 的元素。
删除后，nums 等于 [1, 3, 3, 3] 。
最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
可以证明无法创建更长的等值子数组。
示例 2：
输入：nums = [1,1,2,2,1,1], k = 2
输出：4
解释：最优的方案是删除下标 2 和下标 3 的元素。
删除后，nums 等于 [1, 1, 1, 1] 。
数组自身就是等值子数组，长度等于 4 。
可以证明无法创建更长的等值子数组。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= nums.length
0 <= k <= nums.length
题解：
方法：滑动窗口
遍历输入列表，对于每个元素 x，将其索引减去该元素在 posLists[x] 中已有元素的数量，然后添加到 posLists[x] 中。。
遍历 posLists 中的每个列表，如果当前列表的长度小于等于答案，则跳过。否则，初始化左指针 left 为 0，遍历当前列表，如果右指针和左指针之间的距离大于 k，则移动左指针；更新答案为当前答案和右指针与左指针之间的距离加一的最大值。
class Solution {
// 定义一个方法，用于求解最长相等子数组的长度
public int longestEqualSubarray(List<Integer> nums, int k) {
int n = nums.size(); // 获取输入列表的长度
List<Integer>[] posLists = new ArrayList[n + 1]; // 创建一个长度为 n+1 的列表数组
Arrays.setAll(posLists, i -> new ArrayList<>()); // 初始化数组中的每个元素为一个新的空列表
for (int i = 0; i < n; i++) {
// 遍历输入列表
int x = nums.get(i); // 获取当前元素的值
posLists[x].add(i - posLists[x].size()); // 将当前元素的索引减去该元素在 posLists[x] 中已有元素的数量，然后添加到 posLists[x] 中
}
int ans = 0; // 初始化答案为 0
for (List<Integer> pos : posLists) {
// 遍历 posLists 中的每个列表
if (pos.size() <= ans) {
// 如果当前列表的长度小于等于答案，则跳过
continue;
}
int left = 0; // 初始化左指针为 0
for (int right = 0; right < pos.size(); right++) {
// 遍历当前列表
while (pos.get(right) - pos.get(left) > k) {
// 如果右指针和左指针之间的距离大于 k，则移动左指针
left++;
}
ans = Math.max(ans, right - left + 1); // 更新答案为当前答案和右指针与左指针之间的距离加一的最大值
}
}
return ans; // 返回答案
}
}
24.找出最具竞争力的子序列
题目链接：1673. 找出最具竞争力的子序列
给你一个整数数组 nums 和一个正整数 k ，返回长度为 k 且最具 竞争力 的 nums 子序列。
数组的子序列是从数组中删除一些元素（可能不删除元素）得到的序列。
在子序列 a 和子序列 b 第一个不相同的位置上，如果 a 中的数字小于 b 中对应的数字，那么我们称子序列 a 比子序列 b（相同长度下）更具 竞争力 。 例如，[1,3,4] 比 [1,3,5] 更具竞争力，在第一个不相同的位置，也就是最后一个位置上， 4 小于 5 。
示例 1：
输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的子序列集合 {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6]
最具竞争力。
示例 2：
输入：nums = [2,4,3,3,5,4,9,6], k = 4
输出：[2,3,3,4]
提示：
1 <= nums.length <= 105
0 <= nums[i] <= 109
1 <= k <= nums.length
题解：
方法：栈
我们从左到右遍历数组 nums，维护一个栈 stk，遍历过程中，如果当前元素 nums[i] 小于栈顶元素，且栈中元素个数加上 n−i 大于 k，则将栈顶元素出栈，直到不满足上述条件为止。此时如果栈中元素个数小于 k，则将当前元素入栈。遍历结束后，栈中元素即为所求。
class Solution {
public int[] mostCompetitive(int[] nums, int k) {
Deque<Integer> stk = new ArrayDeque<>();
int n = nums.length;
for (int i = 0; i < nums.length; ++i) {
while (!stk.isEmpty() && stk.peek() > nums[i] && stk.size() + n - i > k) {
stk.pop();
}
if (stk.size() < k) {
stk.push(nums[i]);
}
}
int[] ans = new int[stk.size()];
for (int i = ans.length - 1; i >= 0; --i) {
ans[i] = stk.pop();
}
return ans;
}
}
25.找出满足差值条件的下标 I
题目链接：2903. 找出满足差值条件的下标 I
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，以及整数 indexDifference 和整数 valueDifference 。
你的任务是从范围 [0, n - 1] 内找出 2 个满足下述所有条件的下标 i 和 j ：
abs(i - j) >= indexDifference 且
abs(nums[i] - nums[j]) >= valueDifference
返回整数数组 answer。如果存在满足题目要求的两个下标，则 answer = [i, j] ；否则，answer = [-1, -1] 。如果存在多组可供选择的下标对，只需要返回其中任意一组即可。
注意：i 和 j 可能 相等 。
示例 1：
输入：nums = [5,1,4,1], indexDifference = 2, valueDifference = 4
输出：[0,3]
解释：在示例中，可以选择 i = 0 和 j = 3 。
abs(0 - 3) >= 2 且 abs(nums[0] - nums[3]) >= 4 。
因此，[0,3] 是一个符合题目要求的答案。
[3,0] 也是符合题目要求的答案。
示例 2：
输入：nums = [2,1], indexDifference = 0, valueDifference = 0
输出：[0,0]
解释：
在示例中，可以选择 i = 0 和 j = 0 。
abs(0 - 0) >= 0 且 abs(nums[0] - nums[0]) >= 0 。
因此，[0,0] 是一个符合题目要求的答案。
[0,1]、[1,0] 和 [1,1] 也是符合题目要求的答案。
示例 3：
输入：nums = [1,2,3], indexDifference = 2, valueDifference = 4
输出：[-1,-1]
解释：在示例中，可以证明无法找出 2 个满足所有条件的下标。
因此，返回 [-1,-1] 。
提示：
1 <= n == nums.length <= 100
0 <= nums[i] <= 50
0 <= indexDifference <= 100
0 <= valueDifference <= 50
题解：
方法：双指针
class Solution {
public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {
int maxIdx = 0;
int minIdx = 0;
for (int j = indexDifference; j < nums.length; j++) {
int i = j - indexDifference;
if (nums[i] > nums[maxIdx]) {
maxIdx = i;
} else if (nums[i] < nums[minIdx]) {
minIdx = i;
}
if (nums[maxIdx] - nums[j] >= valueDifference) {
return new int[]{
maxIdx, j};
}
if (nums[j] - nums[minIdx] >= valueDifference) {
return new int[]{
minIdx, j};
}
}
return new int[]{
-1, -1};
}
}
26.找出第 K 大的异或坐标值
题目链接：1738. 找出第 K 大的异或坐标值
给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
示例 1：
输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
示例 2：
输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
示例 3：
输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
示例 4：
输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 106
1 <= k <= m * n
题解：
方法：二维前缀异或和
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int[] a = new int[m * n];
int[][] s = new int[m + 1][n + 1];
int idx = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j];
a[idx++] = s[i + 1][j + 1];
}
}
Arrays.sort(a);
return a[idx - k];
}
}
方法：列前缀异或和
public class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int[] a = new int[m * n];
int[] colSum = new int[n];
int i = 0;
for (int[] row : matrix) {
int s = 0;
for (int j = 0; j < row.length; j++) {
colSum[j] ^= row[j];
s ^= colSum[j];
a[i++] = s;
}
}
Arrays.sort(a);
return a[i - k];
}
}
