shelterofly

目标

在神秘的地牢中，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];
    }
}

性能

目标

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

说明:

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

思路

有一个非负整数的数组，返回其中可以组成三角形的三元组。

可以先排序，然后使用二重循环，二分查找满足条件的第三边。

代码

/**
 * @date 2025-09-26 8:52
 */
public class TriangleNumber611 {

    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int t = nums[i] + nums[j];
                int index = bs(nums, j, t);
                res += Math.max(0, index - j);
            }
        }
        return res;
    }

    public int bs(int[] nums, int l, int target) {
        int r = nums.length - 1;
        int m = l + (r - l) / 2;
        while (l <= r) {
            if (nums[m] >= target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

说明：

• 1 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

进阶：

你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

思路

有一个由多行数字排列组成的三角形，每一行比上一行多一个数字，当前数字可以到达下一行下标相同或者下标 +1 的两个数字，求从第一行到最后一行的路径中数字和的最小值。

定义 dp[i][j] 表示从第 i 行 j 列到达底部的最小路径和。dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row[i][j]。

代码

/**
 * @date 2024-08-06 15:42
 */
public class MinimumTotal120 {

    public int minimumTotal_new(List<List<Integer>> triangle) {
        int n = triangle.size();
        int m = triangle.get(n - 1).size();
        int[] dp = new int[m];
        for (int i = 0; i < m; i++) {
            dp[i] = triangle.get(n - 1).get(i);
        }
        for (int i = n - 2; i >= 0; i--) {
            List<Integer> row = triangle.get(i);
            int l = row.size();
            for (int j = 0; j < l; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + row.get(j);
            }
        }
        return dp[0];
    }

}

性能