在一款智能代码编辑器中,光标用字符 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。
输出一行字符串,表示所有操作结束后的括号串。
10 3 ((()(I))(( backspace backspace delete
(((I((
5 3 ((I)) backspace backspace delete
I
考点:双指针
数据规模 n ≤ 200000 | 限制 1 秒 / 256MB | 标准输入输出
推荐方向:双指针
用两个指针协同移动,把两层循环的 O(n²) 优化到 O(n)。
思路框架(双指针 通法 · 非本题专属)
实现要点:写成 while (l < r) 循环最清晰,切记每轮至少有一个指针移动,否则死循环。
复杂度:时间 O(n)(排序则 O(n log n)) | 空间 O(1)
该范式的通法易错点
对照本题
样例 1:输入 5 3 / ((I)) / backspace / backspace / delete → 输出 I
显然括号都被删除完了。
解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:华为机试编程模拟题2。