题解 | #小苯的IDE括号问题（easy）#
小苯的IDE括号问题（easy）
https://www.nowcoder.com/practice/0a526c7863474220aaef082ab5f2a00a
题目链接
题目描述
给定一个包含 (, ) 和一个光标 I 的字符串，以及一个操作序列。需要模拟两种删除操作并输出最终的字符串。
backspace:- 如果光标左边是
(，右边是)，则同时删除这对括号。 - 否则，如果光标左边有字符，只删除左边的一个字符。
- 如果左边没字符，则无操作。
- 如果光标左边是
delete:- 如果光标右边有字符，删除右边的一个字符。
- 如果右边没字符，则无操作。
解题思路
直接在字符串上进行删除操作效率很低，因为每次删除都可能导致大量字符的移动。为了高效地模拟光标左右两侧的删除操作，我们可以使用一个经典的数据结构技巧：两个栈（或双端队列）。
- 一个栈
用于存储光标左边的所有字符。
- 另一个栈
用于存储光标右边的所有字符。
为了方便操作，我们让 的栈顶是离光标最近的字符，而
的栈顶也是离光标最近的字符。这意味着，
正常存储（字符串
abc 存为 a,b,c），而 需要反向存储（字符串
def 存为 f,e,d）。
算法步骤如下：
-
初始化：
- 找到光标
I的位置。 - 将光标左边的字符依次压入
- 将光标右边的字符从右到左依次压入
- 找到光标
-
模拟操作：
- 遍历操作序列，对于每个操作：
backspace:- 首先检查特殊情况：
(，)。如果满足，则分别从两个栈中弹出一个元素。 - 如果不满足特殊情况，且
- 首先检查特殊情况：
delete:- 如果
- 如果
-
输出结果：
- 所有操作完成后，最终的字符串由三部分拼接而成：
）。
- 光标
I。
- 所有操作完成后，最终的字符串由三部分拼接而成：
使用两个栈（或 Python 中的列表，Java 中的 ArrayDeque）可以将每次操作的时间复杂度降至均摊 。
代码
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
deque<char> left_part;
deque<char> right_part;
size_t cursor_pos = s.find('I');
for (size_t i = 0; i < cursor_pos; ++i) {
left_part.push_back(s[i]);
}
for (size_t i = n - 1; i > cursor_pos; --i) {
right_part.push_back(s[i]);
}
for (int i = 0; i < q; ++i) {
string op;
cin >> op;
if (op == "backspace") {
if (!left_part.empty() && !right_part.empty() && left_part.back() == '(' && right_part.back() == ')') {
left_part.pop_back();
right_part.pop_back();
} else if (!left_part.empty()) {
left_part.pop_back();
}
} else { // delete
if (!right_part.empty()) {
right_part.pop_back();
}
}
}
for (char c : left_part) {
cout << c;
}
cout << 'I';
while (!right_part.empty()) {
cout << right_part.back();
right_part.pop_back();
}
cout << endl;
return 0;
}
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
String s = sc.next();
Deque<Character> leftPart = new ArrayDeque<>();
Deque<Character> rightPart = new ArrayDeque<>();
int cursorPos = s.indexOf('I');
for (int i = 0; i < cursorPos; i++) {
leftPart.addLast(s.charAt(i));
}
for (int i = n - 1; i > cursorPos; i--) {
rightPart.addLast(s.charAt(i));
}
for (int i = 0; i < q; i++) {
String op = sc.next();
if (op.equals("backspace")) {
if (!leftPart.isEmpty() && !rightPart.isEmpty() &&
leftPart.peekLast() == '(' && rightPart.peekLast() == ')') {
leftPart.pollLast();
rightPart.pollLast();
} else if (!leftPart.isEmpty()) {
leftPart.pollLast();
}
} else { // delete
if (!rightPart.isEmpty()) {
rightPart.pollLast();
}
}
}
StringBuilder result = new StringBuilder();
for (char c : leftPart) {
result.append(c);
}
result.append('I');
while (!rightPart.isEmpty()) {
result.append(rightPart.pollLast());
}
System.out.println(result.toString());
}
}
n, q = map(int, input().split())
s = input()
cursor_pos = s.find('I')
left_part = list(s[:cursor_pos])
right_part = list(s[cursor_pos + 1:])
right_part.reverse()
for _ in range(q):
op = input()
if op == "backspace":
if left_part and right_part and left_part[-1] == '(' and right_part[-1] == ')':
left_part.pop()
right_part.pop()
elif left_part:
left_part.pop()
else: # delete
if right_part:
right_part.pop()
right_part.reverse()
result = "".join(left_part) + 'I' + "".join(right_part)
print(result)
算法及复杂度
- 算法：双栈（或双端队列）模拟。
- 时间复杂度：
，其中
是初始字符串长度，
是操作次数。初始化需要
，每次操作的复杂度是
。
- 空间复杂度：
查看8道真题和解析
