作者： admin

目标

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

给你一个数组 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;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是 0 到 9 之间（两者都包含）的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

1. nums 初始包含 n 个元素。如果 n == 1 ，终止 操作。否则，创建 一个新的下标从 0 开始的长度为 n - 1 的整数数组 newNums 。
2. 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] 赋值 为 (nums[i] + nums[i+1]) % 10 ，% 表示取余运算。
3. 将 newNums 替换 数组 nums 。
4. 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

示例 1：

输入：nums = [1,2,3,4,5]
输出：8
解释：
上图展示了得到数组三角和的过程。

示例 2：

输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，数组的三角和为这个元素自己。

说明：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

思路

有一个长度为 n 的数组，将 nums[i] 替换为 (nums[i] + nums[i + 1]) % 10，得到一个长度为 n - 1 的数组，反复执行这一过程，最终得到数组的三角和。

定义 dp[i] 表示 [i, n) 的三角和， 状态转移方程为 dp[i] = (dp[i] + dp[i + 1]) % 10。

代码

/**
 * @date 2025-09-30 8:44
 */
public class TriangularSum2221 {

    public int triangularSum(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                nums[j] = (nums[j] + nums[j + 1]) % 10;
            }
        }
        return nums[0];
    }
}

性能