华为 · 双指针 · 算法编程题
华为 双指针 n ≤ 200000 时限 1 秒 / 256 MB

题目描述

在一款智能代码编辑器中,光标用字符 I 表示。初始时给出一个只包含字符 ( 、 ) 、 I 的括号串,其中 恰好出现一次 I 作为光标位置。编辑器支持下列两种删除操作:
_1. backspace:
若光标左侧字符为 `(`,且光标右侧紧跟字符为 `)`,编辑器会一次性删除这对括号;
否则,若光标左侧仍有字符,则仅删除光标左侧一个字符;若左侧为空则无效果。
_2. delete:
若光标右侧存在字符,则删除光标右侧第一个字符;否则无效果。
给定初始括号串以及 k 次操作序列(每次为 backspace 或 delete),请输出全部操作执行完毕后的最终字符串。

输入输出

输入描述
第一行输入两个整数 n,k(1≤ k≤ n≤ 2×10^5) ——初始字符串长度及操作次数。
第二行输入长度为 n 的字符串 s ,仅包含 `(`, `)` 与 `I`,其中 I 恰好出现一次。
接下来 k 行,每行输入一个操作类型:backspace 或 delete。
输出描述
输出一行字符串,表示所有操作结束后的括号串。

样例共 2 组

样例 1
输入
10 3
((()(I))((
backspace
backspace
delete
输出
(((I((
样例 2 · 显然括号都被删除完了。
输入
5 3
((I))
backspace
backspace
delete
输出
I

算法解析依据充分

考点:双指针

数据规模 n ≤ 200000 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:k ≤ 200000,n ≤ 200000
  • 复杂度门槛:只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:双指针

用两个指针协同移动,把两层循环的 O(n²) 优化到 O(n)。

思路框架(双指针 通法 · 非本题专属)

  1. 判断是「对撞指针」(一左一右向中间靠拢)还是「快慢指针」(同向不同速)。
  2. 确定指针移动的单调条件:什么情况下移动左指针,什么情况下移动右指针。
  3. 每一步根据当前指针位置更新答案,直到指针相遇或越界。
  4. 常配合有序性使用:无序时先排序。

实现要点:写成 while (l < r) 循环最清晰,切记每轮至少有一个指针移动,否则死循环。

复杂度:时间 O(n)(排序则 O(n log n)) | 空间 O(1)

该范式的通法易错点

  • 指针移动条件写反,漏解或死循环。
  • 两指针同时移动导致跳过合法解。

对照本题

  • 数据规模 n ≤ 200000,只允许 O(n) 或 O(n log n),且常数要小(注意读入效率)。

样例解读

样例 1:输入 5 3 / ((I)) / backspace / backspace / delete → 输出 I

显然括号都被删除完了。

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

本题来源:华为机试编程模拟题2。

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