分类： leetcode

目标

电子表格是一个网格，它有 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];
        }
    }

}

性能

目标

在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。

对于给定的查询单词 query，拼写检查器将会处理两类拼写错误：

• 大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
  • 例如：wordlist = ["yellow"], query = "YellOw": correct = "yellow"
  • 例如：wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
  • 例如：wordlist = ["yellow"], query = "yellow": correct = "yellow"
• 元音错误：如果在将查询单词中的元音 ('a', 'e', 'i', 'o', 'u') 分别替换为任何元音后，能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。
  • 例如：wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
  • 例如：wordlist = ["YellOw"], query = "yeellow": correct = "" （无匹配项）
  • 例如：wordlist = ["YellOw"], query = "yllw": correct = "" （无匹配项）

此外，拼写检查器还按照以下优先级规则操作：

• 当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
• 当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 如果该查询在单词列表中没有匹配项，则应返回空字符串。

给出一些查询 queries，返回一个单词列表 answer，其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。

示例 1：

输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

示例 2:

输入：wordlist = ["yellow"], queries = ["YellOw"]
输出：["yellow"]

说明：

• 1 <= wordlist.length, queries.length <= 5000
• 1 <= wordlist[i].length, queries[i].length <= 7
• wordlist[i] 和 queries[i] 只包含英文字母

思路

有一个单词列表 wordlist，将输入单词 query 按照下面规则转换为列表中的单词：

• 如果 query 在 wordlist 中直接返回
• 如果 query 忽略大小写后在 wordlist 中返回第一个匹配的单词
• 如果 query 忽略大小并且其中的元音替换为任意元音后在 wordlist 中返回第一个匹配的单词
• 如果以上都没有匹配返回空串

依题意模拟即可。创建三个哈希表，key 分别为 原单词、忽略大小写后的单词以及 将元音字母替换为通配符后的单词。

代码

/**
 * @date 2025-09-14 21:25
 */
public class Spellchecker966 {

    public String[] spellchecker(String[] wordlist, String[] queries) {
        Set<String> originSet = new HashSet<>();
        Map<String, List<String>> caseMap = new HashMap<>();
        Map<String, List<String>> vowelMap = new HashMap<>();
        for (String word : wordlist) {
            originSet.add(word);
            String key = word.toLowerCase();
            caseMap.putIfAbsent(key, new ArrayList<>());
            caseMap.get(key).add(word);
            String vowelKey = key.replaceAll("[aeiouAEIOU]", "*");
            vowelMap.putIfAbsent(vowelKey, new ArrayList<>());
            vowelMap.get(vowelKey).add(word);
        }
        for (int i = 0; i < queries.length; i++) {
            String query = queries[i];
            if (originSet.contains(query)) {
                continue;
            }
            String key = query.toLowerCase();
            List<String> caseList = caseMap.get(key);
            if (caseList != null && caseList.size() > 0) {
                queries[i] = caseList.get(0);
                continue;
            }
            List<String> vowelList = vowelMap.get(key.replaceAll("[aeiouAEIOU]", "*"));
            if (vowelList != null && vowelList.size() > 0) {
                queries[i] = vowelList.get(0);
                continue;
            }
            queries[i] = "";
        }
        return queries;
    }

}

性能