文章目录
- 双周赛98
- [6359. 替换一个数字后的最大差值](https://leetcode.cn/problems/maximum-difference-by-remapping-a-digit/)
- [6361. 修改两个元素的最小分数](https://leetcode.cn/problems/minimum-score-by-changing-two-elements/)
- 贪心+排序
- [6360. 最小无法得到的或值](https://leetcode.cn/problems/minimum-impossible-or/)
- [6358. 更新数组后处理求和查询](https://leetcode.cn/problems/handling-sum-queries-after-update/)
- 周赛333
- [6362. 合并两个二维数组 - 求和法](https://leetcode.cn/problems/merge-two-2d-arrays-by-summing-values/)
- [6365. 将整数减少到零需要的最少操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-an-integer-to-0/)
- 记忆化搜索
0x3f:从周赛中学算法 - 2022 年周赛题目总结(下篇)https://leetcode.cn/circle/discuss/WR1MJP/
- 模拟
- 技巧
- 动态规划
- 数据结构
- 图论
- 数学
- 思维题
双周赛98
6359. 替换一个数字后的最大差值
难度简单1
给你一个整数 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
class Solution {public int minMaxDifference(int num) {String str = num + "";String max = str, min = str;for(int i = 0; i < str.length(); i++){if(str.charAt(i) != '9'){max = str.replace(str.charAt(i),'9');break;}}for(int i = 0; i < str.length(); i++){if(str.charAt(i) != '0'){min = str.replace(str.charAt(i), '0');break;}}return Integer.parseInt(max) - Integer.parseInt(min);}
}
class Solution {public int minMaxDifference(int num) {String str = num + "";char a = str.charAt(0), b = ' ';boolean flag = false;for(int i = 0; i < str.length(); i++){char c = str.charAt(i);if(c != '9'){flag = true;b = c;break;}}String min = str.replace(a, '0');String max = flag ? str.replace(b, '9') : str;return Integer.parseInt(max) - Integer.parseInt(min);}
}
6361. 修改两个元素的最小分数
难度中等5
给你一个下标从 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
贪心+排序
class Solution {//排序 + 贪心,本质是求修改后数组的最大差最小是多少。//左边修改两个最小的变成第三小,右边修改两个大最大的变成第三大,左右各修改一个最大最小public int minimizeSum(int[] nums) {// 最小的得分和,就要求所有的数尽量的小Arrays.sort(nums);// 最小得分一定可以是0// 三种情况int ans = 0x7f7f7f7f;int n = nums.length;// 一头一尾ans = Math.min(ans, nums[n - 2] - nums[1]);// 两头ans = Math.min(ans, nums[n - 1] - nums[2]);// 两尾ans = Math.min(ans, nums[n - 3] - nums[0]);return ans;}
}
6360. 最小无法得到的或值
难度中等6
给你一个下标从 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
或操作越或越大
class Solution {public int minImpossibleOR(int[] nums) {// 脑经急转弯// 第一个不在nums中的2的幂// 如果2^1, ... , 2^k都在// 那么可以表示所有1...2^(k + 1) - 1的数Set<Integer> set = new HashSet<>();for(int i : nums){set.add(i);}for(int i = 0; i < 32; i++){if(!set.contains(1 << i)) return 1 << i;}return -1;}
}
6358. 更新数组后处理求和查询
难度困难5
给你两个下标从 0 开始的数组 nums1
和 nums2
,和一个二维数组 queries
表示一些操作。总共有 3 种类型的操作:
- 操作类型 1 为
queries[i] = [1, l, r]
。你需要将nums1
从下标l
到下标r
的所有0
反转成1
或将1
反转成0
。l
和r
下标都从 0 开始。 - 操作类型 2 为
queries[i] = [2, p, 0]
。对于0 <= i < n
中的所有下标,令nums2[i] = nums2[i] + nums1[i] * p
。 - 操作类型 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
//有错不想调试了,后面复习线段树
class Solution {/**操作类型1:lazy更新 : 0 表示不需要更新 != 0 表示需要更新*/public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {int n = nums1.length;List<Long> ans = new ArrayList<>();long sum = 0;for(int x :nums2) sum += x;buildTree(root, 0,n-1, nums1);for(int[] q : queries){if(q[0] == 1) update(root, 0, N, q[1], q[2]);else if(q[0] == 2) sum += q[1] * 1L * sum();else ans.add(sum);}return ans.stream().mapToLong(Long::valueOf).toArray();}class Node {Node left, right;int val, add;}private int N = (int) 1e9;private Node root = new Node();public void buildTree(Node node, int start, int end, int[] nums1) {// 到达叶子节点if (start == end) {node.val = nums1[start];return ;}int mid = (start + end) >> 1;node.left = new Node();node.right = new Node();buildTree(node.left, start, mid, nums1);buildTree(node.right, mid + 1, end, nums1);// 向上更新pushUp(node);}//初始值start和end是固定的0-N,l和r是要更新的区间,更新值为valpublic void update(Node node, int start, int end, int l, int r) {if (l <= start && end <= r) {//node.val += (end - start + 1) * val;node.val = end - start + 1 - node.val;node.add = 1;return;}int mid = (start + end) >> 1;pushDown(node, mid - start + 1, end - mid, mid);if (l <= mid) update(node.left, start, mid, l, r);if (r > mid) update(node.right, mid + 1, end, l, r);pushUp(node);}public int query(Node node, int start, int end, int l, int r) {if (l <= start && end <= r) return node.val;int mid = (start + end) >> 1, ans = 0;pushDown(node, mid - start + 1, end - mid, mid);if (l <= mid) ans += query(node.left, start, mid, l, r);if (r > mid) ans += query(node.right, mid + 1, end, l, r);return ans;}private void pushUp(Node node) {node.val = node.left.val + node.right.val;}private void pushDown(Node node, int leftNum, int rightNum, int mid) {if (node.left == null) node.left = new Node();if (node.right == null) node.right = new Node();if (node.add == 0) return ;node.left.val += mid - leftNum - node.val;node.right.val += rightNum - mid - node.val;// 对区间进行「加减」的更新操作,下推懒惰标记时需要累加起来,不能直接覆盖node.left.add = 1;node.right.add = 1;node.add = 0;}private int sum(){return root.val;}
}
周赛333
6362. 合并两个二维数组 - 求和法
难度简单2
给你两个 二维 整数数组 nums1
和 nums2.
nums1[i] = [idi, vali]
表示编号为idi
的数字对应的值等于vali
。nums2[i] = [idi, vali]
表示编号为idi
的数字对应的值等于vali
。
每个数组都包含 互不相同 的 id ,并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组,并符合下述条件:
- 只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
- 每个 id 在结果数组中 只能出现一次 ,并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ,则认为其对应的值等于
0
。
返回结果数组。返回的数组需要按 id 以递增顺序排列。
示例 1:
输入:nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
输出:[[1,6],[2,3],[3,2],[4,6]]
解释:结果数组中包含以下元素:
- id = 1 ,对应的值等于 2 + 4 = 6 。
- id = 2 ,对应的值等于 3 。
- id = 3 ,对应的值等于 2 。
- id = 4 ,对应的值等于5 + 1 = 6 。
示例 2:
输入:nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
输出:[[1,3],[2,4],[3,6],[4,3],[5,5]]
解释:不存在共同 id ,在结果数组中只需要包含每个 id 和其对应的值。
提示:
1 <= nums1.length, nums2.length <= 200
nums1[i].length == nums2[j].length == 2
1 <= idi, vali <= 1000
- 数组中的 id 互不相同
- 数据均按 id 以严格递增顺序排列
class Solution {public int[][] mergeArrays(int[][] nums1, int[][] nums2) {List<int[]> list = new ArrayList<>();int i = 0, j = 0;while(i < nums1.length && j < nums2.length){int key = 0, val = 0;if(nums1[i][0] == nums2[j][0]){val = nums1[i][1] + nums2[j][1];key = nums1[i][0];i++; j++;}else if(nums1[i][0] < nums2[j][0]){val = nums1[i][1];key = nums1[i][0];i++;}else{val = nums2[j][1];key = nums2[j][0];j++;}list.add(new int[]{key, val});}if(i != nums1.length){while(i != nums1.length){list.add(new int[]{nums1[i][0], nums1[i][1]});i++;}}if(j != nums2.length){while(j != nums2.length){list.add(new int[]{nums2[j][0], nums2[j][1]});j++;}}int[][] res = new int[list.size()][2];for(int k = 0; k < list.size(); k++){res[k][0] = list.get(k)[0];res[k][1] = list.get(k)[1];}return res;}
}
6365. 将整数减少到零需要的最少操作数
难度简单11
给你一个正整数 n
,你可以执行下述操作 任意 次:
n
加上或减去2
的某个 幂
返回使 n
等于 0
需要执行的 最少 操作数。
如果 x == 2i
且其中 i >= 0
,则数字 x
是 2
的幂。
示例 1:
输入:n = 39
输出:3
解释:我们可以执行下述操作:
- n 加上 20 = 1 ,得到 n = 40 。
- n 减去 23 = 8 ,得到 n = 32 。
- n 减去 25 = 32 ,得到 n = 0 。
可以证明使 n 等于 0 需要执行的最少操作数是 3 。
示例 2:
输入:n = 54
输出:3
解释:我们可以执行下述操作:
- n 加上 21 = 2 ,得到 n = 56 。
- n 加上 23 = 8 ,得到 n = 64 。
- n 减去 26 = 64 ,得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。
提示:
1 <= n <= 105
记忆化搜索
class Solution {Map<Integer, Integer> map = new HashMap<>();public int minOperations(int n) {return dfs(n);}public int dfs(int x){if((x & (x-1)) == 0) return 1;if(map.containsKey(x)) return map.get(x);int lowbit = x & -x;int cur = 1 + Math.min(dfs(x + lowbit), dfs(x - lowbit));map.put(x, cur);return cur;}
}
,得到 n = 0 。
使 n 等于 0 需要执行的最少操作数是 3 。
**提示:**- `1 <= n <= 105`### 记忆化搜索```java
class Solution {Map<Integer, Integer> map = new HashMap<>();public int minOperations(int n) {return dfs(n);}public int dfs(int x){if((x & (x-1)) == 0) return 1;if(map.containsKey(x)) return map.get(x);int lowbit = x & -x;int cur = 1 + Math.min(dfs(x + lowbit), dfs(x - lowbit));map.put(x, cur);return cur;}
}