华为 · 哈希 · 算法编程题
华为 哈希 时限 1 秒 / 256 MB

题目描述

在一种复杂的命令行系统中,命令的格式由一个模板字符串定义。模板由关键字、抉择结构 `{...}` 和可选结构 `[...]` 组成,元素间由空格分隔。
您的任务是解析这个模板,找出所有在顶层定义的固定关键字,并计算出每一个固定关键字在任意合法的命令中保证会出现的最小次数。
定义:
1. 关键字: 仅由小写字母组成的字符串。
2. 固定关键字: 在模板的顶层,不被任何括号包裹的关键字。它们是命令的根基。
3. 抉择结构 `{ A | B | ... }`: 表示该位置必须从选项 `A`, `B`, ... 中选择一个。选项本身可以是复杂的子模板。
4. 可选结构 `[ C ]`: 表示 `C` 部分是可选的,可以出现 0 次或 1 次。
保证出现次数的计算规则:
一个关键字 K 的“保证出现次数” C(K) ,是基于以下递归逻辑计算的:
- 首先,统计 K 作为固定关键字出现的次数。
- 然后,遍历模板中的所有抉择结构 `{ A | B | ... }`,如果 K 在每一个选项 A, B, ... 中都保证会出现(即,递归计算出的保证次数都 ≥ 1 ),那么这个抉择结构就为 C(K) 贡献 `+1`。
- 在可选结构 `[...]` 内部的任何关键字,都不被视为“保证出现”。

输入输出

输入描述
- 输入为一行字符串,代表命令格式模板。
- 字符串由关键字、`{`, `}`, `|`, `[`, `]` 和空格组成。
- 输入字符串保证格式合法。
输出描述
- 输出共两行。
- 第一行:按输入顺序,输出所有固定关键字,以单个空格分隔。
- 第二行:对应第一行的每个关键字,输出其保证出现的最小次数以单个空格分隔。

样例共 1 组

样例 1
输入
a b { c | d [ e ] } [ f { g | h } ]
输出
a b
1 1

算法解析依据一般

考点:哈希

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:哈希

用哈希表把「查找/计数」的开销降到 O(1) 均摊。

思路框架(哈希 通法 · 非本题专属)

  1. 一次遍历,把元素作为 key、出现次数/首次位置作为 value 存进哈希表。
  2. 第二次遍历(或边扫边查)拿到需要的信息。
  3. 注意哈希无序:需要按原顺序输出时要额外记录顺序。

实现要点:Python 用 dict / collections.Counter / defaultdict;C++ 用 unordered_map。

复杂度:时间 O(n) 均摊 | 空间 O(n)

该范式的通法易错点

  • 遍历哈希表时依赖了不存在的顺序。
  • 多次查询时每次都重新统计。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:a b { c | d [ e ] } [ f { g | h } ]
  • 输出:a b / 1 1

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2025年秋招-华为-9月3号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解