LeetCode第379场周赛

​ 这场比赛感觉来恶心人的，一堆边界条件，又让我疯狂WA，简单题也WA，受不了了。

第一题

给你一个下标从 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(vector<vector<int>>& dimensions) {
        int ans = 0;
        double s = 0;
        for(auto nums: dimensions){
            int a = nums[0], b = nums[1];
            double tmp = sqrt(a * a + b * b);
            if(tmp > s){	// 当对角线大时直接更新ans
                s = tmp;
                ans = a * b;
            } else if(tmp == s){	// 相等时再判断最值
                ans = max(ans, a * b);
            }
        }
        return ans;
    }
};
class Solution {
    public int areaOfMaxDiagonal(int[][] dimensions) {
        int ans = 0;
        double s = 0;
        for(int[] nums: dimensions){
            int a = nums[0], b = nums[1];
            double tmp = Math.sqrt(a * a + b * b);
            if(tmp > s){	// 当对角线大时直接更新ans
                s = Math.sqrt(a * a + b * b);
                ans = a * b;
            }
            else if(tmp == s){	// 相等时再判断最值
                ans = Math.max(ans, a * b);
            }
        }
        return ans;
    }
}
class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        ans = 0
        s = 0
        for a, b in dimensions:
            tmp = sqrt(a * a + b * b)
            if tmp > s:
                s = tmp
                ans = a * b
            elif tmp == s:
                ans = max(ans, a * b)
        return ans

复杂度分析

  • 时间复杂度：O(n)，n为数组长度。
  • 空间复杂度：O(1)。

第二题

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

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

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

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

请注意：

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

示例 1：

img

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

示例 2：

img

输入：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
  • 两枚棋子不会同时出现在同一个格子上。

思路分析

恶心人的题，分类讨论。

  1. 如果车能直接攻击到皇后，或者象能直接攻击到皇后，那么返回1。

  2. 如果车被象挡住，那么移走象，车就可以攻击到皇后，返回2。

  3. 如果象被车挡住，那么移走车，象就可以攻击到皇后，返回2。

  4. 如果车不能直接攻击到皇后，那么车可以水平移动或者垂直移动，其中一个位置必定不会被象挡住，可以攻击到皇后，返回2。

代码

class Solution:
    def minMovesToCaptureTheQueen(self, a: int, b: int, c: int, d: int, e: int, f: int) -> int:
        i = c
        j = d
        while i > 0 and j > 0:
            if i == e and j == f: return 1
            if i == a and j == b: break
            i -= 1
            j -= 1
            
        i = c
        j = d
        while i > 0 and j < 9:
            if i == e and j == f: return 1
            if i == a and j == b: break
            i -= 1
            j += 1
            
        i = c
        j = d
        while i < 9 and j > 0:
            if i == e and j == f: return 1
            if i == a and j == b: break
            i += 1
            j -= 1
            
        i = c
        j = d
        while i < 9 and j < 9:
            if i == e and j == f: return 1
            if i == a and j == b: break
            i += 1
            j += 1
        
        if(a == e and a != c): return 1
        if(b == f and b != d): return 1
        if(a == c and a == e and abs(b - f) != abs(b - d) + abs(d - f)): return 1
        if(b == d and b == f and abs(a - e) != abs(a - c) + abs(c - e)): return 1
        return 2

复杂度分析

  • 时间复杂度：O(9 * 4) = O(1)。
  • 空间复杂度：O(1)。

第三题

给你两个下标从 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 * 10^4
  • n是偶数。
  • 1 <= nums1[i], nums2[i] <= 10^9

思路分析

这题一看，好像很难，但其实就是简单的求交集，数学找规律求方程即可。

代码

class Solution {
    public int maximumSetSize(int[] nums1, int[] nums2) {
        int n = nums1.length;
        HashSet<Integer> set1 = new HashSet<>();
        HashSet<Integer> set2 = new HashSet<>();
        for (int i: nums1){
            set1.add(i);    // nums1的集合
        }
        for (int i: nums2){
            set2.add(i);    // nums2的集合
        }
        HashSet<Integer> set = new HashSet<>(set1);
        set.addAll(set2);   // set1和set2的并集
        int x1 = Math.max(0, set1.size() - n / 2), x2 = Math.max(0, set2.size() - n / 2);   // nums1和nums2仍需要删除的数的数量
        if(x1 == 0 && x2 == 0){
            return set.size();  // 如果不需要删除了，就直接返回两者的并集的长度
        }
        HashSet<Integer> s = new HashSet<>(set1);
        s.retainAll(set2);  // 两者的交集
        int x = Math.min(0, s.size() - x1 - x2);    // 通过统计找到的规律，先从两者交集中移除元素，如果够用了x=0，不够的话x<0,然后再从两者的并集中移除元素。
        return set.size() + x;
    }
}
class Solution:
    def maximumSetSize(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        s1, s2 = set(nums1), set(nums2)
        x1, x2 = max(0, len(s1) - n // 2), max(0, len(s2) - n // 2) # nums1和nums2仍需要删除的数的数量
        if (x1 == 0 and x2 == 0):
            return len(s1 | s2)	# 如果不需要删除了，就直接返回两者的并集的长度
        
        s = s1 & s2
        x = min(len(s) - x1 - x2, 0) # 通过统计找到的规律，先从两者交集中移除元素，如果够用了x=0，不够的话x<0,然后再从两者的并集中移除元素。
        return len(s1 | s2) + x

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n * 4) = O(n)，定义了4个哈希集合。