【LeetCode周赛】第379场周赛

本文主要是介绍【LeetCode周赛】第379场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode第379场周赛

100170. 对角线最长的矩形的面积简单
100187. 捕获黑皇后需要的最少移动次数中等
100150. 移除后集合的最多元素数中等

100170. 对角线最长的矩形的面积简单

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

分析：
根据题意模拟即可。
遍历数组，计算矩形对角线长度。

如果对角线更长，则更新新的矩形面积。
如果对角线一样长，则判断是否新的矩形面积更大

代码：

class Solution {
public:int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {int ans=0,ml=0;for(auto d : dimensions){int x=d[0], y=d[1];int l=x*x+y*y;if(ml<l){ans=x*y;ml=l;}else if(ml==l){ans=max(ans,x*y);}}return ans;}
};

100187. 捕获黑皇后需要的最少移动次数中等

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

分析：
棋盘一共只有三个棋子：白车、白象、黑皇后

白车：只要路径上没有其他棋子，可以沿行或者列走任意格。
白象：只要路径上没有其他棋子，可以沿对角线方向走任意格。
黑皇后：不能动。

根据棋子的数量和特性，我们可以得到：最多两步白车就能吃掉 黑皇后。
因此我们只需要判断是否存在一步就能吃掉 黑皇后 的方法：

黑皇后 和白车在同一行或者同一列，且白象不在二者中间！
黑皇后 和白象在同一斜线，且白车不在二者中间！

如果以上一步能吃掉 黑皇后 的方法行不通，返回 2 即可。

代码：

class Solution {
public:int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {if(a==e){int mi=min(b,f),ma=max(b,f);if((c!=a)||(c==a&&(d<mi||d>ma))) return 1;// 白车 黑皇后 同行，且白象不在二者中间}if(b==f){int mi=min(a,e),ma=max(a,e);if((d!=b)||(d==b&&(c<mi||c>ma))) return 1;// 白车 黑皇后 同列，且白象不在二者中间}if(c+d==e+f){int mix=min(c,e),ma_x=max(c,e),miy=min(d,f),may=max(d,f);if(c+d!=a+b) return 1;else if(!(mix<a&&a<ma_x&&miy<b&&b<may)) return 1;// 白象 黑皇后 同一右斜线，且白车不在二者中间}if(c-d==e-f){int mix=min(c,e),ma_x=max(c,e),miy=min(d,f),may=max(d,f);if(c-d!=a-b) return 1;else if(!(mix<a&&a<ma_x&&miy<b&&b<may)) return 1;// 白象 黑皇后 同一左斜线，且白车不在二者中间}return 2;}
};

100150. 移除后集合的最多元素数中等

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

分析：
题目求：每一个数组去除一半元素之后，二者取并集，集合的最大长度（即数字种类最多）。

对于每一类出现在这两个数组中的数字，总共有以下几种状态：

只出现在 nums1中的数
只出现在 nums2 中的数
nums1 和 nums2 中都出现的数

首先第一个贪心：为了尽可能的使并集的数字种类更多，我们只需要判断两个数组中每一个数只取一个的情况即可。因为集合会自动去重，重复的数字不会影响集合的长度。
再次利用贪心思想：如果某个数组中数字种类超过了一半，优先去除两个数组中都出现的数。因为如果先去除只出现在一个数组中的数，那么最终并集的数字种类一定会少1，而去除两个数组中都出现过的数，可能通过另外一个数组补充回来。
第三个贪心思想：如果两个数组重复数字的类别还没有完全去除，尽可能拿不一样的数，这样就能让并集更大，当然上限即为 nums1 和 nums2中重复的数字种类。

代码：

class Solution {
public:int maximumSetSize(vector<int>& nums1, vector<int>& nums2) {unordered_map<int,int> m1,m2;int n=nums2.size(),lm1,lm2,l;lm1=lm2=l=0;for(int i=0;i<n;i++){m1[nums1[i]]++;if(m1[nums1[i]]==1) lm1++;m2[nums2[i]]++;if(m2[nums2[i]]==1) lm2++;}for(auto [k,v] : m1){if(m2[k]!=0) l++;}n=n/2;lm1-=l,lm2-=l;int l1=l,l2=l;if(lm1+l1>n){if(lm1<=n) l1=n-lm1;else{l1=0,lm1=n;}}if(lm2+l2>n){if(lm2<=n) l2=n-lm2;else{l2=0,lm2=n;}}int ans=lm1+lm2;if(l1!=0||l2!=0){if(l1+l2>=l) ans+=l;else ans+=(l1+l2);}return ans;}
};