首页 > 试题广场 >

小苯的IDE括号问题(easy)

[编程题]小苯的IDE括号问题(easy)
  • 热度指数:1337 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}在一款智能代码编辑器中,光标用字符 I 表示。初始时给出一个只包含字符 \text{(}\text{)}\text{I} 的括号串,其中 恰好出现一次 I 作为光标位置。编辑器支持下列两种删除操作:
{\hspace{23pt}}_\texttt{1.}\, backspace
{\hspace{38pt}}\circ\,若光标左侧字符为 `(`,且光标右侧紧跟字符为 `)`,编辑器会一次性删除这对括号;
{\hspace{38pt}}\circ\,否则,若光标左侧仍有字符,则仅删除光标左侧一个字符;若左侧为空则无效果。
{\hspace{23pt}}_\texttt{2.}\, delete
{\hspace{38pt}}\circ\,若光标右侧存在字符,则删除光标右侧第一个字符;否则无效果。

\hspace{15pt}给定初始括号串以及 k 次操作序列(每次为 backspacedelete),请输出全部操作执行完毕后的最终字符串。

输入描述:
\hspace{15pt}第一行输入两个整数 n,k\left(1\leqq k\leqq n\leqq 2\times10^{5}\right)——初始字符串长度及操作次数。 
\hspace{15pt}第二行输入长度为 n 的字符串 s,仅包含 `(`, `)` 与 `I`,其中 I 恰好出现一次。
\hspace{15pt}接下来 k 行,每行输入一个操作类型:backspacedelete


输出描述:
\hspace{15pt}输出一行字符串,表示所有操作结束后的括号串。
示例1

输入

10 3
((()(I))((
backspace
backspace
delete

输出

(((I((
示例2

输入

5 3
((I))
backspace
backspace
delete

输出

I

说明

显然括号都被删除完了。

备注:

我就不懂了,怎么都用双端队列。用数组标记删除位置再输出未删除的字符不是更简单?没学过队列也能做。
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, k;
    string s, op;
    cin >> n >> k;
    cin >> s;
    //用数组标记当前位置是否被删除
    vector<bool>isDelete(n, false);
    int pos = s.find('I');//光标位置
    int l = pos - 1, r = pos + 1;//定义左指针和右指针
    while (k--) {
        cin >> op;
        //按照题目规则操作即可,每删除一次指针移动一步
        if (op == "backspace") {
            if (l >= 0 && r < n && s[l] == '(' && s[r] == ')') {
                isDelete[l--] = true;
                isDelete[r++] = true;
            } else if (l >= 0)
                isDelete[l--] = true;
        } else if (r < n)
            isDelete[r++] = true;
    }
    //由于n比较大,所以这里不判断标记,直接扫描未删除的区间
    for (int i = 0; i <= l; i++)cout << s[i];
    cout << 'I';//不要忘记中间的I
    for (int i = r; i < n; i++)cout << s[i];
}


发表于 2025-11-11 22:18:45 回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//感觉不是很难
//既然是用双指针的话,那就加上两个指针进行移动就行,这样就不用通过删除字符串上的字符构建新字符串的复杂操作了
int main() {
    int n,k;
    scanf("%d %d",&n,&k);
    char* string=malloc(sizeof(char)*(n+1));//读取字符串
    scanf("%s",string);

    int I_pos;//找I字符所在下标的位置
    int a,b;     //指向I当前位置的左右两边
    for (int i=0; i<n; i++) {
        if(string[i]=='I')
        {
            I_pos=i;
            a=I_pos-1;
            b=I_pos+1;
        }
    }
    for (int caozuo=1; caozuo<=k; caozuo++) {  //读取每一次操作
        char caozuo_string[10];
        scanf("%s",caozuo_string);

        if (strcmp(caozuo_string, "backspace")==0) {    //根据操作指令进行双指针移动就行了
            if (a>=0) {   //ab不能超出范围
                if (string[a]=='('&&string[b]==')') {
                    a--;//左右同时移动,相当于删除了
                    b++;
                }else {   //这种情况只需要删除a这边的就行了
                    a--;
                }
            }
        }else if (strcmp(caozuo_string, "delete")==0) {  //strcmp等于0才是相等啊
            if(b<n)   //b不超出范围就可以删除右边的
            {
                b++;
            }
        }
    }

    //然后输出0-a,b-n的部分剩余的内容即可
    for (int i=0; i<=a; i++) {
        printf("%c",string[i]);
    }
    printf("I");
    for (int i=b; i<n; i++) {
        printf("%c",string[i]);
    }

    return 0;
}

发表于 2025-10-19 14:22:25 回复(0)
用nextLine() 获取总超时,换成next()就行,学到了
发表于 2025-09-26 04:40:13 回复(0)
import java.util.*; 
import java.io.*;

// I两侧存为两个双端队列进行操作
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String[] s=bf.readLine().split(" ");
        int n=Integer.parseInt(s[0]);
        int m=Integer.parseInt(s[1]);
        String input=bf.readLine();
        int indexI=input.indexOf('I');

        Deque<Character> d1=new LinkedList<>();
        Deque<Character> d2=new LinkedList<>();

        for(int i=0;i<n;i++){
            if(i<indexI){
                d1.offerLast(input.charAt(i));
            }
            if(i>indexI){
                d2.offerLast(input.charAt(i));
            }
        }

        while(m>0){
            if("backspace".equals(bf.readLine())){
                if(!d1.isEmpty()&&!d2.isEmpty()&&d1.peekLast()=='('&&d2.peekFirst()==')'){
                    d1.removeLast();
                    d2.removeFirst();
                }
                else{
                    d1.pollLast();
                }
            }else{
                d2.pollFirst();
            }
            m--;
        }

        for(char c:d1){
            System.out.print(c);
        }
        System.out.print('I');
        while(d2.peekFirst()!=null)
        {
            System.out.print(d2.pollFirst());
        }
        System.out.println();
    }
}

发表于 2025-08-28 23:18:41 回复(1)
n, k = map(int, input().split())
s = input()

# 找到光标位置
cursor_pos = s.find("I")

# 将字符串分为左右两部分,不包括光标
left_part = s[:cursor_pos]
right_part = s[cursor_pos + 1 :]

for _ in range(k):
    operation = input().strip()

    if operation == "delete":
        # delete操作:删除光标右侧一个字符(如果存在)
        if right_part:  # 如果右侧有字符
            right_part = right_part[1:]

    elif operation == "backspace":
        # backspace操作
        if left_part and right_part and left_part[-1] == "(" and right_part[0] == ")":
            # 如果光标左右是一对匹配的括号,则同时删除
            left_part = left_part[:-1]
            right_part = right_part[1:]
        elif left_part:  # 如果左侧有字符
            left_part = left_part[:-1]

# 输出最终结果
result = left_part + "I" + right_part
print(result)

发表于 2025-08-27 10:02:13 回复(0)