欢迎大家加QQ群：623375442，可以方便群里面交流。
100410. Check if Two Chessboard Squares Have the Same Color
给你两个字符串 coordinate1 和 coordinate2，代表 8 x 8 国际象棋棋盘上的两个方格的坐标。
测试样例：
输入：coordinate1 = "a1", coordinate2 = "c3"
输出：true
解释：两个方格均为黑色。
解答：暴力枚举一下两个位置的颜色。
class Solution {
public boolean checkTwoChessboards(String coordinate1, String coordinate2) {
if (coordinate1.equals(coordinate2)) {
return true;
}
int c1 = -1, c2 = -1;
for (char l = 'a'; l <= 'h'; ++l) {
int c = (l - 'a') % 2;
for (int n = 1; n <= 8; ++n) {
if (coordinate1.charAt(0) == l && coordinate1.charAt(1) - '0' == n) {
c1 = c;
} else if (coordinate2.charAt(0) == l && coordinate2.charAt(1) - '0' == n) {
c2 = c;
}
c ^= 1;
}
}
return c1 == c2;
}
}100412. Final Array State After K Multiplication Operations II
有一个无限大的二维平面。
给你一个正整数 k ，同时给你一个二维数组 queries ，包含一系列查询：
- queries[i] = [x, y] ：在平面上坐标 (x, y) 处建一个障碍物，数据保证之前的查询 不会 在这个坐标处建立任何障碍物。
每次查询后，你需要找到离原点第 k 近 障碍物到原点的 距离 。
请你返回一个整数数组 results ，其中 results[i] 表示建立第 i 个障碍物以后，离原地第 k 近障碍物距离原点的距离。如果少于 k 个障碍物，results[i] == -1 。
注意，一开始 没有 任何障碍物。
坐标在 (x, y) 处的点距离原点的距离定义为 |x| + |y| 。
测试样例：
输入：queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2
输出：[-1,7,5,3]
解释：最初，不存在障碍物。
- queries[0] 之后，少于 2 个障碍物。
- queries[1] 之后， 两个障碍物距离原点的距离分别为 3 和 7 。
- queries[2] 之后，障碍物距离原点的距离分别为 3 ，5 和 7 。
- queries[3] 之后，障碍物距离原点的距离分别为 3，3，5 和 7 。
解答：典型的优先队列题目，记录最小的k个数字。
class Solution {
public int[] resultsArray(int[][] queries, int k) {
int[] res = new int[queries.length];
PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> (Integer.compare(b, a)));
for (int i = 0; i < queries.length; ++i) {
queue.add(Math.abs(queries[i][0]) + Math.abs(queries[i][1]));
if (queue.size() > k) {
queue.poll();
}
if (queue.size() == k) {
res[i] = queue.peek();
} else {
res[i] = -1;
}
}
return res;
}
}100419. Select Cells in Grid With Maximum Score
给你一个由正整数构成的二维矩阵 grid。
你需要从矩阵中选择 一个或多个 单元格，选中的单元格应满足以下条件：
- 所选单元格中的任意两个单元格都不会处于矩阵的 同一行。
- 所选单元格的值 互不相同。
你的得分为所选单元格值的总和。
返回你能获得的 最大 得分。
测试样例：
输入：grid = [[1,2,3],[4,3,2],[1,1,1]]
输出：8
解释：对应的值分别为 1、3 和 4 。
解答：这题范围太小了。直接用一点动态规划开始暴力。我们先记录每个数字出现的行数情况。然后暴力枚举买一种行取的情况下，最大值。
class Solution {
public int maxScore(List<List<Integer>> grid) {
int m = grid.size();
Set<Integer>[] map = new Set[101];
for (int i = 0; i <= 100; ++i) {
map[i] = new HashSet<>();
}
for (int i = 0; i < grid.size(); ++i) {
List<Integer> row = grid.get(i);
for (int n : row) {
map[n].add(i);
}
}
// 动态规划，记录每一种行取的情况下，最大值。
int[] dp = new int[1 << m];
Arrays.fill(dp, -1);
// 0代表一行都不取，这个时候是0
dp[0] = 0;
int res = 0;
for (int i = 100; i >= 1; --i) {
if (!map[i].isEmpty()) {
// 暴力枚举一下每种数字下，每种行取的情况下，最大值。
int[] nextDP = new int[1 << m];
for (int j = 0; j < (1 << m); ++j) {
nextDP[j] = dp[j];
}
for (int n : map[i]) {
for (int j = 0; j < dp.length; ++j) {
if (dp[j] == -1) continue;
int mark = (j >> n) & 1;
if (mark == 0) {
int tmp = j + (1 << n);
nextDP[tmp] = Math.max(nextDP[tmp], dp[j] + i);
res = Math.max(res, nextDP[tmp]);
}
}
}
dp = nextDP;
}
}
return res;
}
}100408. Maximum XOR Score Subarray Queries
给你一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri]。
对于每一个查询，你需要找出 nums[li..ri] 中任意 子数组 的 最大异或值。
数组的异或值 需要对数组 a 反复执行以下操作，直到只剩一个元素，剩下的那个元素就是 异或值：
- 对于除最后一个下标以外的所有下标 i，同时将 a[i] 替换为 a[i] XOR a[i + 1] 。
- 移除数组的最后一个元素。
返回一个大小为 q 的数组 answer，其中 answer[i] 表示查询 i 的答案。
测试样例：
输入：nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]
输出：[12,60,60]
解释：在第一个查询中，nums[0..2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，所有异或值中的最大值。
在第二个查询中，nums[1..4] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。
在第三个查询中，nums[0..5] 的子数组中最大的异或值是子数组 nums[1..4] 的异或值，为 60。
解答：这题脑筋急转弯。用几个例子试验一下，就能知道x到y的数组异或值XOR[x][y] = XOR[x - 1][y] ^ XOR[x][y - 1]。之后就退化成区间最大值了。
class Solution {
public int[] maximumSubarrayXor(int[] nums, int[][] queries) {
int len = nums.length;
int[][] dp = new int[len][len];
for (int i = 0; i < len; ++i) {
int st = 0, ed = i;
// 按照公式计算数组异或值
while (ed < len) {
if (i == 0) {
dp[st][ed] = nums[st];
} else {
dp[st][ed] = dp[st][ed - 1] ^ dp[st + 1][ed];
}
++st;
++ed;
}
}
// 求区间最大值
int[][] rangeMax = new int[len][len];
for (int i = 0; i < len; ++i) {
int st = 0, ed = i;
while (ed < len) {
if (i == 0) {
rangeMax[st][ed] = dp[st][ed];
} else {
rangeMax[st][ed] = Math.max(dp[st][ed], Math.max(rangeMax[st][ed - 1], rangeMax[st + 1][ed]));
}
++st;
++ed;
}
}
int[] res = new int[queries.length];
for (int i = 0; i < res.length; ++i) {
res[i] = rangeMax[queries[i][0]][queries[i][1]];
}
return res;
}
}