标签： 贪心算法

目标

给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。

请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。

请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。

回文串 指的是从前往后和从后往前读一样的字符串。

示例 1：

输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。

示例 2：

输入：words = ["ab","ty","yt","lc","cl","ab"]
输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。

示例 3：

输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。

说明：

• 1 <= words.length <= 10^5
• words[i].length == 2
• words[i] 仅包含小写英文字母。

思路

有一个字符串数组 words，其元素字符个数为 2，求从中选择任意元素组成回文串的最大长度。

统计每个元素的出现次数，如果数组元素的两个字符不同，要组成回文只能左右对称，计算对称的元素对数 cnt，长度为 cnt * 4。如果元素的两个字符相同，它可以全部放到中间，为了使回文最长，当出现更长的相同字符元素时，可以将原来放中间的个数 centerCnt，放到对称的两边，centerCnt / 2 * 4。

代码

/**
 * @date 2025-05-25 1:03
 */
public class LongestPalindrome2131 {

    public int longestPalindrome(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            char a = word.charAt(0);
            char b = word.charAt(1);
            map.merge(a + String.valueOf(b), 1, Integer::sum);
        }
        int res = 0;
        int centerCnt = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            char a = key.charAt(0);
            char b = key.charAt(1);
            if (a == b) {
                Integer cnt = entry.getValue();
                if (cnt % 2 == 1) {
                    res += centerCnt / 2 * 4;
                    centerCnt = cnt;
                } else {
                    res += cnt / 2 * 4;
                }
            } else {
                int cnt = Math.min(entry.getValue(), map.getOrDefault(b + String.valueOf(a), 0));
                res += cnt * 4;
            }
            entry.setValue(0);
        }
        return res + centerCnt * 2;
    }

}

性能

目标

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [li, ri] 。

每一个 queries[i] 表示对于 nums 的以下操作：

• 将 nums 中下标在范围 [li, ri] 之间的每一个元素 最多 减少 1 。
• 坐标范围内每一个元素减少的值相互 独立 。

零数组 指的是一个数组里所有元素都等于 0 。

请你返回 最多 可以从 queries 中删除多少个元素，使得 queries 中剩下的元素仍然能将 nums 变为一个 零数组 。如果无法将 nums 变为一个 零数组 ，返回 -1 。

示例 1：

输入：nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
输出：1
解释：
删除 queries[2] 后，nums 仍然可以变为零数组。
对于 queries[0] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。
对于 queries[1] ，将 nums[0] 和 nums[2] 减少 1 ，将 nums[1] 减少 0 。

示例 2：

输入：nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
输出：2
解释：
可以删除 queries[2] 和 queries[3] 。

示例 3：

输入：nums = [1,2,3,4], queries = [[0,3]]
输出：-1
解释：
nums 无法通过 queries 变成零数组。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= li <= ri < nums.length

思路

有一个长度为 n 的整数数组，每一次操作可以将给定范围内的任意元素减 1，返回最多可以删掉多少个操作，使得剩下的操作能够将数组中的所有元素变为 0。

对于元素 nums[0] 要将其变为 0 必须要操作 nums[0] 次，且操作范围必须包括 0，因此可以按照操作范围的左端点排序，每次选择右端点最远即覆盖最广的操作区间。可以维护一个由大到小的优先队列，从操作中选出左端点小于等于当前下标的操作，将其右端点放入队列。从队列中取出右端点大于等于当前下标的操作，使用差分数组进行区间修改。

代码

/**
 * @date 2025-05-22 23:02
 */
public class MaxRemoval3362 {

    public int maxRemoval(int[] nums, int[][] queries) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        Arrays.sort(queries, (a, b) -> a[0] - b[0]);
        int n = nums.length;
        int[] diff = new int[n + 1];
        diff[0] = nums[0];
        for (int i = 1; i < n; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
        int num = 0;
        int k = 0;
        for (int i = 0; i < n; i++) {
            num += diff[i];
            while (k < queries.length && queries[k][0] <= i) {
                q.offer(queries[k++][1]);
            }
            while (!q.isEmpty() && q.peek() >= i && num > 0) {
                diff[q.poll() + 1]++;
                num--;
            }
            if (num > 0) {
                return -1;
            }
        }
        return q.size();
    }

}

性能

目标

给你两个由正整数和 0 组成的数组 nums1 和 nums2 。

你必须将两个数组中的 所有 0 替换为 严格 正整数，并且满足两个数组中所有元素的和 相等 。

返回 最小 相等和 ，如果无法使两数组相等，则返回 -1 。

示例 1：

输入：nums1 = [3,2,0,1,0], nums2 = [6,5,0]
输出：12
解释：可以按下述方式替换数组中的 0 ：
- 用 2 和 4 替换 nums1 中的两个 0 。得到 nums1 = [3,2,2,1,4] 。
- 用 1 替换 nums2 中的一个 0 。得到 nums2 = [6,5,1] 。
两个数组的元素和相等，都等于 12 。可以证明这是可以获得的最小相等和。

示例 2：

输入：nums1 = [2,0,2,0], nums2 = [1,4]
输出：-1
解释：无法使两个数组的和相等。

说明：

• 1 <= nums1.length, nums2.length <= 10^5
• 0 <= nums1[i], nums2[i] <= 10^6

思路

有两个非负数组，将其中的 0 替换为正整数并且使两个数组的所有元素和相等，求和的最小值。

判断两个数组中是否存在 0，如果不存在零，判断和是否相等，如果不相等返回 -1。

如果数组中存在零，必须要将其改为正整数，为了使和最小，应改为 1。

如果其中一个数组存在零，判断 修改后 数组的元素和是否大于另一数组的元素和，如果大于则无法使数组和相等返回 -1。

如果两个数组都存在 0，取这两个数组修改后的最大和即可。

代码

/**
 * @date 2025-05-10 20:50
 */
public class MinSum2918 {

    public long minSum(int[] nums1, int[] nums2) {
        long sum1 = 0, sum2 = 0;
        int cnt1 = 0, cnt2 = 0;
        for (int num : nums1) {
            sum1 += num;
            cnt1 += num == 0 ? 1 : 0;
        }
        for (int num : nums2) {
            sum2 += num;
            cnt2 += num == 0 ? 1 : 0;
        }
        if (cnt1 == 0 && cnt2 == 0) {
            return sum1 == sum2 ? sum1 : -1;
        } else if (cnt1 != 0 && cnt2 == 0) {
            return sum1 + cnt1 <= sum2 ? sum2 : -1;
        } else if (cnt1 == 0) {
            return sum1 >= sum2 + cnt2 ? sum1 : -1;
        } else {
            return Math.max(sum1 + cnt1, sum2 + cnt2);
        }
    }

}

性能

目标

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

• 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
• 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

示例 1：

输入：s = "0011"
输出：2
解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2：

输入：s = "010101"
输出：9
解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
执行第二种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。 

说明：

• 1 <= s.length == n <= 10^5
• s[i] 为 '0' 或 '1'

思路

有一个二进制字符串，每次操作可以反转前缀 0 ~ i，成本是 i + 1，也可以反转后缀 i ~ n - 1，成本是 n - i。求使字符串所有字符相等的最小成本。

如何操作才能使字符相等？相等字符是 0 还是 1？操作哪边才能使成本最小？

关键点是想清楚与是 0 还是 1 没有关系，只要相邻的元素值不同，就必须要反转，无非是考虑反转前缀还是后缀，每次操作只影响相邻的元素关系。

代码

/**
 * @date 2025-03-27 1:33
 */
public class MinimumCost2712 {

    public long minimumCost(String s) {
        int n = s.length();
        long res = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                // i 表示反转 0 ~ i - 1，n - i 表示反转 i ~ n - 1
                res += Math.min(i, n - i);
            }
        }
        return res;
    }
}

性能

目标

给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

示例 1：

输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。 

说明：

• 1 <= n, k <= 50

思路

定义 k-avoiding 数组是由不同的正整数组成，并且任意两个元素的和不等于 k 的数组。求长度为 n 的 k-avoiding 数组的最小和。

构造一个长度为 n 的正整数数组，要使和最小，需要从 num = 1 开始选，跳过 k - num。

网友指出可以使用等差数列求和来计算，第一部分是 1 ~ m, m = min(k / 2, n) 和为 m * (m + 1) / 2，第二部分是 k ~ k + n - m - 1，和为 (n - m) * (2 * k + n - m - 1) / 2。

代码

/**
 * @date 2025-03-26 0:13
 */
public class MinimumSum2829 {

    public int minimumSum(int n, int k) {
        int res = 0;
        int length = 0;
        int num = 1;
        Set<Integer> avoiding = new HashSet<>();
        while (length < n) {
            if (avoiding.contains(num)) {
                num++;
                continue;
            }
            if (num < k) {
                avoiding.add(k - num);
            }
            length++;
            res += num;
            num++;
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

说明：

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

思路

有一个整数数组 nums，最多可以对它执行 k 次操作，每次操作可以任选一个数将其左移 1 位。求操作后数组所有元素的最大或值。

操作集中到同一个数上可以将最高有效位移到最高，少一次操作最高位就低一位。问题的关键在于，如果所有数字都有相同的最高有效位，移哪个是不确定的。

这时就需要枚举操作数了，每选择一个操作数就需要重新计算其余元素的或值。由于或运算没有逆运算，我们无法撤销已经或进去的值。

直接的想法是计算或前缀、后缀，枚举所有元素，将其左移 k 次，然后与前后缀进行或运算，取最大值。

网友提供了另一种基于位运算的解法，计算全体元素的或值，同时计算所有 bit 位上存在重复 1 的位置，通过异或运算将当前元素对或值的贡献抵消，然后补上重复位置上的 1。

代码

/**
 * @date 2025-03-21 0:08
 */
public class MaximumOr2680 {

    public long maximumOr_v1(int[] nums, int k) {
        int n = nums.length;
        int or = 0;
        int multiBits = 0;
        for (int i = 0; i < n; i++) {
            multiBits = multiBits | or & nums[i];
            or = or | nums[i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, or ^ nums[i] | multiBits | ((long) nums[i] << k));
        }
        return res;
    }

    public long maximumOr(int[] nums, int k) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        int[] suffix = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] | nums[i - 1];
            suffix[n - i] = suffix[n - i + 1] | nums[n - i];
        }
        long res = 0L;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, prefix[i] | suffix[i + 1] | ((long) nums[i] << k));
        }
        return res;
    }

}

性能

目标

给你一个字符串 s ，下标从 0 开始 ，且长度为偶数 n 。字符串 恰好 由 n / 2 个开括号 '[' 和 n / 2 个闭括号 ']' 组成。

只有能满足下述所有条件的字符串才能称为 平衡字符串 ：

• 字符串是一个空字符串，或者
• 字符串可以记作 AB ，其中 A 和 B 都是 平衡字符串 ，或者
• 字符串可以写成 [C] ，其中 C 是一个 平衡字符串 。

你可以交换 任意 两个下标所对应的括号 任意 次数。

返回使 s 变成 平衡字符串 所需要的 最小 交换次数。

示例 1：

输入：s = "][]["
输出：1
解释：交换下标 0 和下标 3 对应的括号，可以使字符串变成平衡字符串。
最终字符串变成 "[[]]" 。

示例 2：

输入：s = "]]][[["
输出：2
解释：执行下述操作可以使字符串变成平衡字符串：
- 交换下标 0 和下标 4 对应的括号，s = "[]][][" 。
- 交换下标 1 和下标 5 对应的括号，s = "[[][]]" 。
最终字符串变成 "[[][]]" 。

示例 3：

输入：s = "[]"
输出：0
解释：这个字符串已经是平衡字符串。

说明：

• n == s.length
• 2 <= n <= 10^6
• n 为偶数
• s[i] 为'[' 或 ']'
• 开括号 '[' 的数目为 n / 2 ，闭括号 ']' 的数目也是 n / 2

思路

有一个长度为偶数 n 的字符串，有 n / 2 个 [ 和 ]。定义括号能够匹配的字符串是平衡字符串。每一次操作可以交换任意两个下标对应的括号，求将字符串变平衡的最少操作次数。

[[]] 和 [][] 都是平衡字符串，如何确定该与哪个括号交换才能使操作次数最小？对于 ]][[ 和 ][][，第一个与最后一个交换之后变为平衡字符串 [][] 和 [[]]。而如果选择与倒数第二个 [ 交换，会变成 []][，需要再交换一次才能变为平衡字符串。

平衡字符串有这样的性质：其前缀中 [ 的个数总是大于等于 ] 的个数。如果发现 ] 的个数超过 [，那么必须要进行交换。最好将它交换到最后，因为这样可以减少它在前面前缀中对 ] 的贡献，将交换操作尽可能地延后，减小必须进行交换的次数。

也可以先将平衡的括号消掉，剩下的必然是 ]]]......[[[ 的形式。交换一次最多可以抵消 4 个，最少抵消 2 个，即 (stack.size() + 2) / 4。

代码

/**
 * @date 2025-03-17 16:32
 */
public class MinSwaps1963 {

    public int minSwaps_v1(String s) {
        int n = s.length();
        int left = 0, right = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '[') {
                left++;
            } else if (c == ']' && left > 0) {
                left--;
            } else {
                right++;
            }
        }
        return (left + right + 2) / 4;
    }

    public int minSwaps(String s) {
        int n = s.length();
        ArrayDeque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return (stack.size() + 2) / 4;
    }

}

性能