小苯的IDE括号问题（CD） —–牛客小白月赛87（双链表）

C题：C-小苯的IDE括号问题（easy）_牛客小白月赛87 (nowcoder.com)

D题：D-小苯的IDE括号问题（hard）_牛客小白月赛87 (nowcoder.com)

C题代码：

#includeusing namespace std;const int N = 2e5+10;int n,k;int l[N],r[N];//删除操作void remove(int x){r[l[x]] = r[x];l[r[x]] = l[x];}int main(){cin.tie(nullptr)->ios::sync_with_stdio(false);cin >> n >> k;string s;cin >> s;//做一个标记头尾哨子s = "L" + s + "R";int pos = 0; //标记位置，用来去找鼠标I的位置for(int i=1;i<s.size();i++){if(s[i] == 'I'){pos = i;break;}}r[0] = s.size()-1,l[s.size()-1] = 0;for(int i=1;i> str;if(str == "backspace"){if(s[l[pos]] == '(' && s[r[pos]] == ')'){remove(l[pos]);remove(r[pos]);}else{if(s[l[pos]] == 'L') continue;remove(l[pos]);}}else{if(s[r[pos]] == 'R') continue;remove(r[pos]);}}for(int i=r[0];i!=s.size()-1;i=r[i])cout << s[i];return 0;}

D题代码：

#includeusing namespace std;const int N = 2e5+10;int l[N],r[N];int n,k;void remove(int x){r[l[x]] = r[x];l[r[x]] = l[x];}int main(){cin.tie(nullptr)->ios::sync_with_stdio(false);cin >> n >> k;string s;cin >> s;s = "L" + s + "R";int pos = 0;for(int i=1;i<=n;i++){if(s[i] == 'I'){pos = i;break;}}//这里对于C题换了一种写法，两种都可以r[0] = s.size()-1,l[s.size()-1] = 0;for (int i = 1; i > str;if(str == "backspace"){if(s[l[pos]] == '(' && s[r[pos]] == ')'){remove(l[pos]);remove(r[pos]);}else{if(s[l[pos]] == 'L') continue;remove(l[pos]);}}else if(str == "delete"){//注意：这块一定要仔细读题不要落条件，不写会超时（本人的错）if(s[r[pos]] == 'R') continue;remove(r[pos]);}else if(str == "->"){if(s[r[pos]] != 'R'){//交换只改变原数组，不改变双链表//删除只改变双链表，不改变原数组 int idx = r[pos];swap(s[idx],s[pos]);pos = idx; //一定要挪动一下pos的位置}}else{if(s[l[pos]]!='L'){int idx = l[pos];//这里交换原数组不会改变，双链表数组swap(s[idx],s[pos]);pos = idx;}}}//遍历链表for(int i=r[0];i!=s.size()-1; i=r[i])cout << s[i];return 0;}

双链表 一定要多动手模拟，手动去做一下删除和插入操作，自己就会深有体会