标签： medium

目标

给你两个正整数数组 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];
    }

}

性能

目标

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。

如果小数部分为循环小数，则将循环的部分括在括号内。

如果存在多个答案，只需返回 任意一个 。

对于所有给定的输入，保证 答案字符串的长度小于 10^4 。

示例 1：

输入：numerator = 1, denominator = 2
输出："0.5"

示例 2：

输入：numerator = 2, denominator = 1
输出："2"

示例 3：

输入：numerator = 4, denominator = 333
输出："0.(012)"

说明：

• -2^31 <= numerator, denominator <= 2^31 - 1
• denominator != 0

思路

有一个分数，分子分母均为整数，以字符串的形式返回小数，如果是循环小数，将循环部分括在括号内。

关键是如何确定从哪里开始循环？记录余数对应的商的下标，如果余数重复出现说明进入了循环节，根据下标来找出循环节。

代码

/**
 * @date 2025-09-24 9:13
 */
public class FractionToDecimal166 {

    public String fractionToDecimal_v1(int numerator, int denominator) {
        long a = numerator;
        long b = denominator;
        if (a % b == 0) {
            return String.valueOf(a / b);
        }
        StringBuilder sb = new StringBuilder();
        if (a * b < 0) {
            sb.append("-");
        }
        a = Math.abs(a);
        b = Math.abs(b);
        long d = a / b;
        sb.append(d);
        long rem = a % b;
        sb.append(".");
        StringBuilder fraction = new StringBuilder();
        Map<Long, Integer> map = new HashMap<>();
        int i = 0;
        while (rem != 0) {
            if (map.get(rem) != null) {
                return sb.append(fraction.substring(0, map.get(rem)))
                        .append("(")
                        .append(fraction.substring(map.get(rem)))
                        .append(")").toString();
            }
            map.put(rem, i);
            rem *= 10;
            if (rem < b) {
                fraction.append(0);
            } else {
                d = rem / b;
                fraction.append(d);
                rem = rem % b;
            }
            i++;
        }
        return sb.append(fraction).toString();
    }

}

性能

目标

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

• 如果 version1 < version2 返回 -1，
• 如果 version1 > version2 返回 1，
• 除此之外返回 0。

示例 1：

输入：version1 = "1.2", version2 = "1.10"
输出：-1
解释：
version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2 < 10，所以 version1 < version2。

示例 2：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：
忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。

示例 3：

输入：version1 = "1.0", version2 = "1.0.0.0"
输出：0
解释：
version1 有更少的修订号，每个缺失的修订号按 "0" 处理。

说明：

• 1 <= version1.length, version2.length <= 500
• version1 和 version2 仅包含数字和 '.'
• version1 和 version2 都是 有效版本号
• version1 和 version2 的所有修订号都可以存储在 32 位整数 中

思路

比较两个由 . 分隔的版本号，每个由 . 隔开的部分称为修订号，从左到右分别比较对应的修订号，如果修订号缺失可认为是 0。如果 version1 > version2 返回 1，version1 < version2 返回 -1，否则返回 0。

使用 split 函数获取修订号，取二者修订号个数的最大值，初始化修订号为 0，如果修订号没有缺失则解析修订号，如果修订号不相等直接返回比较结果，否则继续比较下一个修订号。

代码

/**
 * @date 2025-09-23 8:49
 */
public class CompareVersion165 {

    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int n = Math.max(v1.length, v2.length);
        for (int i = 0; i < n; i++) {
            int i1 = 0;
            int i2 = 0;
            if (i < v1.length) {
                i1 = Integer.parseInt(v1[i]);
            }
            if (i < v2.length) {
                i2 = Integer.parseInt(v2[i]);
            }
            if (i1 > i2) {
                return 1;
            } else if (i1 < i2) {
                return -1;
            }
        }
        return 0;
    }
}

性能

目标

电子表格是一个网格，它有 26 列（从 'A' 到 'Z'）和指定数量的 rows。每个单元格可以存储一个 0 到 10^5 之间的整数值。

请你实现一个 Spreadsheet 类：

• Spreadsheet(int rows) 初始化一个具有 26 列（从 'A' 到 'Z'）和指定行数的电子表格。所有单元格最初的值都为 0 。
• void setCell(String cell, int value) 设置指定单元格的值。单元格引用以 "AX" 的格式提供（例如，"A1"，"B10"），其中字母表示列（从 'A' 到 'Z'），数字表示从 1 开始的行号。
• void resetCell(String cell) 重置指定单元格的值为 0 。
• int getValue(String formula) 计算一个公式的值，格式为 "=X+Y"，其中 X 和 Y 要么 是单元格引用，要么非负整数，返回计算的和。

注意： 如果 getValue 引用一个未通过 setCell 明确设置的单元格，则该单元格的值默认为 0 。

示例 1：

输入：
["Spreadsheet", "getValue", "setCell", "getValue", "setCell", "getValue", "resetCell", "getValue"]
[[3], ["=5+7"], ["A1", 10], ["=A1+6"], ["B2", 15], ["=A1+B2"], ["A1"], ["=A1+B2"]]
输出：
[null, 12, null, 16, null, 25, null, 15]
解释
Spreadsheet spreadsheet = new Spreadsheet(3); // 初始化一个具有 3 行和 26 列的电子表格
spreadsheet.getValue("=5+7"); // 返回 12 (5+7)
spreadsheet.setCell("A1", 10); // 设置 A1 为 10
spreadsheet.getValue("=A1+6"); // 返回 16 (10+6)
spreadsheet.setCell("B2", 15); // 设置 B2 为 15
spreadsheet.getValue("=A1+B2"); // 返回 25 (10+15)
spreadsheet.resetCell("A1"); // 重置 A1 为 0
spreadsheet.getValue("=A1+B2"); // 返回 15 (0+15)

说明：

• 1 <= rows <= 10^3
• 0 <= value <= 10^5
• 公式保证采用 "=X+Y" 格式，其中 X 和 Y 要么是有效的单元格引用，要么是小于等于 10^5 的 非负 整数。
• 每个单元格引用由一个大写字母 'A' 到 'Z' 和一个介于 1 和 rows 之间的行号组成。
• 总共 最多会对 setCell、resetCell 和 getValue 调用 10^4 次。

思路

依题意模拟即可。

代码

/**
 * @date 2025-09-19 8:38
 */
public class Spreadsheet {

    private final int[][] data;

    public Spreadsheet(int rows) {
        data = new int[26][rows + 1];
    }

    public void setCell(String cell, int value) {
        int col = cell.charAt(0) - 'A';
        int row = Integer.parseInt(cell.substring(1));
        data[col][row] = value;
    }

    public void resetCell(String cell) {
        int col = cell.charAt(0) - 'A';
        int row = Integer.parseInt(cell.substring(1));
        data[col][row] = 0;
    }

    public int getValue(String formula) {
        String[] params = formula.substring(1).split("\\+");
        int res = 0;
        for (String param : params) {
            if (param.charAt(0) < 'A' || param.charAt(0) > 'Z') {
                res += Integer.parseInt(param);
            } else {
                int col = param.charAt(0) - 'A';
                int row = Integer.parseInt(param.substring(1));
                res += data[col][row];
            }
        }
        return res;
    }
}

性能

目标

一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。

请你设计一个 TaskManager 类：

TaskManager(vector<vector>& tasks) 初始化任务管理器，初始化的数组格式为 [userId, taskId, priority] ，表示给 userId 添加一个优先级为 priority 的任务 taskId 。

void add(int userId, int taskId, int priority) 表示给用户 userId 添加一个优先级为 priority 的任务 taskId ，输入 保证 taskId 不在系统中。

void edit(int taskId, int newPriority) 更新已经存在的任务 taskId 的优先级为 newPriority 。输入 保证 taskId 存在于系统中。

void rmv(int taskId) 从系统中删除任务 taskId 。输入 保证 taskId 存在于系统中。

int execTop() 执行所有用户的任务中优先级 最高 的任务，如果有多个任务优先级相同且都为 最高 ，执行 taskId 最大的一个任务。执行完任务后，taskId 从系统中 删除 。同时请你返回这个任务所属的用户 userId 。如果不存在任何任务，返回 -1 。

注意 ，一个用户可能被安排多个任务。

示例 1：

输入：
["TaskManager", "add", "edit", "execTop", "rmv", "add", "execTop"]
[[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]
输出：
[null, null, null, 3, null, null, 5]
解释：
TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]]); // 分别给用户 1 ，2 和 3 初始化一个任务。
taskManager.add(4, 104, 5); // 给用户 4 添加优先级为 5 的任务 104 。
taskManager.edit(102, 8); // 更新任务 102 的优先级为 8 。
taskManager.execTop(); // 返回 3 。执行用户 3 的任务 103 。
taskManager.rmv(101); // 将系统中的任务 101 删除。
taskManager.add(5, 105, 15); // 给用户 5 添加优先级为 15 的任务 105 。
taskManager.execTop(); // 返回 5 。执行用户 5 的任务 105 。

说明：

• 1 <= tasks.length <= 10^5
• 0 <= userId <= 10^5
• 0 <= taskId <= 10^5
• 0 <= priority <= 10^9
• 0 <= newPriority <= 10^9
• add ，edit ，rmv 和 execTop 的总操作次数 加起来 不超过 2 * 10^5 次。
• 输入保证 taskId 是合法的。

思路

与 2349.设计数字容器系统 类似，同样是懒删除。

代码

/**
 * @date 2025-09-18 8:42
 */
public class TaskManager3408 {

    static class TaskManager {

        private final Map<Integer, int[]> taskIdMap = new HashMap<>();
        private final PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
            int compare = b[2] - a[2];
            if (compare != 0) {
                return compare;
            }
            return b[1] - a[1];
        });

        public TaskManager(List<List<Integer>> tasks) {
            for (List<Integer> task : tasks) {
                int[] t = {task.get(0), task.get(1), task.get(2)};
                taskIdMap.put(t[1], t);
                q.offer(t);
            }
        }

        public void add(int userId, int taskId, int priority) {
            int[] t = {userId, taskId, priority};
            taskIdMap.put(taskId, t);
            q.offer(t);
        }

        public void edit(int taskId, int newPriority) {
            int[] t = taskIdMap.get(taskId);
            t = new int[]{t[0], t[1], newPriority};
            taskIdMap.put(taskId, t);
            q.offer(t);
        }

        public void rmv(int taskId) {
            taskIdMap.remove(taskId);
        }

        public int execTop() {
            while (!q.isEmpty() && (taskIdMap.get(q.peek()[1]) == null || taskIdMap.get(q.peek()[1])[2] != q.peek()[2]|| taskIdMap.get(q.peek()[1])[0] != q.peek()[0])) {
                q.poll();
            }
            if (q.isEmpty()) {
                return -1;
            }
            int[] task = q.poll();
            taskIdMap.remove(task[1]);
            return task[0];
        }
    }

}

性能