算法学习之路|POJ 1068 Parencodings(简单模拟)

简介: 有一个括号串(括号成对),给出一串数字数组p,p[i]表示从左往右第i个右括号左边共有p[i]个左括号,求一个数组w,w[i]表示第i个右括号和其所匹配的左括号之间有多少个左括号(包括这个左括号本身)

题目大意:

有一个括号串(括号成对),给出一串数字数组p,p[i]表示从左往右第i个右括号左边共有p[i]个左括号,求一个数组w,w[i]表示第i个右括号和其所匹配的左括号之间有多少个左括号(包括这个左括号本身)

一个例子:

括号串:    (((()()())))

P 4 5 6 6 6 6

W 1 1 1 4 5 6

思路

用一个vis数组标标记,1表示左括号,0表示右括号,模拟出w数组时用2标记已经用过的左括号,-1标记已经用过的右括号

代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 100
int main()
{
    int p[maxn],w[maxn],vis[maxn];
    int t,n,index,ww;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        memset(w,0,sizeof(w));
        index=1;//标记vis数组
        ww=1;
        p[0]=0;
        w[0]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
            int temp=p[i]-p[i-1];
            for(int j=1;j<=temp;j++)
            {
                vis[index++]=1;
            }
            index++;
        }
        for(int i=1;i<=n*2;i++)//输入数字有n个,说明括号有n对,因此vis数组有2n的长度
        {
            int index2=1;//标记w数组
            if(vis[i]==0)
            {
                vis[i]=-1;
                int x=i;
                while(vis[x]!=1)
                {
                    if(vis[x]==2)
                    {
                        index2++;
                    }
                    x--;
                }
                w[ww++]=index2;
                vis[x]=2;
            }
        }
        for(int i=1;i<=n;i++)
        {
            printf("%d",w[i]);
            if(i<n)
                printf(" ");
        }
        printf("\n");
    }
    return 0;
}

就是简单模拟,没有坑。

目录
相关文章
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!