题解 | #小苯的IDE括号问题（easy）#

小苯的IDE括号问题（easy）

https://www.nowcoder.com/practice/0a526c7863474220aaef082ab5f2a00a

题目链接

小苯的IDE括号问题（easy）

题目描述

在一个特殊的代码编辑器中，光标由字符 'I' 表示。给定一个初始字符串，它由 '('、')' 和一个 'I' 组成。编辑器支持两种操作：

backspace:
- 如果光标左侧是 '(' 且右侧是 ')'，则同时删除这对括号。
- 否则，如果光标左侧有字符，则仅删除左侧的第一个字符。
- 如果光标左侧没有字符，则无效果。
delete:
- 如果光标右侧有字符，则删除右侧的第一个字符。
- 否则，无效果。

给定初始字符串和一系列操作，要求输出执行所有操作后最终的字符串。

输入:

第一行输入两个整数 $n$ 和 $m$ ，分别代表初始字符串的长度和操作次数。
第二行输入长度为 $n$ 的字符串。
接下来 $m$ 行，每行输入一个操作："backspace" 或 "delete"。

输出:

输出一行字符串，表示最终结果。

解题思路

这道题本质上是模拟一个光标在文本中的移动和编辑过程。直接对字符串进行操作（如删除字符）效率较低，因为每次删除都可能导致后续字符的移动，时间复杂度较高。

一个更高效的思路是，将光标 'I' 作为分割点，维护光标左右两边的字符序列。我们可以使用两个双端队列（Deque） 来分别存储光标左侧和右侧的字符。

left_q：一个双端队列，存储光标左侧的所有字符。队尾的元素是紧邻光标左侧的字符。
right_q：另一个双端队列，存储光标右侧的所有字符。队首的元素是紧邻光标右侧的字符。

算法步骤：

初始化：遍历初始字符串，找到光标 'I' 的位置。将 'I' 左边的字符依次存入 left_q，将 'I' 右边的字符依次存入 right_q。
模拟操作：循环 $m$ 次，对每次操作进行处理：
- backspace:
  - 检查 left_q 的队尾是否为 '(' 且 right_q 的队首是否为 ')'。
  - 如果是，则从 left_q 弹出队尾元素，并从 right_q 弹出队首元素。
  - 否则，如果 left_q 不为空，仅从 left_q 弹出队尾元素。
- delete:
  - 如果 right_q 不为空，从 right_q 弹出队首元素。
输出结果：所有操作结束后，将 left_q 中的所有元素、字符 'I'、以及 right_q 中的所有元素按顺序拼接起来，即为最终的字符串。

使用双端队列的好处是，在队首和队尾进行添加或删除操作的平均时间复杂度都是 $\mathcal{O}(1)$ ，因此整个模拟过程非常高效。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <deque>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    deque<char> left_q, right_q;
    int cursor_pos = -1;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'I') {
            cursor_pos = i;
            break;
        }
        left_q.push_back(s[i]);
    }
    for (int i = cursor_pos + 1; i < n; ++i) {
        right_q.push_back(s[i]);
    }

    for (int i = 0; i < m; ++i) {
        string op;
        cin >> op;
        if (op == "backspace") {
            if (!left_q.empty() && !right_q.empty() && left_q.back() == '(' && right_q.front() == ')') {
                left_q.pop_back();
                right_q.pop_front();
            } else if (!left_q.empty()) {
                left_q.pop_back();
            }
        } else { // delete
            if (!right_q.empty()) {
                right_q.pop_front();
            }
        }
    }

    for (char c : left_q) {
        cout << c;
    }
    cout << 'I';
    for (char c : right_q) {
        cout << c;
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String s = sc.next();

        Deque<Character> leftQ = new LinkedList<>();
        Deque<Character> rightQ = new LinkedList<>();

        int cursorPos = s.indexOf('I');
        for (int i = 0; i < cursorPos; i++) {
            leftQ.addLast(s.charAt(i));
        }
        for (int i = cursorPos + 1; i < n; i++) {
            rightQ.addLast(s.charAt(i));
        }

        for (int i = 0; i < m; i++) {
            String op = sc.next();
            if (op.equals("backspace")) {
                if (!leftQ.isEmpty() && !rightQ.isEmpty() && leftQ.peekLast() == '(' && rightQ.peekFirst() == ')') {
                    leftQ.pollLast();
                    rightQ.pollFirst();
                } else if (!leftQ.isEmpty()) {
                    leftQ.pollLast();
                }
            } else { // delete
                if (!rightQ.isEmpty()) {
                    rightQ.pollFirst();
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (char c : leftQ) {
            sb.append(c);
        }
        sb.append('I');
        for (char c : rightQ) {
            sb.append(c);
        }
        System.out.println(sb.toString());
    }
}

from collections import deque

def main():
    n, m = map(int, input().split())
    s = input()

    cursor_pos = s.find('I')
    left_q = deque(s[:cursor_pos])
    right_q = deque(s[cursor_pos+1:])

    for _ in range(m):
        op = input()
        if op == "backspace":
            if left_q and right_q and left_q[-1] == '(' and right_q[0] == ')':
                left_q.pop()
                right_q.popleft()
            elif left_q:
                left_q.pop()
        else: # delete
            if right_q:
                right_q.popleft()

    print("".join(left_q) + 'I' + "".join(right_q))

if __name__ == "__main__":
    main()

算法及复杂度

算法：模拟 + 双端队列
时间复杂度： $\mathcal{O}(n+m)$ 。初始化需要 $\mathcal{O}(n)$ 的时间来遍历字符串。后续 $m$ 次操作，每次操作对双端队列的修改都是 $\mathcal{O}(1)$ 的。最后输出结果需要遍历队列，时间与剩余字符数相关，最多为 $\mathcal{O}(n)$ 。
空间复杂度： $\mathcal{O}(n)$ ，用于存储双端队列中的字符。