标签： 排序

目标

给你一个 回文 字符串 s。

返回 s 的按字典序排列的 最小 回文排列。

如果一个字符串从前往后和从后往前读都相同，那么这个字符串是一个 回文 字符串。

排列 是字符串中所有字符的重排。

如果字符串 a 按字典序小于字符串 b，则表示在第一个不同的位置，a 中的字符比 b 中的对应字符在字母表中更靠前。

如果在前 min(a.length, b.length) 个字符中没有区别，则较短的字符串按字典序更小。

示例 1：

输入： s = "z"
输出： "z"
解释：
仅由一个字符组成的字符串已经是按字典序最小的回文。

示例 2：

输入： s = "babab"
输出： "abbba"
解释：
通过重排 "babab" → "abbba"，可以得到按字典序最小的回文。

示例 3：

输入： s = "daccad"
输出： "acddca"
解释：
通过重排 "daccad" → "acddca"，可以得到按字典序最小的回文。

说明：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成。
• 保证 s 是回文字符串。

思路

有一个回文字符串 s，将其重新排列成回文字符串，使得字典序最小。

记录字符串中字符的出现次数，然后按字典序从两边向中间填充，如果出现次数为奇数，那么该字符为中间元素。

代码

/**
 * @date 2026-07-28 9:03
 */
public class SmallestPalindrome3517 {

    public String smallestPalindrome(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        char[] res = new char[n];
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }
        char mid = 0;
        int cur = 0;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] % 2 == 1) {
                mid = (char) ('a' + i);
            }
            int k = cnt[i] / 2;
            char c = (char) ('a' + i);
            for (int j = 0; j < k; j++) {
                res[cur + j] = c;
                res[n - cur - j - 1] = c;
            }
            cur += k;
        }
        if (n % 2 == 1) {
            res[n / 2] = mid;
        }
        return new String(res);
    }

}

性能

目标

给你一个长度为 n 的整数数组 nums。

构造一个数组 prefixGcd，其中对于每个下标 i：

• 令 mxi = max(nums[0], nums[1], ..., nums[i])。
• prefixGcd[i] = gcd(nums[i], mxi)。

在构造 prefixGcd 之后：

• 将 prefixGcd 按 非递减 顺序排序。
• 通过取 最小的未配对 元素和 最大的未配对 元素来形成数对。
• 重复此过程，直到无法再形成更多数对。
• 对于每个形成的数对，计算 两个元素的最大公约数 gcd。
• 如果 n 是奇数，prefixGcd 数组中的 中间 元素保持 未配对 状态，并应被忽略。

返回一个整数，表示所有形成数对的 最大公约数之和。

术语 gcd(a, b) 表示 a 和 b 的 最大公约数。

示例 1：

输入： nums = [2,6,4]
输出： 2
解释：
构造 prefixGcd：
i nums[i] mxi prefixGcd[i]
0    2    2      2
1    6    6      6
2    4    6      2
prefixGcd = [2, 6, 2]。排序后形成 [2, 2, 6]。
将最小和最大的元素配对：gcd(2, 6) = 2。剩下的中间元素 2 被忽略。因此，总和为 2。

示例 2：

输入： nums = [3,6,2,8]
输出： 5
解释：
构造 prefixGcd：
i nums[i] mxi prefixGcd[i]
0    3     3      3
1    6     6      6
2    2     6      2
3    8     8      8
prefixGcd = [3, 6, 2, 8]。排序后形成 [2, 3, 6, 8]。
形成数对：gcd(2, 8) = 2 和 gcd(3, 6) = 3。因此，总和为 2 + 3 = 5。

说明：

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

思路

有一个正整数数组 nums，构造数组 prefixGcd，prefixGcd[i] = gcd(maxi, nums[i])，其中 maxi 为 [0, i] 的最大值。将 prefixGcd 排序后首尾配对，忽略中间未配对元素，求每对 gcd 之和。

根据题目模拟即可。

代码

/**
 * @date 2026-07-16 9:34
 */
public class GcdSum3867 {

    public long gcdSum(int[] nums) {
        int n = nums.length;
        int[] prefixGcd = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, nums[i]);
            prefixGcd[i] = gcd(max, nums[i]);
        }
        Arrays.sort(prefixGcd);
        long res = 0;
        int l = 0, r = n - 1;
        while (l < r) {
            res += gcd(prefixGcd[l++], prefixGcd[r--]);
        }
        return res;
    }

    public int gcd(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }
}

性能

目标

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。

示例：

输入：intervals = [[1,4],[3,6],[2,8]]
输出：2
解释：区间 [3,6] 被区间 [2,8] 覆盖，所以它被删除了。

说明：

• 1 <= intervals.length <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• 对于所有的 i != j：intervals[i] != intervals[j]

思路

有一个区间列表，删除被其它区间覆盖的区间，返回剩余的区间。区间 [a, b] 被区间[c, d] 覆盖需满足 c <= a && b <= d。

根据左端点从小到大排序，右端点从大到小排序。按顺序遍历排序后的数组，当前区间的左端点一定大于等于之前的区间的左端点，只需要判断右端点是否超过前面记录的最长右端点即可。

代码

/**
 * @date 2026-07-06 9:00
 */
public class RemoveCoveredIntervals1288 {

    public int removeCoveredIntervals(int[][] intervals) {
        int n = intervals.length;
        Arrays.sort(intervals, (a, b) -> {
            int compare = a[0] - b[0];
            return compare != 0 ? compare : b[1] - a[1];
        });
        int r = intervals[0][1];
        int res = 0;
        for (int i = 1; i < n; i++) {
            if (intervals[i][1] <= r) {
                res++;
            } else {
                r = intervals[i][1];
            }
        }
        return n - res;
    }
}

性能

目标

给你一个正整数数组 arr 。请你对 arr 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：

• arr 中 第一个 元素必须为 1 。
• 任意相邻两个元素的差的绝对值 小于等于 1 ，也就是说，对于任意的 1 <= i < arr.length （数组下标从 0 开始），都满足 abs(arr[i] - arr[i - 1]) <= 1 。abs(x) 为 x 的绝对值。

你可以执行以下 2 种操作任意次：

• 减小 arr 中任意元素的值，使其变为一个 更小的正整数 。
• 重新排列 arr 中的元素，你可以以任意顺序重新排列。

请你返回执行以上操作后，在满足前文所述的条件下，arr 中可能的 最大值 。

示例 1：

输入：arr = [2,2,1,2,1]
输出：2
解释：
我们可以重新排列 arr 得到 [1,2,2,2,1] ，该数组满足所有条件。
arr 中最大元素为 2 。

示例 2：

输入：arr = [100,1,1000]
输出：3
解释：
一个可行的方案如下：
1. 重新排列 arr 得到 [1,100,1000] 。
2. 将第二个元素减小为 2 。
3. 将第三个元素减小为 3 。
现在 arr = [1,2,3] ，满足所有条件。
arr 中最大元素为 3 。

示例 3：

输入：arr = [1,2,3,4,5]
输出：5
解释：数组已经满足所有条件，最大元素为 5 。

说明：

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

思路

有一个正整数数组 arr，可以将任意元素变成比它更小的正整数，也可以按任意顺序重新排列元素。需要将 arr 变成目标数组，使得第一个元素为 1，且相邻元素差的绝对值不超过 1。返回目标数组可能的最大值。

根据题目要求，第一个元素必须是 1，且相邻元素差的绝对值不超过 1，要使元素值变大只能 +1，且该元素只能由大于等于它的元素转化而来。

贪心策略，从小到大排序数组，遍历数组记录最大值，由于元素值都大于 0，都可以操作成 1，当元素值小于最大值时直接跳过，否则，将元素操作成最大值加一。越大的元素越晚操作，可以使最大值更大。

由于最大值不超过 n，可以将大于 n 的元素都视为 n，这样可以使用计数排序优化。

代码

/**
 * @date 2026-06-29 18:11
 */
public class MaximumElementAfterDecrementingAndRearranging1846 {

    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int res = 0;
        for (int num : arr) {
            if (num <= res) {
                continue;
            }
            res++;
        }
        return res;
    }

}

性能

目标

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

注意：Tony 可以按任意顺序购买雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

你必须使用计数排序解决此问题。

示例 1：

输入：costs = [1,3,2,4,1], coins = 7
输出：4
解释：Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

输入：costs = [10,6,8,7,7,8], coins = 5
输出：0
解释：Tony 没有足够的钱买任何一支雪糕。

示例 3：

输入：costs = [1,6,3,1,2,5], coins = 20
输出：6
解释：Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

说明：

• costs.length == n
• 1 <= n <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= coins <= 10^8

思路

costs[i] 表示第 i 支雪糕的数量，求使用现金 coins 所能购买雪糕的最大数量。

贪心策略：优先购买价格较低的雪糕。使用计数排序记录每种价格的雪糕数量，从小到大遍历价格，累加当前所能购买的雪糕数量，如果超过剩余金额直接返回。

代码

/**
 * @date 2026-06-22 9:27
 */
public class MaxIceCream1833 {

    public int maxIceCream_v1(int[] costs, int coins) {
        int max = 0;
        for (int cost : costs) {
            max = Math.max(max, cost);
        }
        int[] cnt = new int[max + 1];
        for (int cost : costs) {
            cnt[cost]++;
        }
        int res = 0;
        for (int i = 1; i < cnt.length; i++) {
            if (cnt[i] == 0) {
                continue;
            }
            if (coins < i) {
                return res;
            }
            int amount = Math.min(coins / i, cnt[i]);
            coins -= amount * i;
            res += amount;
        }
        return res;
    }

}

性能