100170. Maximum Area of Longest Diagonal Rectangle
给你一个下标从 0 开始的二维整数数组 dimensions。
对于所有下标 i（0 <= i < dimensions.length），dimensions[i][0] 表示矩形 i 的长度，而 dimensions[i][1] 表示矩形 i 的宽度。
返回对角线最 长 的矩形的 面积 。如果存在多个对角线长度相同的矩形，返回面积最 大 的矩形的面积。
测试样例：
输入：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。
解答：按照题意，计算对角线长和面积。
class Solution {
public int areaOfMaxDiagonal(int[][] dimensions) {
int maxDig = 0, area = 0;
for (int[] r : dimensions) {
int tmp = r[0] * r[0] + r[1] * r[1];
if (tmp > maxDig) {
maxDig = tmp;
area = r[0] * r[1];
} else if (tmp == maxDig) {
area = Math.max(area, r[0] * r[1]);
}
}
return area;
}
}100187. Minimum Moves to Capture The Queen
现有一个下标从 0 开始的 8 x 8 棋盘，上面有 3 枚棋子。
给你 6 个整数 a 、b 、c 、d 、e 和 f ，其中：
- (a, b) 表示白色车的位置。
- (c, d) 表示白色象的位置。
- (e, f) 表示黑皇后的位置。
假定你只能移动白色棋子，返回捕获黑皇后所需的最少移动次数。
请注意：
- 车可以向垂直或水平方向移动任意数量的格子，但不能跳过其他棋子。
- 象可以沿对角线方向移动任意数量的格子，但不能跳过其他棋子。
- 如果车或象能移向皇后所在的格子，则认为它们可以捕获皇后。
- 皇后不能移动。
测试样例：
输入：a = 1, b = 1, c = 8, d = 8, e = 2, f = 3
输出：2
解释：将白色车先移动到 (1, 3) ，然后移动到 (2, 3) 来捕获黑皇后，共需移动 2 次。由于起始时没有任何棋子正在攻击黑皇后，要想捕获黑皇后，移动次数不可能少于 2 次。
解答：我WA了一次，注意车和象都不能跳过其他棋子这个条件。一般来说，如果车和象一步就能吃到黑皇后，那么步数是1，否则必然是2（车或者象动2次，是一定可以把皇后吃到的）。1步的条件，就是车和皇后在相同的垂直或者水平位置，且象不挡路。或者象和皇后在相同的对角线上，且车不挡路。
class Solution {
public int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
if (a == e || b == f) {
if (a == e && c == e && isBetween(d, b, f)) {
} else if (b == f && d == f && isBetween(c, a, e)) {
} else {
return 1;
}
}
if (c + d == e + f) {
if (a + b == c + d && isBetween(a, c, e)) {
} else {
return 1;
}
}
if (c - d == e - f) {
if (a - b == c - d && isBetween(a, c, e)) {
} else {
return 1;
}
}
return 2;
}
private boolean isBetween(int a, int b, int c) {
return (a > b && a < c) || (a > c && a < b);
}
}100150. Maximum Size of a Set After Removals
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，它们的长度都是偶数 n 。
你必须从 nums1 中移除 n / 2 个元素，同时从 nums2 中也移除 n / 2 个元素。移除之后，你将 nums1 和 nums2 中剩下的元素插入到集合 s 中。
返回集合 s可能的 最多 包含多少元素。
测试样例：
输入：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 个元素。
解答：贪婪算法。先尽量把出现在nums1，但是不出现在nums2的数留下来。如果nums1还能取数，就把在nums2中出现的数部分留下。最后把nums2中出现的，还没取到的数字留下。
class Solution {
public int maximumSetSize(int[] nums1, int[] nums2) {
Set<Integer> set2 = new HashSet<>();
int len = nums1.length, half = len / 2;
for (int n : nums2) {
set2.add(n);
}
Set<Integer> result = new HashSet<>();
for (int n : nums1) {
if (!set2.contains(n) && half > 0) {
if (!result.contains(n)) {
result.add(n);
--half;
}
}
}
for (int n : nums1) {
if (set2.contains(n) && half > 0) {
if (!result.contains(n)) {
result.add(n);
--half;
}
}
}
half = len / 2;
for (int n : nums2) {
if (!result.contains(n) && half > 0) {
result.add(n);
--half;
}
}
return result.size();
}
}100154. Maximize the Number of Partitions After Operations
给你一个下标从 0 开始的字符串 s 和一个整数 k。
你需要执行以下分割操作，直到字符串 s 变为 空：
- 选择 s 的最长前缀，该前缀最多包含 k 个 不同 字符。
- 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。
执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。
在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。
测试样例：
输入：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。
解答：这道题目有点难。。。首先我们先把不动当前数组，然后从每个位置出发的最大分割数计算出来（代码里面就是firstChoice）。然后我们枚举每个位置更换字母之后对整个分区数的变化计算出来。要计算分区数变化，我们需要利用到字母前缀和，然后利用折半搜索来寻找第一个不满足条件的位置（即当前位置会导致前序不同字符数超过k）。
class Solution {
private class InternalMem {
int[] firstChoice;
int[][] mark;
int k, len;
}
public int maxPartitionsAfterOperations(String s, int k) {
InternalMem mem = new InternalMem();
mem.len = s.length();
mem.k = k;
mem.mark = new int[mem.len + 1][26];
for (int i = 0; i < mem.len; ++i) {
for (int j = 0; j < 26; ++j) {
mem.mark[i + 1][j] = mem.mark[i][j];
}
mem.mark[i + 1][s.charAt(i) - 'a'] += 1;
}
mem.firstChoice = new int[mem.len + 1];
Arrays.fill(mem.firstChoice, -1);
mem.firstChoice[mem.len] = 0;
for (int i = 0; i < mem.len; ++i) {
findInitialResult(mem, i);
}
int max = mem.firstChoice[0], alreadyMark = 0;
int last = binarySearchNextPos(mem, 0), st = 0;
for (int i = 0; i < mem.len; ++i) {
if (last == i) {
st = last;
last = binarySearchNextPos(mem, last);
++alreadyMark;
}
int ori = s.charAt(i) - 'a';
for (int j = 0; j < 26; ++j) {
if (j != ori) {
int tmp = binarySearchNextPosWithUpdate(mem, st, i, ori, j);
if (tmp != last) {
int addUp = alreadyMark + 1;
if (tmp > i) {
max = Math.max(addUp + mem.firstChoice[tmp], max);
} else {
max = Math.max(alreadyMark + 2
+ mem.firstChoice[binarySearchNextPosWithUpdate(mem, i, j, ori, j)], max);
}
}
}
}
}
return max;
}
private int findInitialResult(InternalMem mem, int pos) {
if (mem.firstChoice[pos] == -1) {
int next = binarySearchNextPos(mem, pos);
mem.firstChoice[pos] = findInitialResult(mem, next) + 1;
}
return mem.firstChoice[pos];
}
private int binarySearchNextPos(InternalMem mem, int pos) {
int st = pos + 1, ed = mem.mark.length;
while (st < ed) {
int mid = (st + ed) / 2;
int distinctCount = 0;
for (int i = 0; i < 26; ++i) {
if (mem.mark[mid][i] - mem.mark[pos][i] > 0) {
++distinctCount;
}
}
if (distinctCount <= mem.k) {
st = mid + 1;
} else {
ed = mid;
}
}
return st - 1;
}
private int binarySearchNextPosWithUpdate(InternalMem mem, int pos, int update, int ori, int next) {
int st = pos + 1, ed = mem.mark.length;
while (st < ed) {
int mid = (st + ed) / 2;
int distinctCount = 0;
for (int i = 0; i < 26; ++i) {
int tmp = mem.mark[mid][i];
if (i == ori && mid - 1 >= update) {
tmp -= 1;
} else if (i == next && mid - 1 >= update) {
tmp += 1;
}
if (tmp - mem.mark[pos][i] > 0) {
++distinctCount;
}
}
if (distinctCount <= mem.k) {
st = mid + 1;
} else {
ed = mid;
}
}
return st - 1;
}
}