🏆 第 315 场力扣周赛

最后一题想歪了，写麻烦了

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

显示英文描述
我的提交返回竞赛

• 通过的用户数5165
• 尝试过的用户数5232
• 用户总通过次数5245
• 用户总提交次数7285
• 题目难度Easy

给你一个 不包含 任何零的整数数组 nums ，找出自身与对应的负数都在数组中存在的最大正整数 k 。
返回正整数_ _k ，如果不存在这样的整数，返回 -1 。

示例 1：
输入：nums = [-1,2,-3,3] 输出：3 解释：3 是数组中唯一一个满足题目要求的 k 。
示例 2：
输入：nums = [-1,10,6,7,-7,1] 输出：7 解释：数组中存在 1 和 7 对应的负数，7 的值更大。
示例 3：
输入：nums = [-10,8,6,7,-2,-3] 输出：-1 解释：不存在满足题目要求的 k ，返回 -1 。

提示：

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• nums[i] != 0

思路：哈希

class Solution {
    public int findMaxK(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 0;
        for (int x : nums) set.add(x);
        for (int x : set) {
            if (set.contains(-x))
                max = Math.max(max, x);
        }
        return max == 0 ? -1 : max;
    }
}

6205. 反转之后不同整数的数目

显示英文描述
我的提交返回竞赛

• 通过的用户数4878
• 尝试过的用户数5017
• 用户总通过次数4965
• 用户总提交次数6595
• 题目难度Medium

给你一个由 正 整数组成的数组 nums 。
你必须取出数组中的每个整数，反转其中每个数位，并将反转后得到的数字添加到数组的末尾。这一操作只针对 nums 中原有的整数执行。
返回结果数组中 不同 整数的数目。

示例 1：
输入：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）。
示例 2：
输入：nums = [2,2,2] 输出：1 解释：反转每个数字后，结果数组是 [2,2,2,2,2,2] 。 数组中不同整数的数目为 1（数字 2）。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106

思路：哈希

class Solution {
    public int countDistinctIntegers(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
            set.add(reverse(x));
        }
        return set.size();
    }
    int reverse(int x) {
        int res = 0;
        while (x > 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

6219. 反转之后的数字和

给你一个 非负 整数 num 。如果存在某个 非负 整数 k 满足 k + reverse(k) = num ，则返回 true ；否则，返回_ _false 。
reverse(k) 表示 k 反转每个数位后得到的数字。

示例 1：
输入：num = 443 输出：true 解释：172 + 271 = 443 ，所以返回 true 。
示例 2：
输入：num = 63 输出：false 解释：63 不能表示为非负整数及其反转后数字之和，返回 false 。
示例 3：
输入：num = 181 输出：true 解释：140 + 041 = 181 ，所以返回 true 。注意，反转后的数字可能包含前导零。

提示：

• 0 <= num <= 105

思路：暴力

class Solution {
    public boolean sumOfNumberAndReverse(int num) {
        for (int x = 0; x <= num; x++) {
            if (x + reverse(x) == num)
                return true;
        }
        return false;
    }
    int reverse(int x) {
        int res = 0;
        while (x > 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

6207. 统计定界子数组的数目

显示英文描述
我的提交返回竞赛

• 通过的用户数942
• 尝试过的用户数2456
• 用户总通过次数1113
• 用户总提交次数5562
• 题目难度Hard

给你一个整数数组 nums 和两个整数 minK 以及 maxK 。
nums 的定界子数组是满足下述条件的一个子数组：

• 子数组中的 最小值 等于 minK 。
• 子数组中的 最大值 等于 maxK 。

返回定界子数组的数目。
子数组是数组中的一个连续部分。

示例 1：
输入：nums = [1,3,5,2,7,5], minK = 1, maxK = 5 输出：2 解释：定界子数组是 [1,3,5] 和 [1,3,5,2] 。
示例 2：
输入：nums = [1,1,1,1], minK = 1, maxK = 1 输出：10 解释：nums 的每个子数组都是一个定界子数组。共有 10 个子数组。

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i], minK, maxK <= 106

思路：贪心 + 双指针，线段树

class Solution {
    int[] nums;
    int n;
    int N = 100010;
    Node[] tr = new Node[4 * N];
    int minK, maxK;
    public long countSubarrays(int[] nums, int minK, int maxK) {
        n = nums.length;
        this.minK = minK;
        this.maxK = maxK;
        this.nums = nums;
        build(1, 1, nums.length);
        for (int i = 1; i <= n; i++) {
            modify(1, i, nums[i - 1]);
        }
        // System.out.println(query(1, 7, 10)[1]);
        long c = 0;
        int pre = 0;
        for (int i = 1; i <= n; i++) {
            if (nums[i - 1] < minK || nums[i - 1] > maxK) {
                pre = i;
                continue;
            } else {
                int l = pre + 1, r = i;
                int[] v = query(1, l, r);
                if (v[0] != maxK || v[1] != minK) continue;
                // int minIdx = deal1(l, r);
                // int maxIdx = deal2(l, r);
                // l = Math.min(minIdx, maxIdx);
                while (l < r) {
                    int mid = l + r + 1 >> 1;
                    int[] t = query(1, mid, i);
                    if (t[0] != maxK || t[1] != minK)
                        r = mid - 1;
                    else l = mid;
                }
                // System.out.println(i + " " + r);
                c += l - pre;
            }
        }
        return c;
    }
    int deal1(int l, int r) {
        while (l < r) {
            int mid = l + r + 1 >> 1;
            int[] t = query(1, mid, r);
            if (t[1] == minK)
                l = mid;
            else r = mid - 1;
        }
        return l;
    }
    int deal2(int l, int r) {
        while (l < r) {
            int mid = l + r + 1 >> 1;
            int[] t = query(1, mid, r);
            if (t[0] == maxK)
                l = mid;
            else r = mid - 1;
        }
        return l;
    }
    void build(int u, int l, int r) {
        tr[u] = new Node(l, r);
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void modify(int u, int idx, int x) {
        if (tr[u].l == idx && tr[u].r == idx) {
            tr[u].max = Math.max(x, tr[u].max);
            tr[u].min = Math.min(x, tr[u].min);
        } else {
            int mid = tr[u].l + tr[u].r >> 1;
            if (idx <= mid) modify(u << 1, idx, x);
            else modify(u << 1 | 1, idx, x);
            pushup(u);
        }
    }
    void pushup(int u) {
        tr[u].max = Math.max(tr[u << 1].max, tr[u << 1 | 1].max);
        tr[u].min = Math.min(tr[u << 1].min, tr[u << 1 | 1].min);
    }
    int[] query(int u, int l, int r) {
        if (tr[u].l >= l && r >= tr[u].r)
            return new int[]{tr[u].max, tr[u].min};
        int mid = tr[u].l + tr[u].r >> 1;
        // max, min
        int[] res = {-0x3f3f3f3f, 0x3f3f3f3f};
        if (l <= mid) res = query(u << 1, l, r);
        if (r > mid) {
            int[] t = query(u << 1 | 1, l, r);
            res[0] = Math.max(res[0], t[0]);
            res[1] = Math.min(res[1], t[1]);
        }
        return res;
    }
}
class Node {
    int l, r;
    int max = -0x3f3f3f3f;
    int min = 0x3f3f3f3f;
    Node(int l, int r) {
        this.l = l;
        this.r = r;
    }
}

class Solution {
    public long countSubarrays(int[] nums, int minK, int maxK) {
        long c = 0;
        int n = nums.length;
        int pre = -1, max = -1, min = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] < minK || nums[i] > maxK) {
                pre = i;
                max = min = -1;
            } else {
                if (max == -1) max = i;
                else max = nums[i] >= nums[max] ? i : max;
                if (min == -1) min = i;
                else min = nums[i] <= nums[min] ? i : min;
                // System.out.println(i + " " + max + " " + min);
                if (nums[max] == maxK && nums[min] == minK) {
                    c += Math.min(max, min) - pre;
                }
            }
        }
        return c;
    }
}