LeetCode 第379场周赛个人题解

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

题目描述

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

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

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

思路分析

一次遍历维护最值即可

详细代码

class Solution
{
public:
    int areaOfMaxDiagonal(vector<vector<int>> &dimensions)
    {
        int ma1 = 0, ma2 = 0;
        for (auto &v : dimensions)
        {
            if (ma1 < v[0] * v[0] + v[1] * v[1])
                ma1 = v[0] * v[0] + v[1] * v[1], ma2 = v[0] * v[1];
            else if(ma1 == v[0] * v[0] + v[1] * v[1])
                ma2 = max(ma2, v[0] * v[1]);
        }
        return ma2;
    }
};

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

题目描述

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

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

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

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

请注意：

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

思路分析

无论是象还是车，攻击黑皇后的步数不超过3次不少于一次

如果车或者象挡着对方路线了，那么就是3次，但是要明白二者不可能同时挡着互相的路线，所以最终结果不超过2

对于没被挡着的那个，那么根据皇后位置可以分为1次和2次

详细代码

class Solution {
public:
    int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
        int ret = 10;
        if(a == e || b == f){
            if(b == f && b == d && ((a < c && c < e) || (e < c && c < a)))
            ret = min(ret , 3);
            else if(a == e && a == c && ((b < d && d < f) || (f < d && d < b)))
            ret = min(ret , 3);
            else
            ret = min(ret , 1);
        }
        if(abs(c - e) == abs(d - f)){
            if(abs(a - c) == abs(b - d) && ((c < a && a < e) || (e < a && a < c)))
            ret = min(ret , 3);
            else
            ret = min(ret , 1);
        }
        return min(2 , ret);
    }
};

?

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

题目描述

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

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

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

思路分析

考虑特殊情况，二者去重后的各自数目都是2 / n，那么我们每个元素取一个，其他的全删了就行

更进一步，二者去重后各自数目都不超过2 / n，那么我们一定可以各自删去n/2个元素并且使得去重后的元素个数不变

那么也就是说，对于超出2 / n的部分，超出多少，至少要减少几种数字

对于二者重叠的部分，一个删另一个不删，这样可以保证合并后这个元素仍然在

我们不妨把重叠的元素都删掉一个，然后看二者是否还需要删除，再删去不得不删的元素就行了

详细代码

class Solution
{
public:
    int maximumSetSize(vector<int> &nums1, vector<int> &nums2)
    {
        unordered_set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end());
        int n = nums1.size();
        if (s1.size() <= n / 2 && s2.size() <= n / 2)
        {
            s1.insert(s2.begin(), s2.end());
            return s1.size();
        }
        int com = 0, res1 = s1.size() - n / 2, res2 = s2.size() - n / 2;
        for (auto x : s1)
            if (s2.count(x))
                if (res1 > 0)
                    s2.erase(x), res1--;
                else if (res2 > 0)
                    s2.erase(x), res2--;
        s1.insert(s2.begin(), s2.end());
        int ret = s1.size();
        if (res1 > 0)
            ret -= res1;
        if (res2 > 0)
            ret -= res2;
        return ret;
    }
};

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

题目描述

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

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

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

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

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

思路分析

这个比赛的时候剪枝写错了，过了两百多个点，有几个没过，赛后发现问题所在了，哭死

对于每个位置我们有两种选择，改或者不改

那么我们可以暴力的去枚举所有情况，然后贪心的分割，当前能割就割，这样的话大概能过一百多个点？

当然，暴力不是目的，而是为了优化。

基于这样的思路，我们记当前前缀为cur，枚举下标为i，k - 已经枚举字符种类 = res，前缀是否进行修改操作为lim

对于当前已经枚举前缀中的字符种类最多也就26个，我们可以状态压缩为一个26位的整数cur，

那么如果当前已经枚举了k个字符了，如果下一个字符已经存在于前缀中了，我们就继续往下递归，res不变

回溯时，如果lim为false，我们就枚举下一个位置可以修改成的字符，这个字符显然要满足不在前缀中，向下递归，此时lim = 1 ， res = k?- 1?

那么如果当前枚举字符小于k，并且下一个字符在前缀中，仍然向下递归，res不变

回溯时，如果lim为false，同样枚举修改情况，lim = 1 ， res = res - 1向下递归

那么如果当前枚举字符小于k，并且下一个字符在前缀中 ，那么向下递归，把下一个字符加入前缀，res - 1，lim不变

代码处理上我们肯定要剪枝，我们的状态数组f[][][]有三个维度，那么要开(1 << 26) * 10010 * 2的空间会炸，我们就把第一维换成unordered_map就能过了，而且空间消耗还满可观的

详细代码

class Solution {
public:
    int num(char ch)
    {return ch - 'a';}
    int maxPartitionsAfterOperations(string s, int k) {
        if(k == 26) return 1;
        int n = s.size();
        unordered_map<int , int> f[10010][2];
        function<int(int,int,int,bool)> dfs = [&](int cur , int i , int res , bool lim)
        {
            if(i == n - 1) return 1;
            if(f[i][lim].count(cur)) return f[i][lim][cur];
            int& ret = f[i][lim][cur];

            if(!res)
            {
                if (cur & (1 << num(s[i + 1]))){
                    ret = dfs(cur , i + 1 , res , lim);
                    if(!lim)
                        for(int j = 0 ; j < 26 ; j++)
                            if(!(cur & (1 << j)))
                                ret = max(ret , 1 + dfs(1 << j , 1 + i , k - 1 , 1));
                    return ret;
                }
                return ret = 1 + dfs(1 << num(s[i + 1]) , i + 1 , k - 1 , lim);
            }

            if(cur & (1 << num(s[i + 1])))
            {
                ret = dfs(cur , i + 1 , res , lim);
                if(!lim)
                    for(int j = 0 ; j < 26 ; j++)
                        if(!(cur & (1 << j)))
                            ret = max(ret , dfs(cur | (1 << j) , 1 + i , res - 1 , 1));
                return ret;
            }

            return ret = dfs(cur | (1 << num(s[i + 1])) , i + 1 , res - 1 , lim);
        };
        return dfs(1 << num(s[0]) , 0 , k - 1 , 0);
    }
};