🌟欢迎来到 我的博客 —— 探索技术的无限可能！
🌟博客的简介（文章目录）
【题解】—— 每日一道题目栏
上接：【题解】—— LeetCode一周小结49
9.判断国际象棋棋盘中一个格子的颜色
题目链接：1812. 判断国际象棋棋盘中一个格子的颜色
给你一个坐标 coordinates ，它是一个字符串，表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。
如果所给格子的颜色是白色，请你返回 true，如果是黑色，请返回 false 。
给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母，第二个字符是数字。
示例 1：
输入：coordinates = “a1”
输出：false
解释：如上图棋盘所示，“a1” 坐标的格子是黑色的，所以返回 false 。
示例 2：
输入：coordinates = “h3”
输出：true
解释：如上图棋盘所示，“h3” 坐标的格子是白色的，所以返回 true 。
示例 3：
输入：coordinates = “c7”
输出：false
提示：
coordinates.length == 2
‘a’ <= coordinates[0] <= ‘h’
‘1’ <= coordinates[1] <= ‘8’
题解：
class Solution {public boolean squareIsWhite(String s) {return s.charAt(0) % 2 != s.charAt(1) % 2;}
}
10.骑士拨号器
题目链接：935. 骑士拨号器
象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
象棋骑士可能的移动方式如下图所示:
我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
因为答案可能很大，所以输出答案模 109 + 7.
示例 1：
输入：n = 1
输出：10
解释：我们需要拨一个长度为1的数字，所以把骑士放在10个单元格中的任何一个数字单元格上都能满足条件。
示例 2：
输入：n = 2
输出：20
解释：我们可以拨打的所有有效号码为[04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61,
67, 72, 76, 81, 83, 92, 94]
示例 3：
输入：n = 3131
输出：136006598
解释：注意取模
提示：
1 <= n <= 5000
题解：
方法：递归 动态规划
class Solution {private static final int MOD = 1_000_000_007;private static final int[][] NEXT = {{4, 6}, {6, 8}, {7, 9}, {4, 8}, {0, 3, 9}, {}, {0, 1, 7}, {2, 6}, {1, 3}, {2, 4}};private static final int[][] memo = new int[5000][10];public int knightDialer(int n) {if (n == 1) {return 10;}int ans = 0;for (int j = 0; j < 10; j++) {ans = (ans + dfs(n - 1, j)) % MOD;}return ans;}private int dfs(int i, int j) {if (i == 0) {return 1;}if (memo[i][j] > 0) { // 之前计算过return memo[i][j];}int res = 0;for (int k : NEXT[j]) {res = (res + dfs(i - 1, k)) % MOD;}return memo[i][j] = res; // 记忆化}
}
11.半有序排列
题目链接：2717. 半有序排列
给你一个下标从 0 开始、长度为 n 的整数排列 nums 。
如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：
选择 nums 中相邻的两个元素，然后交换它们。
返回使 nums 变成 半有序排列 所需的最小操作次数。
排列 是一个长度为 n 的整数序列，其中包含从 1 到 n 的每个数字恰好一次。
示例 1：
输入：nums = [2,1,4,3]
输出：2
解释：可以依次执行下述操作得到半有序排列：
1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。
示例 2：
输入：nums = [2,4,1,3]
输出：3
解释：
可以依次执行下述操作得到半有序排列：
1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。
2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
可以证明，要让 nums 成为半有序排列，不存在执行操作少于 3 次的方案。
示例 3：
输入：nums = [1,3,4,2,5]
输出：0
解释：这个排列已经是一个半有序排列，无需执行任何操作。
提示：
2 <= nums.length == n <= 50
1 <= nums[i] <= 50
nums 是一个 排列
题解：
方法：分类讨论
class Solution {public int semiOrderedPermutation(int[] nums) {int n = nums.length;int p = 0;int q = 0;for (int i = 0; i < n; i++) {if (nums[i] == 1) {p = i;} else if (nums[i] == n) {q = i;}}return p + n - 1 - q - (p > q ? 1 : 0);}
}
12.购买物品的最大开销
题目链接：2931. 购买物品的最大开销
给你一个下标从 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 天，你可以：
选择商店 i 。
购买数组中最右边的物品 j ，开销为 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 <= m == values.length <= 10
1 <= n == values[i].length <= 104
1 <= values[i][j] <= 106
values[i] 按照非递增顺序排序。
题解：
方法：最小堆
class Solution {public long maxSpending(int[][] values) {int m = values.length;int n = values[0].length;PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> values[a[0]][a[1]] - values[b[0]][b[1]]);for (int i = 0; i < m; i++) {pq.offer(new int[]{i, n - 1});}long ans = 0;for (int d = 1; d <= m * n; d++) {int[] p = pq.poll();int i = p[0];int j = p[1];ans += (long) values[i][j] * d;if (j > 0) {pq.offer(new int[]{i, j - 1});}}return ans;}
}
13.K 次乘运算后的最终数组 I
题目链接：3264. K 次乘运算后的最终数组 I
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。
你需要对 nums 执行 k 次操作，每次操作中：
找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
将 x 替换为 x * multiplier 。
请你返回执行完 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]
示例 2：
输入：nums = [1,2], k = 3, multiplier = 4
输出：[16,8]
解释：
操作 结果
1 次操作后 [4, 2]
2 次操作后 [4, 8]
3 次操作后 [16, 8]
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 10
1 <= multiplier <= 5
题解：
方法：优先队列（小根堆）+ 模拟
class Solution {public int[] getFinalState(int[] nums, int k, int multiplier) {PriorityQueue<Integer> pq= new PriorityQueue<>((i, j) -> nums[i] - nums[j] == 0 ? i - j : nums[i] - nums[j]);for (int i = 0; i < nums.length; i++) {pq.offer(i);}while (k-- > 0) {int i = pq.poll();nums[i] *= multiplier;pq.offer(i);}return nums;}
}
14.K 次乘运算后的最终数组 II
题目链接：3266. K 次乘运算后的最终数组 II
给你一个整数数组 nums ，一个整数 k 和一个整数 multiplier 。
你需要对 nums 执行 k 次操作，每次操作中：
找到 nums 中的 最小 值 x ，如果存在多个最小值，选择最 前面 的一个。
将 x 替换为 x * multiplier 。
请你返回执行完 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]
示例 2：
输入：nums = [1,2], k = 3, multiplier = 4
输出：[16,8]
解释：
操作 结果
1 次操作后 [4, 2]
2 次操作后 [4, 8]
3 次操作后 [16, 8]
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 10
1 <= multiplier <= 5
题解：
方法：最小堆模拟+数学公式
class Solution {private static final int MOD = 1_000_000_007;public int[] getFinalState(int[] nums, int k, int multiplier) {if (multiplier == 1) { // 数组不变return nums;}int n = nums.length;int mx = 0;PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));for (int i = 0; i < n; i++) {mx = Math.max(mx, nums[i]);pq.offer(new long[]{nums[i], i});}// 模拟，直到堆顶是 mxfor (; k > 0 && pq.peek()[0] < mx; k--) {long[] p = pq.poll();p[0] *= multiplier;pq.offer(p);}// 剩余的操作可以直接用公式计算for (int i = 0; i < n; i++) {long[] p = pq.poll();nums[(int) p[1]] = (int) (p[0] % MOD * pow(multiplier, k / n + (i < k % n ? 1 : 0)) % MOD);}return nums;}private long pow(long x, int n) {long res = 1;for (; n > 0; n /= 2) {if (n % 2 > 0) {res = res * x % MOD;}x = x * x % MOD;}return res;}
}
15.数组大小减半
题目链接：1338. 数组大小减半
给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。
示例 1：
输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有
{3,5},{3,2},{5,2}。选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
示例 2：
输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。
提示：
1 <= arr.length <= 105
arr.length 为偶数
1 <= arr[i] <= 105
题解：
方法：哈希表
class Solution {public int minSetSize(int[] arr) {Map<Integer, Integer> freq = new HashMap<>();for (int x : arr) {freq.merge(x, 1, Integer::sum); // freq[x]++}List<Integer> cnt = new ArrayList<>(freq.values());cnt.sort((a, b) -> b - a);int s = 0;for (int i = 0; ; i++) {s += cnt.get(i);if (s >= arr.length / 2) {return i + 1;}}}
}
下接：【题解】—— LeetCode一周小结51
