这周双周赛，我觉得题目不是很好。2，3题都是脑经急转弯，最后一题也过于模版。
6359. Maximum Difference by Remapping a Digit
给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字 替换 成另一个数字。
请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差位多少。
注意：
- 当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。
- Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
- Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
- 替换后得到的数字可以包含前导 0 。
- Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。
测试样例
输入：nums = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。
解答：max就是寻找第一个非9的数字，并map为9。min就是把最大位map成0
class Solution {
public int minMaxDifference(int num) {
String tmp = String.valueOf(num);
char map = 0, minMap = tmp.charAt(0);
for (int i = 0; i < tmp.length(); ++i) {
if (tmp.charAt(i) != '9') {
map = tmp.charAt(i);
break;
}
}
int max = 0, min = 0;
for (int i = 0; i < tmp.length(); ++i) {
if (tmp.charAt(i) == map) {
max = max * 10 + 9;
} else {
max = max * 10 + tmp.charAt(i) - '0';
}
if (tmp.charAt(i) == minMap) {
min = min * 10;
} else {
min = min * 10 + tmp.charAt(i) - '0';
}
}
return max - min;
}
}6361. Minimum Score by Changing Two Elements
给你一个下标从 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 的绝对值。
测试样例：
输入：nums = [1,4,3]
输出：0
解释：
将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。
解答: 如果数组长度小于3，直接返回0。
由于最多可以替换2个数，那么min必然可以做到0。重点就是寻找最大的绝对值。其实也很简单。排序之后，我们可以找到最大值和最小值。那么最优的策略就是替换队头或者队尾或者队头队尾各替换一个，就能找到最小的最大绝对差值。
代码没有优化到最佳，直接使用了排序。
class Solution {
public int minimizeSum(int[] nums) {
if (nums.length <= 3) return 0;
Arrays.sort(nums);
return Math.min(nums[nums.length - 1] - nums[2], Math.min(nums[nums.length - 3] - nums[0], nums[nums.length - 2] - nums[1]));
}
}6360. Minimum Impossible OR
给你一个下标从 0 开始的整数数组 nums 。
如果存在一些整数满足 0 <= index1 < index2 < ... < indexk < nums.length ，得到 nums[index1] | nums[index2] | ... | nums[indexk] = x ，那么我们说 x 是 可表达的 。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。
请你返回 nums 不可表达的 最小非零整数 。
测试样例：
输入：nums = [2,1]
输出：4
解释：
1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。
解答: 这道题又是脑经急转弯。其实本质是寻找第一个不存在的，2的倍数。
可以看看简单的例子：
- 如果1，2存在，那么小于4的数字必然都能组合出来
- 如果1，2，4存在，那么小于8的数字都能组合出来
- 以此类推...
class Solution {
public int minImpossibleOR(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i : nums) {
set.add(i);
}
for (int i = 1; i < Integer.MAX_VALUE; i = i * 2) {
if (!set.contains(i)) {
return i;
}
}
return -1;
}
}6358. Handling Sum Queries After Update
给你两个下标从 0 开始的数组 nums1 和 nums2 ，和一个二维数组 queries 表示一些操作。总共有 3 种类型的操作：
- 操作类型 1 为 queries[i] = [1, l, r] 。你需要将 nums1 从下标 l 到下标 r 的所有 0 反转成 1 或将 1 反转成 0 。l 和 r 下标都从 0 开始。
1.操作类型 2 为 queries[i] = [2, p, 0] 。对于 0 <= i < n 中的所有下标，令 nums2[i] = nums2[i] + nums1[i] * p 。
1.操作类型 3 为 queries[i] = [3, 0, 0] 。求 nums2 中所有元素的和。
请你返回一个数组，包含所有第三种操作类型的答案。测试样例：
输入：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] 。
解答：利用惰性传播的线段数的模板题。如果你会惰性传播的线段数，那么稍微换个思路，如果对一个范围内的nums1进行1操作，那么就等于这个范围内长度 - 原始的sum。
操作2，可以通过简单的累和计算得到。
class Solution {
class LazySegmentTree {
int MAX;
int[] tree;
int[] lazy;
int len;
private void updateRangeUtil(int si, int ss, int se, int us,
int ue) {
if (lazy[si] != 0) {
tree[si] = (se - ss + 1) - tree[si];
if (ss != se) {
lazy[si * 2 + 1] ^= lazy[si];
lazy[si * 2 + 2] ^= lazy[si];
}
lazy[si] = 0;
}
if (ss > se || ss > ue || se < us)
return;
if (ss >= us && se <= ue) {
tree[si] = (se - ss + 1) - tree[si];
if (ss != se) {
lazy[si * 2 + 1] ^= 1;
lazy[si * 2 + 2] ^= 1;
}
return;
}
int mid = (ss + se) / 2;
updateRangeUtil(si * 2 + 1, ss, mid, us, ue);
updateRangeUtil(si * 2 + 2, mid + 1, se, us, ue);
tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2];
}
public void updateRange(int us, int ue) {
updateRangeUtil(0, 0, len - 1, us, ue);
}
private int getSumUtil(int ss, int se, int qs, int qe, int si) {
if (lazy[si] != 0) {
tree[si] = (se - ss + 1) - tree[si];
if (ss != se) {
lazy[si * 2 + 1] ^= 1;
lazy[si * 2 + 2] ^= 1;
}
lazy[si] = 0;
}
if (ss > se || ss > qe || se < qs)
return 0;
if (ss >= qs && se <= qe)
return tree[si];
int mid = (ss + se) / 2;
return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
}
public int getSum(int qs, int qe) {
if (qs < 0 || qe > len - 1 || qs > qe) {
return -1;
}
return getSumUtil(0, len - 1, qs, qe, 0);
}
private void constructSTUtil(int arr[], int ss, int se, int si) {
if (ss > se)
return;
if (ss == se) {
tree[si] = arr[ss];
return;
}
int mid = (ss + se) / 2;
constructSTUtil(arr, ss, mid, si * 2 + 1);
constructSTUtil(arr, mid + 1, se, si * 2 + 2);
tree[si] = tree[si * 2 + 1] + tree[si * 2 + 2];
}
public void constructST(int[] arr) {
MAX = findMax(0, arr.length) + 1;
len = arr.length;
tree = new int[MAX];
lazy = new int[MAX];
constructSTUtil(arr, 0, len - 1, 0);
}
private int findMax(int si, int remain) {
if (remain == 1) {
return si;
} else {
return Math.max(findMax(si * 2 + 1, remain - remain / 2), findMax(si * 2 + 2, remain / 2));
}
}
}
public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {
LazySegmentTree tree = new LazySegmentTree();
tree.constructST(nums1);
long sum = 0;
for (int n : nums2) {
sum += n;
}
List<Long> res = new ArrayList<>();
for (int[] q : queries) {
if (q[0] == 1) {
tree.updateRange(q[1], q[2]);
} else if (q[0] == 2) {
long t = q[1];
sum = sum + tree.getSum(0, nums1.length - 1) * t;
} else {
res.add(sum);
}
}
long[] arr = new long[res.size()];
for (int i = 0; i < arr.length; ++i) {
arr[i] = res.get(i);
}
return arr;
}
}