【题解】—— LeetCode一周小结50

🌟欢迎来到 我的博客 —— 探索技术的无限可能！

🌟博客的简介（文章目录）

【题解】—— 每日一道题目栏

上接：【题解】—— 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});
        }

        // 模拟，直到堆顶是 mx
        for (; 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