魔法容器管理系统（K0060）- 华为可信认证科目一方向 · 可信 / 系统设计题解 | AlgoMooc

K0060. 魔法容器管理系统

困难

通过率 67% · 提交 33 · 通过 22

可信系统设计Trie

华为可信认证科目一方向改编 · 聚焦「可信 / 系统设计」 · 难度：困难

在一个神奇的魔法世界里，存在一个用于管理魔法咒语的容器。每个咒语都有自己的名字，并且可以进行插入、删除和等操作。容器中的每个咒语都是由一串字符组成。你将设计一个 `MagicContainer` 类，该类支持以下操作： 1. add(keyword)：将一个新的魔法咒语添加到容器中。 2. remove(keyword)：从容器中删除指定的魔法咒语。 3. filter(sentence)：根据前缀匹配删除。注： - 对于前缀匹配，如果容器中有多个字符串能匹配给定的前缀，则删除字典序最小的那个。 - 容器中每个字符串的长度不超过100，容器最多支持添加100,000个咒语。操作描述 1. add(keyword)：向容器中添加一个魔法咒语 `keyword`。如果该咒语已存在，则直接返回此时容器中的所有咒语数量；若该咒语不存在，则将该咒语加入容器，并返回容器中咒语的数量。 2. remove(keyword)：在容器中删除魔法咒语 `keyword`。若该咒语存在，则返回删除后的容器大小；若该咒语不存在，则返回 -1。 3. filter(sentence)：进行字符串前缀匹配，若有多个咒语的前缀匹配上 `sentence`，则删除字典序最小的匹配前缀。如果容器中有多个字符串能够匹配，则删除字典序最小的那个匹配，并返回此匹配的字符串；若没有匹配的前缀，返回 `-1`。

这类题属于华为可信认证科目一方向中「可信 / 系统设计」方向的高频题型，通常考察对「可信 / 系统设计」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

提示：带虚线的词点一下有通俗解释。

输入描述

第一行输入一个整数 Q，表示操作次数。
接下来的 Q 行中，每行包含一个命令 cmd，命令可能是：
- MagicContainer：初始化容器。
- add：添加一个魔法咒语。
- remove：删除一个魔法咒语。
- filter：进行前缀匹配。
对于每个命令，具体的参数如下：
- MagicContainer：不需要任何参数，初始化容器时输出 null。
- add：一个字符串 keyword，表示要添加的魔法咒语。
- remove：一个字符串 keyword，表示要删除的魔法咒语。
- filter：一个字符串 sentence，表示要进行前缀匹配的目标字符串。

输出描述

对于每个命令的执行结果，输出以下内容：

对于 add(keyword)，输出当前容器中魔法咒语的数量。
对于 remove(keyword)，输出删除后的容器大小；若删除失败，输出 -1。
对于 filter(sentence)，该操作会删除匹配此前缀的最小字典序字符串，并输出该字符串。如果没有匹配的字符串，输出 -1。

示例

示例 1

输入示例

5
MagicContainer
add
fireball
add
frostbolt
remove
fireball
filter
fro

输出示例

null
1
2
1
frostbolt

说明：

初始化 MagicContainer：第一行命令初始化了魔法容器，输出 null。
添加 fireball：容器中有一个元素 "fireball"，输出 1。
添加 frostbolt：容器中有两个元素 "fireball" 和 "frostbolt"，输出 2。
删除 fireball：删除 fireball 后，容器中剩下 "frostbolt"，输出 1。
前缀匹配 fro：匹配前缀 fro 时，删除字典序最小的匹配前缀 "frostbolt"，剩下容器为空，输出 "frostbolt"。

示例 2

输入示例

9
MagicContainer
add
test
add
tes
add
testing
remove
tes
filter
te
add
tesseract
remove
test
filter
t

输出示例

null
1
2
3
2
test
2
-1
tesseract

时间限制 1000 ms · 内存限制 128 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

class MagicContainer:
    def __init__(self):
        pass

    def add(self, keyword: str) -> int:
        # 默认返回 0，表示当前容器中魔法咒语数量
        return 0

    def remove(self, keyword: str) -> int:
        # 默认返回 -1，表示该咒语不存在
        return -1

    def filter(self, sentence: str) -> str:
        # 默认返回 "-1"，表示无匹配项
        return "-1"


# 主程序入口
system = None  # 初始化全局变量，表示魔法容器未建立
Q = int(input())  # 输入操作次数

# 逐行处理每条指令
for i in range(Q):
    cmd = input()  # 读取当前指令
    if i == 0 and cmd == "MagicContainer":
        print("null")  # 初始化输出 null
        system = MagicContainer()  # 初始化魔法容器
    elif cmd == 'add':
        keyword = input()  # 读取咒语
        print(system.add(keyword))  # 输出添加后容器中咒语数量
    elif cmd == 'remove':
        keyword = input()  # 读取要删除的咒语
        print(system.remove(keyword))  # 输出删除结果
    elif cmd == "filter":
        sentence = input()  # 读取要匹配的前缀
        print(system.filter(sentence))  # 输出删除的匹配咒语或 -1
    else:
        assert False  # 若出现未定义指令，触发断言错误

写完代码点「提交」，将对全部测试用例判题。

输入描述

输出描述

示例

我的提交