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);
}
};
