周赛379（排序、分类讨论、记忆化搜索(动态规划)）

文章目录

周赛379
- [3000. 对角线最长的矩形的面积](https://leetcode.cn/problems/maximum-area-of-longest-diagonal-rectangle/)
- - 排序
- [3001. 捕获黑皇后需要的最少移动次数](https://leetcode.cn/problems/minimum-moves-to-capture-the-queen/)
- - 分类讨论
- [3002. 移除后集合的最多元素数](https://leetcode.cn/problems/maximum-size-of-a-set-after-removals/)
- - 分类讨论
- [3003. 执行操作后的最大分割数量](https://leetcode.cn/problems/maximize-the-number-of-partitions-after-operations/)
- - 记忆化搜索（动态规划）

周赛379

3000. 对角线最长的矩形的面积

简单

给你一个下标从 0 开始的二维整数数组 dimensions。

对于所有下标 i（0 <= i < dimensions.length），dimensions[i][0] 表示矩形 i 的长度，而 dimensions[i][1] 表示矩形 i 的宽度。

返回对角线最长的矩形的面积。如果存在多个对角线长度相同的矩形，返回面积最大的矩形的面积。

示例 1：

输入：dimensions = [[9,3],[8,6]]
输出：48
解释：
下标 = 0，长度 = 9，宽度 = 3。对角线长度 = sqrt(9 * 9 + 3 * 3) = sqrt(90) ≈ 9.487。
下标 = 1，长度 = 8，宽度 = 6。对角线长度 = sqrt(8 * 8 + 6 * 6) = sqrt(100) = 10。
因此，下标为 1 的矩形对角线更长，所以返回面积 = 8 * 6 = 48。

示例 2：

输入：dimensions = [[3,4],[4,3]]
输出：12
解释：两个矩形的对角线长度相同，为 5，所以最大面积 = 12。

提示：

1 <= dimensions.length <= 100
dimensions[i].length == 2
1 <= dimensions[i][0], dimensions[i][1] <= 100

排序

class Solution {public int areaOfMaxDiagonal(int[][] dimensions) {Arrays.sort(dimensions, (a, b) -> (b[0]*b[0]+b[1]*b[1]) == (a[0]*a[0]+a[1]*a[1]) ? b[0]*b[1] - a[0]*a[1] :  (b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1]));return dimensions[0][0] * dimensions[0][1];}
}

3001. 捕获黑皇后需要的最少移动次数

中等

现有一个下标从 0 开始的 8 x 8 棋盘，上面有 3 枚棋子。

给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：

(a, b) 表示白色车的位置。
(c, d) 表示白色象的位置。
(e, f) 表示黑皇后的位置。

假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。

请注意：

车可以向垂直或水平方向移动任意数量的格子，但不能跳过其他棋子。
象可以沿对角线方向移动任意数量的格子，但不能跳过其他棋子。
如果车或象能移向皇后所在的格子，则认为它们可以捕获皇后。
皇后不能移动。

示例 1：

输入：a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
输出：2
解释：将白色车先移动到 (1, 3) ，然后移动到 (2, 3) 来捕获黑皇后，共需移动 2 次。
由于起始时没有任何棋子正在攻击黑皇后，要想捕获黑皇后，移动次数不可能少于 2 次。

示例 2：

输入：a = 5, b = 3, c = 3, d = 4, e = 5, f = 2
输出：1
解释：可以通过以下任一方式移动 1 次捕获黑皇后：
- 将白色车移动到 (5, 2) 。
- 将白色象移动到 (5, 2) 。

提示：

1 <= a, b, c, d, e, f <= 8
两枚棋子不会同时出现在同一个格子上。

分类讨论

https://leetcode.cn/problems/minimum-moves-to-capture-the-queen/

class Solution {/**答案不是1就是2如果车能直接攻击到皇后 -> 1如果象能直接攻击到皇后 -> 1*/public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {if ((a == e && (c != a || canReach(b, d, f))) || (b == f && (d != b || canReach(a, c, e)))) {return 1;} else if ((c - e == d - f && (a - e != b - f || canReach(c, a, e))) || (c - e == f - d && (a - e != f - b || canReach(c, a, e)))) {return 1;} else {return 2;}}public boolean canReach(int source, int obstacle, int target) {int minPos = Math.min(source, target), maxPos = Math.max(source, target);return obstacle < minPos || obstacle > maxPos;}
}

3002. 移除后集合的最多元素数

中等

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们的长度都是偶数 n 。

你必须从 nums1 中移除 n / 2 个元素，同时从 nums2 中也移除 n / 2 个元素。移除之后，你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。

返回集合 s可能的最多包含多少元素。

示例 1：

输入：nums1 = [1,2,1,2], nums2 = [1,1,1,1]
输出：2
解释：从 nums1 和 nums2 中移除两个 1 。移除后，数组变为 nums1 = [2,2] 和 nums2 = [1,1] 。因此，s = {1,2} 。
可以证明，在移除之后，集合 s 最多可以包含 2 个元素。

示例 2：

输入：nums1 = [1,2,3,4,5,6], nums2 = [2,3,2,3,2,3]
输出：5
解释：从 nums1 中移除 2、3 和 6 ，同时从 nums2 中移除两个 3 和一个 2 。移除后，数组变为 nums1 = [1,4,5] 和 nums2 = [2,3,2] 。因此，s = {1,2,3,4,5} 。
可以证明，在移除之后，集合 s 最多可以包含 5 个元素。

示例 3：

输入：nums1 = [1,1,2,2,3,3], nums2 = [4,4,5,5,6,6]
输出：6
解释：从 nums1 中移除 1、2 和 3 ，同时从 nums2 中移除 4、5 和 6 。移除后，数组变为 nums1 = [1,2,3] 和 nums2 = [4,5,6] 。因此，s = {1,2,3,4,5,6} 。
可以证明，在移除之后，集合 s 最多可以包含 6 个元素。

提示：

n == nums1.length == nums2.length
1 <= n <= 2 * 104
n是偶数。
1 <= nums1[i], nums2[i] <= 109

分类讨论

https://leetcode.cn/problems/maximum-size-of-a-set-after-removals/solutions/2594380/tan-xin-pythonjavacgo-by-endlesscheng-ymuh/

class Solution {/** 从移除的角度思考设 nums1 中有 n1 个不同的元素， nums2 中有 n2 个不同元素，他们的交集有 common 个元素如果不移除任何元素，nums1 和 nums2 的并集一共有 n1 + n2 - common 个不同元素我们可以先移除每个元素中重复的元素，在考虑从剩下的数中移除元素设 m = n/2， 对于 nums1 来说，如果 n1 > m, 先从交集中移除元素如果交集元素少，那么全部移除， 即移除 common个元素如果交集元素多，那么移除交集中的 n1-m 个元素，就可以让 n1 = m即从交集中移除 min(n1-m, common) 个元素移除后，如果n1仍然大于m，则必须把ans 减少 n1-m*/public int maximumSetSize(int[] nums1, int[] nums2) {Set<Integer> s1 = new HashSet<>();Set<Integer> s2 = new HashSet<>();for(int x : nums1) s1.add(x);int common = 0;for(int x : nums2){// 判断两个set有多少个重叠的元素if(s2.add(x) && s1.contains(x)){common++;}}int n1 = s1.size();int n2 = s2.size();int ans = n1 + n2 - common;int m = nums1.length / 2;if(n1 > m){ // 先从交集中移除元素// 只移除交集元素时，最多能移除 mn 个int mn = Math.min(n1 - m, common);n1 -= mn;common -= mn;// 移除后，如果n1仍然大于m，则必须把ans 减少 n1-m ans -= n1 - m; // 从集合1中取走元素}if(n2 > m){n2 -=  Math.min(n2 - m, common);ans -= n2 - m;}return ans;}
}

3003. 执行操作后的最大分割数量

困难

给你一个下标从 0 开始的字符串 s 和一个整数 k。

你需要执行以下分割操作，直到字符串 s 变为空：

选择 s 的最长前缀，该前缀最多包含 k 个不同字符。
删除这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。

执行操作之前，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。

在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。

示例 1：

输入：s = "accca", k = 2
输出：3
解释：在此示例中，为了最大化得到的分割数量，可以将 s[2] 改为 'b'。
s 变为 "acbca"。
按照以下方式执行操作，直到 s 变为空：
- 选择最长且至多包含 2 个不同字符的前缀，"acbca"。
- 删除该前缀，s 变为 "bca"。现在分割数量为 1。
- 选择最长且至多包含 2 个不同字符的前缀，"bca"。
- 删除该前缀，s 变为 "a"。现在分割数量为 2。
- 选择最长且至多包含 2 个不同字符的前缀，"a"。
- 删除该前缀，s 变为空。现在分割数量为 3。
因此，答案是 3。
可以证明，分割数量不可能超过 3。

示例 2：

输入：s = "aabaab", k = 3
输出：1
解释：在此示例中，为了最大化得到的分割数量，可以保持 s 不变。
按照以下方式执行操作，直到 s 变为空： 
- 选择最长且至多包含 3 个不同字符的前缀，"aabaab"。
- 删除该前缀，s 变为空。现在分割数量为 1。
因此，答案是 1。
可以证明，分割数量不可能超过 1。

示例 3：

输入：s = "xxyz", k = 1
输出：4
解释：在此示例中，为了最大化得到的分割数量，可以将 s[1] 改为 'a'。
s 变为 "xayz"。
按照以下方式执行操作，直到 s 变为空：
- 选择最长且至多包含 1 个不同字符的前缀，"xayz"。
- 删除该前缀，s 变为 "ayz"。现在分割数量为 1。
- 选择最长且至多包含 1 个不同字符的前缀，"ayz"。
- 删除该前缀，s 变为 "yz"，现在分割数量为 2。
- 选择最长且至多包含 1 个不同字符的前缀，"yz"。
- 删除该前缀，s 变为 "z"。现在分割数量为 3。
- 选择最且至多包含 1 个不同字符的前缀，"z"。
- 删除该前缀，s 变为空。现在分割数量为 4。
因此，答案是 4。
可以证明，分割数量不可能超过 4。

提示：

1 <= s.length <= 104
s 只包含小写英文字母。
1 <= k <= 26

记忆化搜索（动态规划）

https://leetcode.cn/problems/maximize-the-number-of-partitions-after-operations/solutions/2595072/ji-yi-hua-sou-suo-jian-ji-xie-fa-pythonj-6g5z/

class Solution {char[] s;int k;Map<Long, Integer> memo;public int maxPartitionsAfterOperations(String S, int k) {memo = new HashMap<>();this.k = k;this.s = S.toCharArray();return dfs(0, 0, 0);}/**定义 dfs(i, mask, changed) 表示当前遍历到s[i],当前这一段在i之前的字符集合是mask,是否已经修改了字符(changed),后续得到的最大分割数讨论是否修改s[i],以及当前字母能否加到mask中如果不改 s[i]:如果s[i]加到mask后，集合的大小超过了k，那么s[i]必须划分到下一段子串中，答案为dfs(i+1,{s[i]},changed)+1如果s[i]加到mask后，集合的大小没有超过k，那么s[i]必须划分到这一段中，答案为dfs(i+1,mask∪{s[i]},changed)如果changed=false，那么可以修改s[i]，枚举改成第j个字母如果j加到mask后，集合大小超过了k，那么j必须划分到下一段子串中，答案为dfs(i+1, {j}, true)+1如果j加到mask后，集合大小没有超过k，那么j必须划分到这一段中，答案为dfs(i+1,mask∪ {j}, true)以上情况取最大值递归边界dfs(n,*,*)=1递归入口dfs(0, 0, false)*/private int dfs(int i, int mask, int changed){if(i == s.length)return 1;long argsMask = (long) i << 32 | mask << 1 | changed;if (memo.containsKey(argsMask)) { // 之前计算过return memo.get(argsMask);}int res;// 不改s[i]int bit = 1 << (s[i] - 'a');int newMask = mask | bit;if(Integer.bitCount(newMask) > k){// 分割出一个子串，这个子串的最后一个字母在 i-1// s[i] 作为下一段的第一个字母，也就是 bit 作为下一段的 mask 的初始值res = dfs(i+1, bit, changed) + 1;}else{ // 不分割res = dfs(i+1, newMask, changed);}// 改s[i]if(changed == 0){// 枚举把 s[i] 改成 a,b,c,...,zfor (int j = 0; j < 26; j++) {newMask = mask | (1 << j);if (Integer.bitCount(newMask) > k) {// 分割出一个子串，这个子串的最后一个字母在 i-1// j 作为下一段的第一个字母，也就是 1<<j 作为下一段的 mask 的初始值res = Math.max(res, dfs(i + 1, 1 << j, 1) + 1);} else { // 不分割res = Math.max(res, dfs(i + 1, newMask, 1));}}}memo.put(argsMask, res); // 记忆化return res;}
}