华为 · 字符串 · 算法编程题
华为 字符串 N ≤ 100 时限 3 秒 / 256 MB

题目描述

作为一名古代奥术师,您正在研究一卷新发现的神秘卷轴。
卷轴上铭刻着一段由古代符文组成的强大文本。
您相信,通过念出特定的咒语(同样由符文组成),可以与卷轴文本产生共鸣,从而释放强大的魔法。
共鸣的强度取决于咒语的符文与卷轴文本的匹配方式和位置。
您的任务是开发一个系统,来精确计算任意咒语与卷轴文本之间的共鸣分数。
共鸣分数由两个核心部分决定:匹配度 和 位置能量 。
1. 匹配度 (Match Score)
根据咒语的符文序列(`incantation`)与卷轴文本序列(`scroll_text`)的匹配情况,分为以下四个等级,按优先级从高到低判断 :
1. 完美谐振 (Perfect Harmonic Match) : 咒语中的所有符文,在卷轴文本中以相同的顺序出现(可以不相邻)。
匹配度得分 : X_1 = 1.0
2. 部分谐振 (Partial Harmonic Match) : 咒语中的所有符文,都能在卷轴文本中找到,但顺序不完全一致。
匹配度得分 : X_2 = 0.8
3. 微弱回响 (Faint Echo) : 只有部分咒语符文能在卷轴文本中找到。设咒语总符文数为 k ,实际匹配到的符文数为 i 。
匹配度得分 : X_3 × (i/k) ,其中 X_3 = 0.6
4. 静默 (Silence) : 不属于以上任何一种情况(即咒语中没有任何一个符文出现在卷轴文本中)。
匹配度得分 : X_4 = 0.0
2. 位置能量 (Positional Energy)
出现在卷轴开头的符文能引导更强大的能量。
设卷轴文本的符文总数为 L 。对于在卷轴中匹配到的一个符文,其 0-索引位置为 p ,则该符文贡献的 位置能量 为:
[ W_p = 1.0 - (p/L-1) ]
(当 L=1 时,分母为0,此时约定 W_0 = 1.0 )
一个咒语的 总位置能量 是其所有匹配到的符文的 位置能量之和 。
如果卷轴文本中包含多个相同的符文,只计算第一次出现的那个符文的位置能量。
3. 最终共鸣分数
共鸣分数由匹配度与总位置能量相乘得到,并需要进行精度处理。
[ Resonance Score = ⌊ (Match Score × Positional Energy) × 10000 ⌋ / 10000 ]
(这相当于将结果小数点后第4位之后的部分直接截断,而不是四舍五入)
注意 :所有符文匹配过程 忽略大小写 。

输入输出

输入描述
输入为单行字符串,由半角管道符 `|` 分隔。
第一个部分是卷轴文本 (`scroll_text`)。
之后的部分是 N 个待测试的咒语 (`incantation_1`, `incantation_2`, ...)。
格式: `scroll_text|incantation_1|incantation_2|...|incantation_N`
卷轴文本和咒语都由一个或多个符文(英文单词)组成,符文之间用空格分隔。
咒语的数量 N < 100 。
输出描述
为每个输入的咒语计算一个共鸣分数。
所有分数在一行内输出,同样由半角管道符 `|` 分隔,并保留4位小数。
格式: `score_1|score_2|...|score_N`

样例共 2 组

样例 1
输入
Advanced Camera: Capture Life in Stunning Detail! Elevate Your Photography with Our Cutting-Edge Camera!|Camera|Camera Photography|digital phone|phone
输出
0.9230|1.2307|0.0000|0.0000
样例 2
输入
buy red running shoes online!|red shoes|buy shoes running|shoes black|Phone
输出
1.0000|1.4000|0.0750|0.0000

算法解析依据充分

考点:字符串

数据规模 N ≤ 100 | 限制 3 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:N ≤ 100
  • 复杂度门槛:允许 O(n³) ~ O(n⁴) 的多重循环,可以放心枚举。
  • 源站时限:3 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:字符串

本题切入点

匹配度判定本质是子序列/集合包含关系:先顺序扫描判定是否为子序列(完美谐振),再判定集合包含(部分谐振),否则按命中符文比例给分,最后叠加位置能量。

按字符逐个处理,或利用字符串的前后缀性质加速匹配。

思路框架(字符串 通法 · 非本题专属)

  1. 明确操作对象是字符还是子串、是否需要保持原顺序。
  2. 子串问题常用双指针 / 滑动窗口;回文问题可用中心扩展或哈希。
  3. 多模式匹配考虑 Trie 或 KMP;只需计数则用哈希表统计字符频次。
  4. 注意字符集大小写敏感性与输入是否带引号。

实现要点:Python 切片 s[l:r+1] 取子串;注意字符串不可变,频繁拼接改用 list。

复杂度:时间 O(n) ~ O(n²) | 空间 O(n)

该范式的通法易错点

  • 下标与切片边界差 1。
  • 忽略了大小写、空白字符的影响。

对照本题

  • 数据规模 N ≤ 100,允许 O(n³) ~ O(n⁴) 的多重循环,可以放心枚举。

样例

样例 1

  • 输入:Advanced Camera: Capture Life in Stunning Detail! Elevate Your Photography with Our Cutting-Edge Camera!|Camera|Camera Photography|digital p
  • 输出:0.9230|1.2307|0.0000|0.0000

样例 2

  • 输入:buy red running shoes online!|red shoes|buy shoes running|shoes black|Phone
  • 输出:1.0000|1.4000|0.0750|0.0000

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

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

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