LeetCode315 周赛
2441. 与对应负数同时存在的最大正整数
给你一个 不包含 任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。
返回正整数 k ，如果不存在这样的整数，返回 -1 。
提示：
1 <= nums.length <= 1000-1000 <= nums[i] <= 1000nums[i] != 0
示例
输入：nums = [-1,2,-3,3]
输出：3
解释：3 是数组中唯一一个满足题目要求的 k 。
思路
简单题，类似两数之和。用一个哈希表记录下出现过的数即可。
// C++
class Solution {
public:
int findMaxK(vector<int>& nums) {
unordered_set<int> s;
int ans = -1;
for (auto &v : nums) {
if (s.count(-v)) ans = max(ans, abs(v));
s.insert(v);
}
return ans;
}
};
2442. 反转之后不同整数的数目
给你一个由 正 整数组成的数组 nums 。
你必须取出数组中的每个整数，反转其中每个数位，并将反转后得到的数字添加到数组的末尾。这一操作只针对 nums 中原有的整数执行。
返回结果数组中 不同 整数的数目。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^6
示例
输入：nums = [1,13,10,12,31]
输出：6
解释：反转每个数字后，结果数组是 [1,13,10,12,31,1,31,1,21,13] 。
反转后得到的数字添加到数组的末尾并按斜体加粗表示。注意对于整数 10 ，反转之后会变成 01 ，即 1 。
数组中不同整数的数目为 6（数字 1、10、12、13、21 和 31）。
思路
直接对每个数进行反转，并全部放到一个set中做去重。
// C++
class Solution {
public:
int reverse(int x) {
int res = 0;
while (x) {
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
int countDistinctIntegers(vector<int>& nums) {
unordered_set<int> s;
for (auto& v : nums) {
s.insert(v);
s.insert(reverse(v));
}
return s.size();
}
};
2443. 反转之后的数字和
给你一个 非负 整数 num 。如果存在某个 非负 整数 k 满足 k + reverse(k) = num ，则返回 true ；否则，返回 false 。
reverse(k) 表示 k 反转每个数位后得到的数字。
提示
0 <= num <= 10^5
示例
输入：num = 443
输出：true
解释：172 + 271 = 443 ，所以返回 true 。
思路
周赛当晚想了很久，观察并找规律。最后还是没有通过。今天重做，根据数据范围10^5，发现直接简单的暴力就能过。
// C++
class Solution {
public:
int reverse(int x) {
int res = 0;
while (x) {
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
bool sumOfNumberAndReverse(int num) {
for (int i = 0; i <= num; i++) {
if (i + reverse(i) == num) return true;
}
return false;
}
};
这道题如果将数据范围提高到 10^9，则用暴力会超时。可以折半枚举，只枚举一半的数位，则另一半的数为也一并会确定下来了（因为将数字进行reverse后相加，随着前一半数位的确定，后一半的数位也会随之确定）。
还有一种递归的解法，有点动态规划的思路在里面，反复看了几次看不太懂，便作罢。这里贴个链接，方便日后再来回看。
2444. 统计定界子数组的数目
给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：
- 子数组中的 最小值 等于
minK。 - 子数组中的 最大值 等于
maxK。
返回定界子数组的数目。
子数组是数组中的一个连续部分。
提示：
2 <= nums.length <= 10^51 <= nums[i], minK, maxK <= 10^6
示例
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5
输出：2
解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。
思路
一个连续的子数组内，所有数都必须在区间[minK, maxK]以内。那么只要某个数x不在上述区间内，则满足条件的子数组不可能跨越x这个位置。则我们可以先找出不在区间[minK, maxK]内的那些数字，然后根据这些数字将整个数组划分成若干个子区间，再对每个子区间单独求解即可。
对某个子区间，区间内所有数都在[minK, maxK]范围内。对于某个位置i，我们往左找到最近的j，满足[j, i]内存在minK和maxK，这意味着，若j再往右走一步，则唯一的一个minK或maxK会被移出区间，即[j + 1, i]不满足条件。那么对于以i作为右端点的子区间，其左端点都一定要<= j，才能满足条件，所以以i为右端点的区间，共有j + 1个。并且对于所有> i的右端点，距离其最近的左端点一定是>= j的，这样随着i往右移动，j也只能往右移动，而不会走回头路。所以可以用双指针算法。
// C++
typedef long long LL;
class Solution {
public:
long long countSubarrays(vector<int>& nums, int minK, int maxK) {
int n = nums.size();
// 定义一个函数
auto f = [&](int l, int r) -> LL {
if (l > r) return 0;
LL res = 0;
int smin = 0, smax = 0; // minK和maxK出现的次数
for (int i = l, j = l; i <= r; i++) {
if (nums[i] == minK) smin++;
if (nums[i] == maxK) smax++;
if (smin && smax) {
// 当minK和maxK都出现后, 尝试右移j
while (smin && smax) {
if (nums[j] == minK) smin--;
if (nums[j] == maxK) smax--;
j++;
}
j--; // 恢复j
if (nums[j] == minK) smin++;
if (nums[j] == maxK) smax++;
// 对于此i, 找到了其左侧最近的j
res += j - l + 1;
}
}
return res;
};
// 遍历并进行拆分
LL ans = 0;
for (int i = 0, last = 0; i < n; i++) {
if (nums[i] < minK || nums[i] > maxK) {
// cut off
ans += f(last, i - 1);
last = i + 1;
} else if (i == n - 1) {
// 最后一个位置
ans += f(last, i);
}
}
return ans;
}
};
总结
这场周赛，只做出2题，WHAT A SHAME！掉大分！
T3一直在观察找规律，坐牢直到比赛结束。没有注意到数据范围其实比较小，可以直接用暴力来做。可惜了。
另外T3在数据范围比较大的时候，注意需要用另一种方法来做（双指针+动态规划+DFS），题解看的我脑壳疼，之后再慢慢啃了。
T3这一类可以都归结到数位统计这一大类问题中，事后可以多刷刷相关题目。另外一道类似的题目（升级版）-> 镜像拆分
另外，T4难度没有特别大，听了y总讲解后一下就理解了。有点类似之前做过的某道题，可以根据一些点将大区间拆分成多个小区间，再单独对每个小区间进行求解。