给你一个整数数组 nums 和一个 正 整数 k 。
定义长度为 2 * x 的序列 seq 的 值 为：
请你求出 nums 中所有长度为 2 * k 的 子序列 的 最大值 。
示例 1：
输入：nums = [2,6,7], k = 1
输出：5
解释：
子序列 [2, 7] 的值最大，为 2 XOR 7 = 5 。示例 2：
输入：nums = [4,2,5,6,7], k = 2
输出：2
解释：
子序列 [4, 5, 6, 7] 的值最大，为 (4 OR 5) XOR (6 OR 7) = 2 。说明：
// todo
给你两个字符串 word1 和 word2 。
如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀，那么我们称字符串 x 是 合法的 。
请你返回 word1 中 合法 子字符串 的数目。
注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。
示例 1：
输入：word1 = "bcca", word2 = "abc"
输出：1
解释：
唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。示例 2：
输入：word1 = "abcabc", word2 = "abc"
输出：10
解释：
除了长度为 1 和 2 的所有子字符串都是合法的。示例 3：
输入：word1 = "abcabc", word2 = "aaabc"
输出：0说明：
参考 3297.统计重新排列后包含另一个字符串的子字符串数目I，本题内存限制小，必须使用线性复杂度的解法。
/**
* @date 2025-01-09 14:28
*/
public class ValidSubstringCount3297 {
public long validSubstringCount_v1(String word1, String word2) {
int[] cnt1 = new int[26];
int[] cnt2 = new int[26];
char[] chars1 = word1.toCharArray();
char[] chars2 = word2.toCharArray();
for (char c : chars1) {
cnt1[c - 'a']++;
}
for (char c : chars2) {
cnt2[c - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (cnt1[i] < cnt2[i]) {
return 0;
}
}
int n = word1.length();
int r = n - 1;
while (--cnt1[chars1[r] - 'a'] >= cnt2[chars1[r] - 'a']) {
r--;
}
long res = n - r;
cnt1[chars1[r++] - 'a']++;
for (int i = 0; i < n - word2.length(); i++) {
int c = chars1[i] - 'a';
cnt1[c]--;
while (r < n && cnt1[c] < cnt2[c]) {
cnt1[chars1[r++] - 'a']++;
}
if (cnt1[c] >= cnt2[c]) {
res += n - r + 1;
} else {
break;
}
}
return res;
}
}
有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。
给你整数 m ，n 和两个数组：
一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：
每次操作后，这块蛋糕都被切成两个独立的小蛋糕。
每次操作的开销都为最开始对应切割线的开销，并且不会改变。
请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。
示例 1：
输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
输出：13
解释：
沿着垂直线 0 切开蛋糕，开销为 5 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
总开销为 5 + 1 + 1 + 3 + 3 = 13 。示例 2：
输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
输出：15
解释：
沿着水平线 0 切开蛋糕，开销为 7 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
总开销为 7 + 4 + 4 = 15 。说明：
有一块 m x n 的蛋糕，horizontalCut[i] 表示水平切第 i 行的开销，verticalCut[i] 表示垂直切第 i 列的开销。求将蛋糕切成 1 x 1 小块的最小代价。
与 切蛋糕的最小总开销I 相比数据范围扩大了，返回值是 long 型。
/**
* @date 2024-12-26 16:38
*/
public class MinimumCost3219 {
public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
int horizontalPart = m;
int verticalPart = n;
Arrays.sort(horizontalCut);
Arrays.sort(verticalCut);
int h = 0;
int v = 0;
long res = 0;
while (h < m - 1 || v < n - 1) {
int hcost = h >= m - 1 ? Integer.MAX_VALUE : horizontalCut[h];
int vcost = v >= n - 1 ? Integer.MAX_VALUE : verticalCut[v];
if (hcost < vcost) {
res += verticalPart * hcost;
horizontalPart--;
h++;
} else {
res += horizontalPart * vcost;
verticalPart--;
v++;
}
}
return res;
}
}
给你一个字符串数组 words 和一个字符串 target。
如果字符串 x 是 words 中 任意 字符串的 前缀，则认为 x 是一个 有效 字符串。
现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
示例 1：
输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
输出： 3
解释：
target 字符串可以通过连接以下有效字符串形成：
words[1] 的长度为 2 的前缀，即 "aa"。
words[2] 的长度为 3 的前缀，即 "bcd"。
words[0] 的长度为 3 的前缀，即 "abc"。示例 2：
输入： words = ["abababab","ab"], target = "ababaababa"
输出： 2
解释：
target 字符串可以通过连接以下有效字符串形成：
words[0] 的长度为 5 的前缀，即 "ababa"。
words[0] 的长度为 5 的前缀，即 "ababa"。示例 3：
输入： words = ["abcdef"], target = "xyz"
输出： -1说明：
// todo
一个酒店里有 n 个房间，这些房间用二维整数数组 rooms 表示，其中 rooms[i] = [roomIdi, sizei] 表示有一个房间号为 roomIdi 的房间且它的面积为 sizei 。每一个房间号 roomIdi 保证是 独一无二 的。
同时给你 k 个查询，用二维数组 queries 表示，其中 queries[j] = [preferredj, minSizej] 。第 j 个查询的答案是满足如下条件的房间 id ：
如果差的绝对值有 相等 的，选择 最小 的 id 。如果 没有满足条件的房间 ，答案为 -1 。
请你返回长度为 k 的数组 answer ，其中 answer[j] 为第 j 个查询的结果。
示例 1：
输入：rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
输出：[3,-1,3]
解释：查询的答案如下：
查询 [3,1] ：房间 3 的面积为 2 ，大于等于 1 ，且号码是最接近 3 的，为 abs(3 - 3) = 0 ，所以答案为 3 。
查询 [3,3] ：没有房间的面积至少为 3 ，所以答案为 -1 。
查询 [5,2] ：房间 3 的面积为 2 ，大于等于 2 ，且号码是最接近 5 的，为 abs(3 - 5) = 2 ，所以答案为 3 。示例 2：
输入：rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
输出：[2,1,3]
解释：查询的答案如下：
查询 [2,3] ：房间 2 的面积为 3 ，大于等于 3 ，且号码是最接近的，为 abs(2 - 2) = 0 ，所以答案为 2 。
查询 [2,4] ：房间 1 和 3 的面积都至少为 4 ，答案为 1 因为它房间编号更小。
查询 [2,5] ：房间 3 是唯一面积大于等于 5 的，所以答案为 3 。说明：
有一个数组 rooms，rooms[i][0] 表示第 i 个房间编号，房间编号不重复，rooms[i][1] 表示第 i 个房间大小。有一个查询数组 queries，queries[j][0] 表示第 j 个查询期望的房间编号，queries[j][1] 表示第 j 个查询最小的房间大小。返回查询数组对应的结果数组，查询结果为房间编号，该房间的面积至少为 queries[j][1]，且房间编号与 queries[j][0] 的距离最小，如果存在距离相等的情况，取房间编号最小的。
首先按房间大小排序，大小相同的按编号排序。对于每个查询首先二分查找出第一个大于 queries[j][1] 的房间在数组中的位置，接下来需要从该位置往后计算距离 queries[j][0] 最近的房间编号。
// todo 官网题解 Bentley Ottmann, Sparse Table 倍增 RMQ,Range Maximum/Minimum Query
/**
* @date 2024-12-16 16:23
*/
public class ClosestRoom1847 {
public int[] closestRoom(int[][] rooms, int[][] queries) {
Arrays.sort(rooms, (a, b) -> {
int compare = a[1] - b[1];
if (compare != 0) {
return compare;
}
return a[0] - b[0];
});
int n = rooms.length;
int k = queries.length;
int[] res = new int[k];
int i = 0;
for (int[] query : queries) {
int minAreaRoomIndex = lowerBound(rooms, 0, n - 1, query[1]);
if (minAreaRoomIndex == n) {
res[i++] = -1;
continue;
}
int dist = Integer.MAX_VALUE;
int roomId = Integer.MAX_VALUE;
for (int j = minAreaRoomIndex; j < n; j++) {
int tmp = Math.abs(query[0] - rooms[j][0]);
if (tmp < dist) {
dist = tmp;
roomId = rooms[j][0];
} else if (tmp == dist) {
roomId = Math.min(rooms[j][0], roomId);
}
}
res[i++] = roomId;
}
return res;
}
public int lowerBound(int[][] rooms, int l, int r, int target) {
int m = l + ((r - l) >> 1);
while (l <= r) {
if (rooms[m][1] >= target) {
r = m - 1;
} else {
l = m + 1;
}
m = l + ((r - l) >> 1);
}
return l;
}
}
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。
你需要对 nums 执行 k 次操作，每次操作中：
k 次操作以后，你需要将 nums 中每一个数值对 10^9 + 7 取余。
请你返回执行完 k 次乘运算以及取余运算之后，最终的 nums 数组。
示例 1：
输入：nums = [2,1,3,5,6], k = 5, multiplier = 2
输出：[8,4,6,5,6]
解释：
操作 结果
1 次操作后 [2, 2, 3, 5, 6]
2 次操作后 [4, 2, 3, 5, 6]
3 次操作后 [4, 4, 3, 5, 6]
4 次操作后 [4, 4, 6, 5, 6]
5 次操作后 [8, 4, 6, 5, 6]
取余操作后 [8, 4, 6, 5, 6]示例 2：
输入：nums = [100000,2000], k = 2, multiplier = 1000000
输出：[999999307,999999993]
解释：
操作 结果
1 次操作后 [100000, 2000000000]
2 次操作后 [100000000000, 2000000000]
取余操作后 [999999307, 999999993]说明：
有一个数组 nums，我们需要执行 k 次操作，每次操作选择数组中最小元素 min，并将它的值替换为 min * multiplier，返回最终的数组。数据范围比 3264.K次乘运算后的最终数组I 大，multiplier 也大，会溢出，需要进行取余运算。
首先 k 最大 10^9，还沿用昨天模拟的解法会超时。更重要的是，由于乘积很大，我们只能在队列中保存取余后的数据，如果还按找之前模拟来取最小元素就不对了。
我们发现，当执行一些次操作之后，所有元素都会被乘以 multiplier，当 k / n 比较大时，我们可以使用快速幂先计算出 multiplier 的 k/n 幂，然后再与元素相乘。
关键在于何时开始使用上面的思路来计算，考虑 1 2 4 8 16，multiplier 为 2，k 为 20。
2 2 4 8 16
4 2 4 8 16
4 4 4 8 16
8 4 4 8 16
8 8 4 8 16
8 8 8 8 16
16 8 8 8 16
16 16 8 8 16
16 16 16 8 16
16 16 16 16 16可以发现 当前数组 最小值 乘以 multiplier 大于 原数组 元素的 最大值 时，后面再乘以 multiplier 就是每一个元素执行一次了。
因此我们需要先使用堆模拟前面几次操作，直到满足上面的条件。注意：堆中数据不能取模，满足条件之前堆中数据使用 long 型不会溢出。
/**
* @date 2024-12-14 10:31
*/
public class GetFinalState3266 {
public int[] getFinalState(int[] nums, int k, int multiplier) {
if (multiplier == 1) {
return nums;
}
int mod = 1000000007;
int n = nums.length;
long[] mul = new long[n];
for (int i = 0; i < n; i++) {
mul[i] = nums[i];
}
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> {
long compare = mul[a] - mul[b];
if (compare != 0) {
return (int) compare;
}
return a - b;
});
long max = 0;
for (int i = 0; i < n; i++) {
q.offer(i);
max = Math.max(max, nums[i]);
}
int i = 0;
for (; i < k; i++) {
if (mul[q.peek()] * (long) multiplier > max) {
break;
}
Integer index = q.poll();
mul[index] = mul[index] * multiplier;
q.offer(index);
}
int remainder = k - i;
if (remainder >= n) {
long pow = pow(multiplier, remainder / n);
for (int j = 0; j < n; j++) {
Integer index = q.poll();
int rem = remainder % n;
mul[index] = (int) ((mul[index] * pow % mod * (j < rem ? (long) multiplier : 1)) % mod);
}
} else {
for (int j = 0; j < remainder; j++) {
Integer index = q.poll();
mul[index] = (int) ((mul[index] * (long) multiplier) % mod);
q.offer(index);
}
}
for (int j = 0; j < n; j++) {
nums[j] = (int) mul[j];
}
return nums;
}
public long pow(long base, int exponent) {
long res = 1;
int mod = 1000000007;
while (exponent > 0) {
if ((exponent & 1) == 1) {
res = res * base % mod;
}
base = base * base % mod;
exponent >>= 1;
}
return res;
}
}
给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。
每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：
values[i][j] * d 。换句话说，选择该商店中还没购买过的物品中最大的下标 j ，并且花费 values[i][j] * d 去购买。注意，所有物品都视为不同的物品。比方说如果你已经从商店 1 购买了物品 0 ，你还可以在别的商店里购买其他商店的物品 0 。
请你返回购买所有 m * n 件物品需要的 最大开销 。
示例 1：
输入：values = [[8,5,2],[6,4,1],[9,7,3]]
输出：285
解释：第一天，从商店 1 购买物品 2 ，开销为 values[1][2] * 1 = 1 。
第二天，从商店 0 购买物品 2 ，开销为 values[0][2] * 2 = 4 。
第三天，从商店 2 购买物品 2 ，开销为 values[2][2] * 3 = 9 。
第四天，从商店 1 购买物品 1 ，开销为 values[1][1] * 4 = 16 。
第五天，从商店 0 购买物品 1 ，开销为 values[0][1] * 5 = 25 。
第六天，从商店 1 购买物品 0 ，开销为 values[1][0] * 6 = 36 。
第七天，从商店 2 购买物品 1 ，开销为 values[2][1] * 7 = 49 。
第八天，从商店 0 购买物品 0 ，开销为 values[0][0] * 8 = 64 。
第九天，从商店 2 购买物品 0 ，开销为 values[2][0] * 9 = 81 。
所以总开销为 285 。
285 是购买所有 m * n 件物品的最大总开销。示例 2：
输入：values = [[10,8,6,4,2],[9,7,5,3,2]]
输出：386
解释：第一天，从商店 0 购买物品 4 ，开销为 values[0][4] * 1 = 2 。
第二天，从商店 1 购买物品 4 ，开销为 values[1][4] * 2 = 4 。
第三天，从商店 1 购买物品 3 ，开销为 values[1][3] * 3 = 9 。
第四天，从商店 0 购买物品 3 ，开销为 values[0][3] * 4 = 16 。
第五天，从商店 1 购买物品 2 ，开销为 values[1][2] * 5 = 25 。
第六天，从商店 0 购买物品 2 ，开销为 values[0][2] * 6 = 36 。
第七天，从商店 1 购买物品 1 ，开销为 values[1][1] * 7 = 49 。
第八天，从商店 0 购买物品 1 ，开销为 values[0][1] * 8 = 64 。
第九天，从商店 1 购买物品 0 ，开销为 values[1][0] * 9 = 81 。
第十天，从商店 0 购买物品 0 ，开销为 values[0][0] * 10 = 100 。
所以总开销为 386 。
386 是购买所有 m * n 件物品的最大总开销。说明：
1 <= values[i][j] <= 10^6有 m 个商店，每个商店里有 n 个商品。values[i][j] 表示商店 i 中商品 j 的价值，values[i] 非严格递减。从第一天开始，在第 d 天，我们可以选择一个商店 i，花费 d * values[i][j] 购买剩余的商品中价值中最小的商品 j。返回购买完所有商店的所有商品所需的最大开销。
要使开销最大，我们应该优先购买价值最小的商品，因为开销有天数加成，价值越大，在后面买翻倍后开销更大。由于每个商店里的商品是非严格递减的，每次从所有商店末尾取价值最小的商品，实际上就是按照所有商店的所有商品的价值从小到大取。
我们可以使用最小堆维护每个商店的最后一个商品，堆中元素记录商店编号 i，与商品下标 j。
如果是求最小开销呢？
如果没有限制购买规则，显然先购买高价值商品花费最小。但是题目规定每一次任选一个商店从其剩余商品中的最后一个（剩余商品中价值最低的）商品购买。
我们应该从 左边 开始优先购买价值 最小 的商品，然后将顺序 反转 就得到了从右购买的序列，按照这个顺序计算购买的开销。
注意：不能从右边选最大的买，比如：
100000 90000 1
100 10 2如果从右边取最大的，购买顺序为 2 10 100 1 90000 100000，这显然不是最小开销。而从左边取最小的买，顺序为 100 10 2 100000 90000 1，反转得到 1 90000 100000 2 10 100 按此顺序购买花费最小。
/**
* @date 2024-12-12 14:11
*/
public class MaxSpending2931 {
/**
* 13ms
* 直接合并为一维数组后排序
* 时间复杂度 O(mnlog(mn))
* 执行快是因为不用维护堆以及操作堆中数据的值，每次计算的复杂度小于维护数据结构的复杂度
*/
public long maxSpending_v2(int[][] values) {
int m = values.length;
int n = values[0].length;
long res = 0L;
long d = 1L;
int[] v = new int[m * n];
for (int i = 0; i < m; i++) {
System.arraycopy(values[i], 0, v, i * n, n);
}
Arrays.sort(v);
for (int i : v) {
res += d++ * i;
}
return res;
}
/**
* 37ms
* 时间复杂度 O(mnlog(m))
*/
public long maxSpending(int[][] values) {
int m = values.length;
int n = values[0].length;
PriorityQueue<int[]> q = new PriorityQueue<>(m, (a, b) -> a[0] - b[0]);
for (int i = 0; i < m; i++) {
q.offer(new int[]{values[i][n - 1], i, n - 1});
}
long res = 0L;
long d = 1L;
while (!q.isEmpty()) {
int[] goods = q.poll();
int storeIndex = goods[1];
res += d++ * goods[0];
int p = --goods[2];
if (p >= 0) {
q.offer(new int[]{values[storeIndex][p], storeIndex, p});
}
}
return res;
}
}
一个 n x n 的二维网络 board 仅由 0 和 1 组成 。每次移动，你能交换任意两列或是两行的位置。
返回 将这个矩阵变为 “棋盘” 所需的最小移动次数 。如果不存在可行的变换，输出 -1。
“棋盘” 是指任意一格的上下左右四个方向的值均与本身不同的矩阵。
示例 1:
输入: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
输出: 2
解释:一种可行的变换方式如下，从左到右：
第一次移动交换了第一列和第二列。
第二次移动交换了第二行和第三行。示例 2:
输入: board = [[0, 1], [1, 0]]
输出: 0
解释: 注意左上角的格值为0时也是合法的棋盘.示例 3:
输入: board = [[1, 0], [1, 0]]
输出: -1
解释: 任意的变换都不能使这个输入变为合法的棋盘。说明：
board[i][j] 将只包含 0或 1有一个 n x n 的网格，仅由 0 和 1 组成。每次移动可以交换网格的任意两行或两列。求将网格变为棋盘的最小移动次数，如果无法变为棋盘返回 -1。所谓棋盘，指的是任意格子的值与它周围四个格子的值不同。
首先需要分析出可以转变为棋盘的条件，棋盘只有两种类型的行，它们互反，且这两种行的个数相差至多为 1。对于每种类型的行，0 的个数和 1 的个数相差至多也是 1。
然后需要求出当前行与列转化为 010101…… 或者 101010…… 所需的移动次数。求出位置不同的个数 diff，如果 n 为偶数，最小交换次数为 Math.min(diff, n - diff)，如果 n 为奇数，最小交换次数为 diff/2。
/**
* @date 2024-12-09 8:46
*/
public class MovesToChessboard782 {
public int movesToChessboard(int[][] board) {
int n = board.length;
int[] firstRow = board[0];
int[] firstCol = new int[n];
int[] firstRowCnt = new int[2];
int[] firstColCnt = new int[2];
for (int i = 0; i < n; i++) {
firstRowCnt[board[0][i]]++;
firstColCnt[board[i][0]]++;
firstCol[i] = board[i][0];
}
// 第一行或者第一列0与1的个数之差超过1就无法转化为棋盘。因为最终棋盘的行与列都是 101010…… 或 010101…… 的形式
if (Math.abs(firstRowCnt[0] - firstRowCnt[1]) > 1 || Math.abs(firstColCnt[0] - firstColCnt[1]) > 1) {
return -1;
}
// 判断行是否完全相同或者完全相反，这里使用异或运算来判断，如果equal == 0 说明完全相同，opposite == 0 说明完全相反，如果都不等于0说明无法转为棋盘
for (int i = 1; i < n; i++) {
int equal = 0;
int opposite = 0;
for (int j = 0; j < board[i].length; j++) {
int tmp = board[i][j] ^ board[0][j];
equal += tmp;
opposite += 1 ^ tmp;
}
if (equal != 0 && opposite != 0) {
return -1;
}
}
// 经过前面的判断，第一行与第一列的第一个格子的值一定是相同的
return minMove(firstRow, firstRowCnt) + minMove(firstCol, firstColCnt);
}
public int minMove(int[] arr, int[] cnt) {
int n = arr.length;
int start = cnt[1] > cnt[0] ? 1 : 0;
int diff = 0;
// 计算与棋盘的差异，我们移动一次可以减少两个 diff，因此最终结果需要除以2
for (int i = 0; i < n; i++) {
// i % 2 ^ start 的作用是确定 1010…… 还是 0101……，如果不考虑start 那么序列是 0101，如果需要以1开头，就需要 异或 1
diff += i % 2 ^ start ^ arr[i];
}
// 这里考虑的是 n 的奇偶性，如果n为奇数，那么必定 abs(cnt[1] - cnt[0]) == 1，多的那一个一定要放在第一个位置，移动的方案只有一种
// 如果为偶数，最终可以是 0101…… 或者 1010……，取移动次数最小的
return n % 2 != 0 ? diff / 2 : Math.min(diff, n - diff) / 2;
}
}
有一个 8 x 8 的棋盘，它包含 n 个棋子（棋子包括车，后和象三种）。给你一个长度为 n 的字符串数组 pieces ，其中 pieces[i] 表示第 i 个棋子的类型（车，后或象）。除此以外，还给你一个长度为 n 的二维整数数组 positions ，其中 positions[i] = [ri, ci] 表示第 i 个棋子现在在棋盘上的位置为 (ri, ci) ，棋盘下标从 1 开始。
棋盘上每个棋子都可以移动 至多一次 。每个棋子的移动中，首先选择移动的 方向 ，然后选择 移动的步数 ，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：
移动组合 包含所有棋子的 移动 。每一秒，每个棋子都沿着它们选择的方向往前移动 一步 ，直到它们到达目标位置。所有棋子从时刻 0 开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 不有效 。
请你返回 有效 移动组合的数目。
注意：
示例 1:
输入：pieces = ["rook"], positions = [[1,1]]
输出：15
解释：上图展示了棋子所有可能的移动。示例 2：
输入：pieces = ["queen"], positions = [[1,1]]
输出：22
解释：上图展示了棋子所有可能的移动。示例 3:
输入：pieces = ["bishop"], positions = [[4,3]]
输出：12
解释：上图展示了棋子所有可能的移动。示例 4:
输入：pieces = ["rook","rook"], positions = [[1,1],[8,8]]
输出：223
解释：每个车有 15 种移动，所以总共有 15 * 15 = 225 种移动组合。
但是，有两个是不有效的移动组合：
- 将两个车都移动到 (8, 1) ，会导致它们在同一个格子相遇。
- 将两个车都移动到 (1, 8) ，会导致它们在同一个格子相遇。
所以，总共有 225 - 2 = 223 种有效移动组合。
注意，有两种有效的移动组合，分别是一个车在 (1, 8) ，另一个车在 (8, 1) 。
即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。示例 5：
输入：pieces = ["queen","bishop"], positions = [[5,7],[3,4]]
输出：281
解释：总共有 12 * 24 = 288 种移动组合。
但是，有一些不有效的移动组合：
- 如果后停在 (6, 7) ，它会阻挡象到达 (6, 7) 或者 (7, 8) 。
- 如果后停在 (5, 6) ，它会阻挡象到达 (5, 6) ，(6, 7) 或者 (7, 8) 。
- 如果象停在 (5, 2) ，它会阻挡后到达 (5, 2) 或者 (5, 1) 。
在 288 个移动组合当中，281 个是有效的。说明：
有一个 8 x 8 的棋盘，行列编号从 1 ~ 8。棋盘上有 n 个棋子，pieces[i] 表示棋子 i 的类型，rook 表示车，queen 表示皇后，bishop 表示象，positions[i] = [ri, ci] 表示棋子 i 所在行编号为 ri，所在列编号为 ci。棋盘上的每个棋子都可以移动 至多 一步，不同的棋子移动方式不同，参考国际象棋。车走竖线或横线，象走斜线，皇后走竖线、横线或斜线，不能跳过其它棋子。
特别注意，我们求的是 有效移动 组合，重点在 移动 而不是最终状态，比如示例4。
棋盘大小固定，考虑车移动或者不移动，它最多有 15 种移动的可能，包括不移动或者移动到相应方向上的其它格子共 1 + 2 * 7 种。由于棋盘是偶数没有中间格子，所以象有 8 + 6 种。同理皇后可能的移动方式最多有 28 种，包括不移动或者移动相应方向上的其它格子 1 + 2 * 7 + 7 + 6 种，如果它位于一条 8 格的对角线上，除去自身还剩 7 格，它所在的另一对角线剩余 6 个格子。
题目描述里面非常让人迷惑的一点是既允许相邻棋子同时交换位置，而示例5又说棋子会阻挡其它棋子通行。这个题的难点在于如果按照棋盘状态去枚举的话，当两个棋子相遇的时候不知道是否应该穿越，如果穿越的话就会移动另一个棋子，如何去重？我们必须将移动的步数考虑进去，如果两个棋子相遇时都没有到达目标位置那么它们可以穿过。否则，某个棋子提前停下，另一个棋子行进到相同的位置发生碰撞，不符合题目条件。
参考题解思路写出来了。
/**
* @date 2024-12-04 14:24
*/
public class CountCombinations2056 {
public static class Move {
public int x;
public int y;
public int dx;
public int dy;
public int step;
public Move(int x, int y, int dx, int dy, int step) {
this.x = x;
this.y = y;
this.dx = dx;
this.dy = dy;
this.step = step;
}
}
public int[][] rookDir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int[][] bishopDir = new int[][]{{-1, -1}, {1, 1}, {1, -1}, {-1, 1}};
public int[][] queenDir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {1, -1}, {-1, 1}};
/**
* 预处理每个棋子可行的移动方案、起点、方向、步数
*/
public int countCombinations(String[] pieces, int[][] positions) {
int n = pieces.length;
Move[][] moves = new Move[n][];
for (int i = 0; i < n; i++) {
moves[i] = generateAllValidMove(pieces[i], positions[i]);
}
Move[] curMove = new Move[n];
return dfs(0, n, curMove, moves);
}
/**
* 回溯，先从棋子0中选一个可行的移动方案，然后进入下一层，
* 从棋子1中选一个可行的移动方案，判断当前方案与前面所选的移动方案是否存在某一时刻使得两个棋子占据同一个格子
* 如果不存在就进入下一层，否则枚举另一个方案。
* i 表示枚举第 i 个棋子的合法移动方案
* curMove 表示前面棋子选择的移动方案，用于下一层比较移动方案是否合法
* moves 表示所有棋子的移动方案
*/
public int dfs(int i, int n, Move[] curMove, Move[][] moves) {
if (i == n) {
return 1;
}
int cnt = 0;
here:
for (Move move : moves[i]) {
for (int j = 0; j < i; j++) {
if (!valid(move, curMove[j])) {
continue here;
}
}
curMove[i] = move;
cnt += dfs(i + 1, n, curMove, moves);
}
return cnt;
}
public boolean valid(Move move, Move curMove) {
int x1 = move.x;
int y1 = move.y;
int x2 = curMove.x;
int y2 = curMove.y;
// 步数小的会提前停下来，如果它们坐标相同说明存在在某一时刻使得两个棋子移动到同一个位置上，不合法
for (int i = 0; i < Math.max(move.step, curMove.step); i++) {
if (i < move.step) {
x1 += move.dx;
y1 += move.dy;
}
if (i < curMove.step) {
x2 += curMove.dx;
y2 += curMove.dy;
}
if (x1 == x2 && y1 == y2) {
return false;
}
}
return true;
}
/**
* 生成该棋子所有可能的移动方案
* 起点，方向，步数
*/
public Move[] generateAllValidMove(String pieces, int[] positions) {
int[][] directions = null;
switch (pieces) {
case "rook":
directions = rookDir;
break;
case "bishop":
directions = bishopDir;
break;
case "queen":
directions = queenDir;
break;
default:
}
if (directions == null) {
return null;
}
List<Move> moves = new ArrayList<>();
int x = positions[0];
int y = positions[1];
// 将不移动的情况加入集合
moves.add(new Move(x, y, 0, 0, 0));
// 遍历该棋子允许的行进方向，
for (int[] dir : directions) {
int dx = dir[0];
int dy = dir[1];
int step = 0;
x = positions[0] + dx;
y = positions[1] + dy;
while (x > 0 && x <= 8 && y > 0 && y <= 8) {
moves.add(new Move(positions[0], positions[1], dx, dy, ++step));
x += dx;
y += dy;
}
}
return moves.toArray(new Move[0]);
}
}
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1
输出：1说明：
1 <= n <= 9
将 n 个皇后放在 n x n 的棋盘上，使它们不在同一行、不在同一列并且不在同一斜线上。返回不同的解决方案数量。与 51_N皇后 相比，本题无需返回具体的布局。
关键点：
(i, j)，(a, b)，如果 i + j == a + b || i - j == a - b，那么它们在一条斜线上i - j + n，最大值为 n - 1 + n，数组初始化为 2 * n，i + j 最大值为 n - 1 + n - 1 初始化为 2 * n - 1
/**
* @date 2024-12-01 17:58
*/
public class TotalNQueens52 {
public int res;
public int n;
public boolean[] colIndexSet;
public boolean[] leftDiagonalSet;
public boolean[] rightDiagonalSet;
public int totalNQueens(int n) {
this.n = n;
colIndexSet = new boolean[n];
leftDiagonalSet = new boolean[2 * n];
rightDiagonalSet = new boolean[2 * n - 1];
backTracing(0);
return res;
}
public void backTracing(int row) {
if (row == n) {
res++;
return;
}
for (int col = 0; col < n; col++) {
if (colIndexSet[col] || leftDiagonalSet[row - col + n] || rightDiagonalSet[row + col]) {
continue;
}
colIndexSet[col] = true;
leftDiagonalSet[row - col + n] = true;
rightDiagonalSet[row + col] = true;
backTracing(row + 1);
colIndexSet[col] = false;
leftDiagonalSet[row - col + n] = false;
rightDiagonalSet[row + col] = false;
}
}
}
