标签： medium

目标

给你一个长度为 n 的整数数组 nums，其中 nums 是范围 [0..n - 1] 内所有数字的一个 排列 。

你可以在满足条件 nums[i] AND nums[j] == k 的情况下交换下标 i 和 j 的元素，其中 AND 表示按位与操作，k 是一个非负整数。

返回可以使数组按 非递减 顺序排序的最大值 k（允许进行任意次这样的交换）。如果 nums 已经是有序的，返回 0。

排列 是数组所有元素的一种重新排列。

示例 1：

输入：nums = [0,3,2,1]
输出：1
解释：
选择 k = 1。交换 nums[1] = 3 和 nums[3] = 1，因为 nums[1] AND nums[3] == 1，从而得到一个排序后的排列：[0, 1, 2, 3]。

示例 2：

输入：nums = [0,1,3,2]
输出：2
解释：
选择 k = 2。交换 nums[2] = 3 和 nums[3] = 2，因为 nums[2] AND nums[3] == 2，从而得到一个排序后的排列：[0, 1, 2, 3]。

示例 3：

输入：nums = [3,2,1,0]
输出：0
解释：
只有当 k = 0 时，才能进行排序，因为没有更大的 k 能够满足 nums[i] AND nums[j] == k 的交换条件。

说明：

• 1 <= n == nums.length <= 10^5
• 0 <= nums[i] <= n - 1
• nums 是从 0 到 n - 1 的一个排列。

思路

有一个 0 ~ n - 1 的排列 nums，如果 nums[i] & nums[j] == k，则允许交换元素 nums[i] 与 nums[j]。返回使得 nums 递增所允许的最大的 k，如果排列本来就是有序的返回 0。

任何数与 0 相与都是 0，如果想交换元素 nums[i] 和 nums[j]，可以将元素 0 作为中间元素来交换，一定有解。

所有不在位置上的元素都是需要交换的，k 就是这些元素相与的结果，无论怎么排列，只是相与的顺序不同，结果是一样的。

代码

/**
 * @date 2026-10-23 9:06
 */
public class SortPermutation3644 {

    public int sortPermutation(int[] nums) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                res &= nums[i];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

}

性能

目标

给你一个由小写英文字母组成的字符串 s。

在一次操作中，你可以选择 s 的任意 子字符串（但 不能 是整个字符串），并将其按 非降序字母顺序 进行 排序。

返回使 s 按 非降序 排列所需的 最小 操作次数。如果无法做到，则返回 -1。

示例 1：

输入： s = "dog"
输出： 1
解释：
将子字符串 "og" 排序为 "go"。
现在，s = "dgo"，已按升序排列。因此，答案是 1。

示例 2：

输入： s = "card"
输出： 2
解释：
将子字符串 "car" 排序为 "acr"，得到 s = "acrd"。
将子字符串 "rd" 排序为 "dr"，得到 s = "acdr"，已按升序排列。因此，答案是 2。

示例 3：

输入： s = "gf"
输出： -1
解释：
在给定提示下，无法对 s 进行排序。因此，答案是 -1。

说明：

• 1 <= s.length <= 10^5
• s 仅由小写英文字母组成。

思路

有一个字符串 s，每次操作可以将其子串（不能是整个字符串）按非递减排序，求使整个字符串按非递减排列所需的最小操作次数，如果无法实现返回 -1。

分类讨论：

• 如果 s 本身非递减，操作次数为 0。
• 否则，找出最大字符 max 与 最小字符 min：
  • 如果 s[0] == min || s[n - 1] == max，只需将剩余部分排序即可，操作次数为 1。
  • 如果 s[0] == max && s[n - 1] == min：
  • 如果字符串中有多余的 min 或者 max，可以直接排序前缀 s[0, n - 2] 或后缀 s[1, n - 1] 使得最大或最小归位，然后再排序剩余部分，操作次数为 2。
  • 否则，需要先将 min 与 max 移出来：
    • 如果 n == 2，返回 -1。
    • 否则，将 min 与 前一个的元素交换，排序前缀 s[0, n - 2]，然后再排序后缀 s[1, n - 1]，操作次数为 3。
  • 其余情况，先排序前缀 s[0, n - 2] 再排序后缀 s[1, n - 1] 即可，操作次数为 2。

代码

/**
 * @date 2026-10-21 9:10
 */
public class MinOperations3863 {

    public int minOperations(String s) {
        int max = s.charAt(0);
        int min = max;
        char[] chars = s.toCharArray();
        int[] cnt = new int[26];
        int n = chars.length;
        boolean ordered = true;
        for (char c : chars) {
            if (c < max) {
                ordered = false;
            }
            cnt[c - 'a']++;
            max = Math.max(max, c);
            min = Math.min(min, c);
        }
        if (ordered) {
            return 0;
        } else if (max == s.charAt(n - 1) || min == s.charAt(0)) {
            return 1;
        } else if (max == s.charAt(0) && min == s.charAt(n - 1)) {
            if (n == 2) {
                return -1;
            } else if (cnt[min - 'a'] > 1 || cnt[max - 'a'] > 1) {
                return 2;
            } else {
                return 3;
            }
        }
        return 2;
    }

}

性能

目标

给你两个 正 整数 num 和 sum。

如果一个正整数 n 满足以下两个条件，则称其为 好整数 ：

• n 的位数 恰好 为 num。
• n 的各位数字之和 恰好 为 sum。

一个 好整数 n 的 分数 定义为 n 的各位数字的平方和。

返回一个 字符串 ，表示能获得 最大分数 的 好整数 n。如果有多个可能的整数，返回 最大 的那个。如果不存在这样的整数，返回一个空字符串。

示例 1:

输入: num = 2, sum = 3
输出: "30"
解释:
有 3 个好整数：12、21 和 30。
12 的分数是 12 + 22 = 5。
21 的分数是 22 + 12 = 5。
30 的分数是 32 + 02 = 9。
最大分数是 9，由好整数 30 获得。因此，答案是 "30"。

示例 2:

输入: num = 2, sum = 17
输出: "98"
解释:
有两个好整数：89 和 98。
89 的分数是 82 + 92 = 145。
98 的分数是 92 + 82 = 145。
最大分数是 145。获得此分数的最大好整数是 98。因此，答案是 "98"。

示例 3:

输入: num = 1, sum = 10
输出: ""
解释:
不存在恰好有 1 位数字且各位数字之和为 10 的整数。因此，答案是 ""。

说明:

• 1 <= num <= 2 * 10^5
• 1 <= sum <= 2 * 10^6

思路

定义数位长度为 num，数位之和为 sum 的整数为好整数，好整数的分数定义为各位数字的平方和，返回分数最大的好整数，如果分数相同则返回整数值最大的，如果不存在返回空串。

贪心策略就是取当前位所能取的最大值，余下的补 0。

代码

/**
 * @date 2026-10-14 9:21
 */
public class MaxSumOfSquares3723 {

    public String maxSumOfSquares(int num, int sum) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            int d = Math.min(sum, 9);
            sum -= d;
            num--;
            sb.append(d);
        }
        return sum == 0 ? sb.toString() : "";
    }

}

性能

目标

给你一个整数数组 nums。你可以以任意顺序 重新排列元素 。

数组 arr 的 交替得分 定义为：

• score = arr[0]^2 - arr[1]^2 + arr[2]^2 - arr[3]^2 + ...

在对 nums 重新排列后，返回其 最大可能的交替得分。

示例 1：

输入： nums = [1,2,3]
输出： 12
解释：
nums 的一种可行重排为 [2,1,3]，该排列在所有可能重排中给出了最大交替得分。
交替得分计算如下：
score = 22 - 12 + 32 = 4 - 1 + 9 = 12

示例 2：

输入： nums = [1,-1,2,-2,3,-3]
输出： 16
解释：
nums 的一种可行重排为 [-3,-1,-2,1,3,2]，该排列在所有可能重排中给出了最大交替得分。
交替得分计算如下：
score = (-3)^2 - (-1)^2 + (-2)^2 - (1)^2 + (3)^2 - (2)^2 = 9 - 1 + 4 - 1 + 9 - 4 = 16

说明：

• 1 <= nums.length <= 10^5
• -4 10^4 <= nums[i] <= 4 10^4

思路

有一个下标从 0 开始的整数数组 nums，数组的交替得分定义为 (nums[0]^2 - nums[1]^2) + (nums[2]^2 - nums[3]^2) + …… ，允许对数组重新排序，返回最大可能的交替得分。

依题意，得分为偶数下标元素的平方减去奇数下标元素的平方，要使得分最大，只需奇数下标的平方值最小。将数组替换为元素的平方，然后排序数组，将前 n/2 个元素放在奇数下标即可。

代码

/**
 * @date 2026-10-13 10:20
 */
public class MaxAlternatingSum3727 {

    public long maxAlternatingSum(int[] nums) {
        long res = 0L;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (i < n / 2) {
                res -= nums[i];
            } else {
                res += nums[i];
            }
        }
        return res;
    }
}

性能

目标

给你一个括号字符串 s ，它只包含字符 '(' 和 ')' 。一个括号字符串被称为平衡的当它满足：

• 任何左括号 '(' 必须对应两个连续的右括号 '))' 。
• 左括号 '(' 必须在对应的连续两个右括号 '))' 之前。

比方说 "())"， "())(())))" 和 "(())())))" 都是平衡的， ")()"， "()))" 和 "(()))" 都是不平衡的。

你可以在任意位置插入字符 '(' 和 ')' 使字符串平衡。

请你返回让 s 平衡的最少插入次数。

示例 1：

输入：s = "(()))"
输出：1
解释：第二个左括号有与之匹配的两个右括号，但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。

示例 2：

输入：s = "())"
输出：0
解释：字符串已经平衡了。

示例 3：

输入：s = "))())("
输出：3
解释：添加 '(' 去匹配最开头的 '))' ，然后添加 '))' 去匹配最后一个 '(' 。

示例 4：

输入：s = "(((((("
输出：12
解释：添加 12 个 ')' 得到平衡字符串。

示例 5：

输入：s = ")))))))"
输出：5
解释：在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ，字符串变成平衡字符串 "(((())))))))" 。

说明：

• 1 <= s.length <= 10^5
• s 只包含 '(' 和 ')' 。

思路

定义平衡括号字符串是每一个左括号都对应有两个连续右括号的字符串。有一个括号字符串 s，每次操作可以插入一个 ( 或者 )，求使括号字符串变平衡的最小操作次数。

记录未匹配的左括号数量 lc，遇到连续的右括号直接滑倒结束并计数 rc，贪心策略：

• 如果 lc >= rc，如果 rc 为奇数，需要补一个右括号，操作加一，lc 减去已匹配的数量，rc 置零。
• 否则，每两个右括号匹配需要补一个左括号，操作加 rc / 2，如果 rc 是奇数，需要补一对括号，操作加 2。

代码

/**
 * @date 2026-10-09 9:09
 */
public class MinInsertions1541 {

    public int minInsertions(String s) {
        char[] chars = s.toCharArray();
        int n = s.length();
        int lc = 0, rc = 0, res = 0;
        int i = 0;
        while (i < n) {
            if (chars[i] == '(') {
                lc += 2;
                i++;
            } else {
                while (i < n && chars[i] == ')') {
                    i++;
                    rc++;
                }
            }
            if (lc >= rc) {
                res += rc % 2;
                lc -= rc + rc % 2;
                rc = 0;
            } else {
                rc -= lc;
                int rem = rc % 2;
                res += rc / 2 + (rem == 0 ? 0 : 2);
                rc = 0;
                lc = 0;
            }
        }
        return res + lc;
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4
• 1 <= x <= 10^9

思路

有一个正整数数组 nums，每一次操作可以移除剩余数组的最左或最右元素，求移除元素和等于 x 的最小操作数，如果不存在则返回 -1。

将问题转化为求子数组和为 sum - x 的最大长度，可以使用滑动窗口。

代码

/**
 * @date 2026-09-23 8:49
 */
public class MinOperations1658 {

    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < x) {
            return -1;
        } else if (sum == x) {
            return n;
        }
        int target = sum - x;
        int res = 0;
        int l = 0;
        sum = 0;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while (sum > target) {
                sum -= nums[l++];
            }
            if (sum == target) {
                res = Math.max(res, r - l + 1);
            }
        }
        return res == 0 ? -1 : n - res;
    }

}

性能

目标

给你一个由 正 整数组成的数组 nums，以及一个 正 整数 k。

你可以对 nums 执行 一次 操作，该操作中可以移除任意 不重叠 的前缀和后缀，使得 nums 仍然 非空 。

你需要找出 nums 的 x 值，即在执行操作后，剩余元素的 乘积 除以 k 后的 余数 为 x 的操作数量。

返回一个大小为 k 的数组 result，其中 result[x] 表示对于 0 <= x <= k - 1，nums 的 x 值。

数组的 前缀 指从数组起始位置开始到数组中任意位置的一段连续子数组。

数组的 后缀 是指从数组中任意位置开始到数组末尾的一段连续子数组。

子数组 是数组中一段连续的元素序列。

注意，在操作中选择的前缀和后缀可以是 空的 。

示例 1：

输入： nums = [1,2,3,4,5], k = 3
输出： [9,2,4]
解释：
对于 x = 0，可行的操作包括所有不会移除 nums[2] == 3 的前后缀移除方式。
对于 x = 1，可行操作包括：
    移除空前缀和后缀 [2, 3, 4, 5]，nums 变为 [1]。
    移除前缀 [1, 2, 3] 和后缀 [5]，nums 变为 [4]。
对于 x = 2，可行操作包括：
    移除空前缀和后缀 [3, 4, 5]，nums 变为 [1, 2]。
    移除前缀 [1] 和后缀 [3, 4, 5]，nums 变为 [2]。
    移除前缀 [1, 2, 3] 和空后缀，nums 变为 [4, 5]。
    移除前缀 [1, 2, 3, 4] 和空后缀，nums 变为 [5]。

示例 2：

输入： nums = [1,2,4,8,16,32], k = 4
输出： [18,1,2,0]
解释：
对于 x = 0，唯一 不 得到 x = 0 的操作有：
    移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
    移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 1，唯一的操作是：
    移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
对于 x = 2，可行操作包括：
    移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 3，没有可行的操作。

示例 3：

输入： nums = [1,1,2,1,1], k = 2
输出： [9,6]

说明：

• 1 <= nums[i] <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= k <= 5

思路

有一个正整数数组 nums 和一个正整数 k，每次操作可以移除数组不重叠的前缀与后缀，即保留中间非空的子数组。求子数组元素乘积模 k 的余数为 x 的操作数量。

定义 dp[i][j] 表示 [0, i] 中以 i 为右端点的子数组中模 k 余 j 的个数。使用刷表法更新 dp[i][nums[i] % k]++, dp[i][nums[i] * j % k] += dp[i - 1][j]。

代码

/**
 * @date 2026-09-21 15:19
 */
public class ResultArray3524 {

    public long[] resultArray(int[] nums, int k) {
        int n = nums.length;
        long[][] dp = new long[n][k];
        dp[0][nums[0] % k] = 1;
        long[] res = new long[k];
        res[nums[0] % k]++;
        for (int i = 1; i < n; i++) {
            int rem = nums[i] % k;
            dp[i][rem]++;
            for (int j = 0; j < k; j++) {
                dp[i][(int) ((long) nums[i] * j % k)] += dp[i - 1][j];
            }
            for (int j = 0; j < k; j++) {
                res[j] += dp[i][j];
            }
        }
        return res;
    }

}

性能

目标

给你一个以 (radius, xCenter, yCenter) 表示的圆和一个与坐标轴平行的矩形 (x1, y1, x2, y2) ，其中 (x1, y1) 是矩形左下角的坐标，而 (x2, y2) 是右上角的坐标。

如果圆和矩形有重叠的部分，请你返回 true ，否则返回 false 。

换句话说，请你检测是否 存在 点 (xi, yi) ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。

示例 1 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
输出：true
解释：圆和矩形存在公共点 (1,0) 。

示例 2 ：

输入：radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
输出：false

示例 3 ：

输入：radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
输出：true

说明：

• 1 <= radius <= 2000
• -10^4 <= xCenter, yCenter <= 10^4
• -10^4 <= x1 < x2 <= 10^4
• -10^4 <= y1 < y2 <= 10^4

思路

平面坐标中有一个圆 (radius, xCenter, yCenter) 和一个平行于坐标轴的矩形 (x1, y1, x2, y2)，判断圆和矩形是否重叠。

求出圆心到矩形的最短距离，然后判断最短距离与圆的半径关系。最短距离为 dx^2 + dy^2 = (x - xCenter)^2 + (y - yCenter)^2，要使距离最小，分别使 |dx| 与 |dy| 最小即可。

要使 x1 <= x <= x2 与 xCenter 的距离最小，

• 当 x1 <= xCenter <= x2 时，取 x = xCenter；
• 当 xCenter < x1 时，取 x = x1；
• 当 xCenter > x2 时，取 x = x2；

可简化为 x = Math.max(x1, Math.min(xCenter, x2))，同理 y = Math.max(y1, Math.min(yCenter, y2))。

代码

/**
 * @date 2026-09-22 10:18
 */
public class CheckOverlap1401 {

    public boolean checkOverlap(int radius, int xCenter, int yCenter, int x1, int y1, int x2, int y2) {
        int dx = Math.max(x1, Math.min(xCenter, x2)) - xCenter;
        int dy = Math.max(y1, Math.min(yCenter, y2)) - yCenter;
        return dx * dx + dy * dy <= radius * radius;
    }
}

性能