月度归档： 2025 年 10 月

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

• 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

示例 1：

输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。

示例 2：

输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。

说明：

• 1 <= nums.length, value <= 10^5
• -10^9 <= nums[i] <= 10^9

思路

有一个数组，可以执行 任意 次操作，每次操作可以加上或者减去 value，求数组中缺失的最小非负整数的最大值。

关键点是想清楚，只要余数相同就能够操作成该数字，剩下的就是对余数的计数了。

代码

/**
 * @date 2025-10-16 8:46
 */
public class FindSmallestInteger2598 {

    public int findSmallestInteger(int[] nums, int value) {
        int[] cnt = new int[value];
        for (int num : nums) {
            int rem = num % value;
            rem = rem >= 0 ? rem : rem + value;
            cnt[rem]++;
        }
        int res = 0;
        while (true) {
            int rem = res % value;
            if (cnt[rem] > 0) {
                cnt[rem]--;
            } else {
                return res;
            }
            res++;
        }
    }

}

性能

目标

一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就 不能 使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用 一次 。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。

示例 1：

输入：power = [1,1,3,4]
输出：6
解释：
可以使用咒语 0，1，3，伤害值分别为 1，1，4，总伤害值为 6 。

示例 2：

输入：power = [7,1,6,6]
输出：13
解释：
可以使用咒语 1，2，3，伤害值分别为 1，6，6，总伤害值为 13 。

说明：

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

思路

有一个数组 power 表示咒语的伤害值，魔法师使用其中任意咒语后，就无法再使用伤害值 +1 +2 -1 -2 的咒语，每个咒语只能使用一次，求伤害值的最大值。

使用哈希表记录伤害值相同的和，创建新数组（不包含重复伤害值），根据伤害值排序。如果不选当前伤害值，状态可以从后面转移而来，如果选则从后面大于当前伤害值 + 2 的转移而来。

代码

/**
 * @date 2025-10-11 8:57
 */
public class MaximumTotalDamage3186 {

    public long maximumTotalDamage(int[] power) {
        Map<Integer, Long> sum = new HashMap<>();
        for (int i : power) {
            sum.merge(i, (long) i, Long::sum);
        }
        int n = sum.size();
        int[] powers = new int[n];
        int i = 0;
        for (Integer damage : sum.keySet()) {
            powers[i++] = damage;
        }
        Arrays.sort(powers);
        long[] mem = new long[n + 1];
        mem[n - 1] = sum.get(powers[n - 1]);
        for (int j = n - 2; j >= 0; j--) {
            int k = j;
            while (k < n && powers[k] - powers[j] <= 2) {
                k++;
            }
            mem[j] = Math.max(mem[j + 1], mem[k] + sum.get(powers[j]));
        }
        return mem[0];
    }

}

性能

目标

在神秘的地牢中，n 个魔法师站成一排。每个魔法师都拥有一个属性，这个属性可以给你提供能量。有些魔法师可能会给你负能量，即从你身上吸取能量。

你被施加了一种诅咒，当你从魔法师 i 处吸收能量后，你将被立即传送到魔法师 (i + k) 处。这一过程将重复进行，直到你到达一个不存在 (i + k) 的魔法师为止。

换句话说，你将选择一个起点，然后以 k 为间隔跳跃，直到到达魔法师序列的末端，在过程中吸收所有的能量。

给定一个数组 energy 和一个整数k，返回你能获得的 最大 能量。

示例 1：

输入： energy = [5,2,-10,-5,1], k = 3
输出： 3
解释：可以从魔法师 1 开始，吸收能量 2 + 1 = 3。

示例 2：

输入： energy = [-2,-3,-1], k = 2
输出： -1
解释：可以从魔法师 2 开始，吸收能量 -1。

说明：

• 1 <= energy.length <= 10^5
• -1000 <= energy[i] <= 1000
• 1 <= k <= energy.length - 1

思路

有 n 个魔法师站成一排，每个魔法师会吸取/提供能量并将你传送到第 i + k 个魔法师的位置，任选一个魔法师作为起点，求能够获得的最大能量。

求 k 个间隔为 k 的后缀和，取过程中产生的最大值。

代码

/**
 * @date 2025-10-10 9:03
 */
public class MaximumEnergy3147 {

    public int maximumEnergy(int[] energy, int k) {
        int n = energy.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < k; i++) {
            int sum = 0;
            for (int j = n - 1 - i; j >= 0; j -= k) {
                sum += energy[j];
                res = Math.max(res, sum);
            }
        }
        return res;
    }

}

性能

目标

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

说明：

• n == spells.length
• m == potions.length
• 1 <= n, m <= 10^5
• 1 <= spells[i], potions[i] <= 10^5
• 1 <= success <= 10^10

思路

有 n 个咒语 和 m 瓶药水，对于每一个咒语，如果它的强度 spells[i] 与 药水能量强度 potions[j] 的乘积 大于等于 success 称为一个成功的组合，返回每个咒语的成功组合数。

将药水按强度排序，二分查找最后一个不成功组合的下标，成功的组合数为 m - (index + 1)。

代码

/**
 * @date 2025-10-09 11:32
 */
public class SuccessfulPairs2300 {

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = potions.length;
        for (int i = 0; i < spells.length; i++) {
            int index = bs(potions, spells[i], success);
            spells[i] = n - 1 - index;
        }
        return spells;
    }

    public int bs(int[] potions, long spell, long success) {
        int r = potions.length - 1;
        int l = 0;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (spell * potions[m] >= success) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

}

性能