LeetCode315 周赛

2441. 与对应负数同时存在的最大正整数

给你一个 不包含 任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。

返回正整数 k ，如果不存在这样的整数，返回 -1 。

提示：

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• nums[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^5
• 1 <= 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^5
• 1 <= 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总讲解后一下就理解了。有点类似之前做过的某道题，可以根据一些点将大区间拆分成多个小区间，再单独对每个小区间进行求解。