leetcode biweekly contest 98

周赛的题目确实越来越难了，质量有所提高，还是继续坚持。

6359. 替换一个数字后的最大差值

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字 替换 成另一个数字。

请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差位多少。

注意：

• 当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。
• Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
• Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
• 替换后得到的数字可以包含前导 0 。
• Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。

示例 1：

输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。

示例 2：

输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。

提示：

• 1 <= num <= 108

地址

https://leetcode.cn/contest/biweekly-contest-98/problems/maximum-difference-by-remapping-a-digit/

题意

直接模拟

思路

1. 简单题目，贪心法如下:

• 最大数即将从左向右第一位不为 $9$ 的数字全部变为 $9$ 即可；
• 最小数即将从左向右第一位不为 $0$ 的数字全部变为 $0$ 即可；
• 将二者结果相减即可；

2. 复杂度分析：

• 时间复杂度：$O(n + \log u)$，其中 $n$ 为数组的长度，$u$ 为数组中最大的元素。
• 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int minMaxDifference(int num) {
        string s = to_string(num);
        char c1 = -1, c2 = -1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '9' && c1 == -1) {
                c1 = s[i];
            }
            if (s[i] != '0' && c2 == -1) {
                c2 = s[i];
            }
        }
        string s1 = s;
        string s2 = s;
        for (int i = 0; i < s.size(); i++) {
            if (s2[i] == c2) {
                s2[i] = '0';
            }
        }
        if (c1 != -1) {
            for (int i = 0; i < s.size(); i++) {
                if (s1[i] == c1) {
                    s1[i] = '9';
                }
            }
        }
        int num1 = stoi(s1);
        int num2 = stoi(s2);
        return num1 - num2;
    }
};

6361. 修改两个元素的最小分数

给你一个下标从 0 开始的整数数组 nums 。

• nums 的 最小 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
• nums的 最大 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
• nums 的分数是 最大 得分与 最小 得分的和。

我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。

请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。

|x| 表示 x 的绝对值。

示例 1：

输入：nums = [1,4,3]
输出：0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。

示例 2：

输入：nums = [1,4,7,8,5]
输出：3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-332/problems/count-the-number-of-fair-pairs/
#### 题意
排序贪心
#### 思路
1. 贪心算法即可，我们可以取出两个数将其改为一样的数字，此时最小得分为 $0$，最大得分只能是 $(nums[n - 1] - nums[2], nums[n - 2] - nums[1], nums[n-3] - nums[0])$ 这三个数中的最小值，不存在比该最大值最小的其他可能。我们可以有以下几种修改：
+ 修改最大的两个数；
+ 修改最小的两个数；
+ 修改最大和最小数；
2. 复杂度分析：
+ 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度。排序需要的时间复杂度为 $O(n \log n)$。
+ 空间复杂度：$O(\log n)$，主要为排序需要空间。
#### 代码
+ 贪心

class Solution { public: int minimizeSum(vector<int>& nums) { int n = nums.size(); if (n <= 3) { return 0; } sort(nums.begin(), nums.end()); return min({nums[n - 1] - nums[2], nums[n - 2] - nums[1], nums[n-3] - nums[0]}); } };

6360. 最小无法得到的或值

给你一个下标从 0 开始的整数数组 nums 。

如果存在一些整数满足 0 <= index1 < index2 < ... < indexk < nums.length ，得到 nums[index1] | nums[index2] | ... | nums[indexk] = x ，那么我们说 x 是 可表达的 。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。

请你返回 nums 不可表达的 最小非零整数 。

示例 1：

输入：nums = [2,1]
输出：4
解释：1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。

示例 2：

输入：nums = [5,3,2]
输出：1
解释：1 是最小不可表达的数字。

提示：

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

地址

https://leetcode.cn/contest/weekly-contest-332/problems/substring-xor-queries/

题意

数学

思路

1. 首先结论为：最小的值一定为 $2^i$，$i \in[0,31]$；有以下提示：

• 首先我们知道 $1$ 和 $2$ 的数位上都只含有 $1$ 个 $1$，因此如果使得 $1$ 与 $2$ 可以生成，则 $1$ 与 $2$ 一定在数组中，此时 $3$ 一定可以生成；
• 如果 $4$ 不在数组中，则 $4$ 一定无法生成，否则 $5,6,7$ 均可以生成；
• 依次类推，最小且无法生成的数一定是 $2^i$；

2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n)$。
• 空间复杂度：时间复杂度为 $O(n)$。

代码

class Solution {
public:
    int minImpossibleOR(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> cnt;
        for (int i = 0; i < n; i++) {
           cnt.emplace(nums[i]);
        }
        for (int i = 0; i < 32; i++) {
            if (!cnt.count(1 << i)) {
                return 1 << i;
            }
        }
        return 0;
    }
};

6358. 更新数组后处理求和查询

给你两个下标从 0 开始的数组 nums1 和 nums2 ，和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作：

1. 操作类型 1 为 queries[i] = [1, l, r] 。你需要将 nums1 从下标 l 到下标 r 的所有 0 反转成 1 或将 1 反转成 0 。l 和 r 下标都从 0 开始。
2. 操作类型 2 为 queries[i] = [2, p, 0] 。对于 0 <= i < n 中的所有下标，令 nums2[i] = nums2[i] + nums1[i] * p 。
3. 操作类型 3 为 queries[i] = [3, 0, 0] 。求 nums2 中所有元素的和。

请你返回一个数组，包含所有第三种操作类型的答案。

示例 1：

输入：nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
输出：[3]
解释：第一个操作后 nums1 变为 [1,1,1] 。第二个操作后，nums2 变成 [1,1,1] ，所以第三个操作的答案为 3 。所以返回 [3] 。

示例 2：

输入：nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
输出：[5]
解释：第一个操作后，nums2 保持不变为 [5] ，所以第二个操作的答案是 5 。所以返回 [5] 。

提示：

• 1 <= nums1.length,nums2.length <= 105
• nums1.length = nums2.length
• 1 <= queries.length <= 105
• queries[i].length = 3
• 0 <= l <= r <= nums1.length - 1
• 0 <= p <= 106
• 0 <= nums1[i] <= 1
• 0 <= nums2[i] <= 109

地址

https://leetcode.cn/contest/weekly-contest-332/problems/subsequence-with-the-minimum-score/

题意

线段树

思路

1. 线段树的懒更新，感觉范围更新一直都是自己的弱项，每次约到线段树的题目都容易写错，真心需要针对线段树的懒更新的题目加强练习，确实非常容易出错的地方，这个题目基本上就是线段树的模板题目，确实没啥好讲的；
2. 每次更新时，我们只需计算 $nums1$ 中的数字的和为 $sum$，则每次更新查询后的数组的元素和增加为 $p \times sum$;
3. 复杂度分析：

• 时间复杂度：$O(m \log n)$，其中 $m$ 为查询的次数，$n$ 为数组的长度。
• 空间复杂度：$O(n)$。

代码

• 线段树：

  const int N = 1e5 * 4; struct node{ int l, r, sum; bool lazytag; }; node tree[N]; class NumArray { public: vector<int> nums; void build(int id, int l, int r){ tree[id].l = l; tree[id].r = r; tree[id].lazytag = false; if(l == r) { tree[id].sum = nums[l]; return; } int mid = (l + r) >> 1; build(2 * id, l, mid); build(2 * id + 1, mid + 1, r); tree[id].sum = tree[2 * id].sum + tree[2 * id + 1].sum; return; } /* lazytag：记录区间的修改情况 pushdown函数：下传懒标记，即将当前区间的修改情况下传到其左右孩子节点 */ // x:下传x节点的懒标记 void pushdown(int x) { if(tree[x].lazytag) { tree[2 * x].lazytag = !tree[2 * x].lazytag; tree[2 * x].sum = tree[2 * x].r - tree[2 * x].l + 1 - tree[2 * x].sum; tree[2 * x + 1].lazytag = !tree[2 * x + 1].lazytag; tree[2 * x + 1].sum = tree[2 * x + 1].r - tree[2 * x + 1].l + 1 - tree[2 * x + 1].sum; tree[x].lazytag = false; } } //区间修改 /* 1.如果节点区间完全包含于目标区间，则将节点的sum加上区间长度*修改情况 2.如果节点区间没有完全包含于目标区间，则先下传懒标记 3.如果这个区间的左儿子和目标区间有交集，那么搜索左儿子 4.如果这个区间的右儿子和目标区间有交集，那么搜索右儿子 */ void modify(int id, int l, int r) { //这里的k是增加的值 if(tree[id].l >= l && tree[id].r <= r){ tree[id].sum = (tree[id].r - tree[id].l + 1) - tree[id].sum; tree[id].lazytag = !tree[id].lazytag; return; } pushdown(id); int mid = (tree[id].l + tree[id].r) >> 1; if(tree[2 * id].r >= l) modify(2 * id, l, r); if(tree[2 * id + 1].l <= r) modify(2 * id + 1, l, r); tree[id].sum = tree[2 * id].sum + tree[2 * id + 1].sum; return; } //区间查询 int query(int id, int l, int r){ if(tree[id].l >= l && tree[id].r <= r) return tree[id].sum; if(tree[id].r < l || tree[id].l > r) return 0; pushdown(id); int s = 0; if(tree[2 * id].r >= l) s += query(2 * id, l, r); if(tree[2 * id + 1].l <= r) s += query(2 * id + 1, l, r); return s; } NumArray(vector<int>& num) { nums = num; build(1, 0, num.size() - 1); } int sumRange(int left, int right) { return query(1, left, right); } }; class Solution { public: vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) { int n = nums1.size(); int m = queries.size(); NumArray segtree(nums1); long long sum = accumulate(nums2.begin(), nums2.end(), 0LL); vector<long long> ans; for (int i = 0; i < m; i++) { if (queries[i][0] == 1) { int l = queries[i][1]; int r = queries[i][2]; segtree.modify(1, l, r); } else if (queries[i][0] == 2) { sum += (long long)segtree.sumRange(0, n - 1) * queries[i][1]; } else if (queries[i][0] == 3) { ans.emplace_back(sum); } } return ans; } };

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿