专栏首页xingoo, 一个梦想做发明家的程序员剑指OFFER之栈的压入、弹出序列(九度OJ1366)

剑指OFFER之栈的压入、弹出序列(九度OJ1366)

题目描述:

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

输入:

每个测试案例包括3行:

第一行为1个整数n(1<=n<=100000),表示序列的长度。

第二行包含n个整数,表示栈的压入顺序。

第三行包含n个整数,表示栈的弹出顺序。

输出:

对应每个测试案例,如果第二个序列是第一个序列的弹出序列输出Yes,否则输出No。

样例输入:

5
1 2 3 4 5
4 5 3 2 1
5
1 2 3 4 5
4 3 5 1 2

样例输出:

Yes
No

解题思路:

重新按照第一组数据入栈,每次入栈都检查一下,是否跟出栈的内容相同,如果相同,则出栈。

  最后,如果这个栈内不存在元素,则证明第二个序列为出栈序列。

代码:

#include <stdio.h>
#include <stdlib.h>
int arr[100005] = {0};
int test[100005] = {0};
int testStack(int n);
int main(int argc, char const *argv[])
{
    int n,i;
    while(scanf("%d",&n)!=EOF && n>=1 && n<=100000){
        for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
        }
        for(i=0;i<n;i++){
            scanf("%d",&test[i]);
        }
        if(testStack(n))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}
int testStack(int n){
    int temp[100005]={0};
    int top=0;
    int j=0;
    int i;
    for(i=0;i<n;i++){
        temp[top++] = arr[i];
        while(top>0 && temp[top-1] == test[j]){
            j++;
            top--;
        }
    }
    if(top)
        return 0;
    else
        return 1;
}
/**************************************************************
    Problem: 1366
    User: xhalo
    Language: C
    Result: Accepted
    Time:230 ms
    Memory:2012 kb
****************************************************************/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 不相交集类应用:迷宫生成

    1 #include <iostream> 2 #include <vector> 3 #include <cstdlib> 4 #includ...

    用户1154259
  • 不相交集类

    等价关系:自反性,对称性,传递性 class DisjSets//不相交集的类架构 { public: explicit DisjSets(int nu...

    用户1154259
  • 图m着色问题

    1 问题描述:   给定无向图,m种不同的颜色。使每一种着色法使G中每条边的2个顶点不同颜色,若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,...

    用户1154259
  • 7-2 神奇字符串 (30 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • BFS+DFS终结游戏题目

    题目描述:在一个 2 x 3 的板上(board)有 5 块砖瓦,用数字 1~5 来表示, 以及一块空缺用 0 来表示.

    公众号guangcity
  • java 随机生成35~95的数

    花狗Fdog
  • 基础知识 | 每日一练(47)

    士人有百折不回之真心,才有万变不穷之妙用。立业建功,事事要从实地着脚,若少慕声闻,便成伪果;讲道修德,念念要从虚处立基,若稍计功效,便落尘情。 ...

    C语言入门到精通
  • BZOJ1050: [HAOI2006]旅行comf(并查集 最小生成树)

    给你一个无向图,N(N<=500)个顶点, M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T,求

    attack
  • 1076: 输入入门(1)

    描述:计算A+B 输入:输入数据有多组。每组一行,为整数A, B。以EOF做结束。 输出:输出A+B的值。 样例输入: 1 23 4 样例输出: 3...

    bboysoul
  • LeetCode133|合并区间

    先对数组进行排序,然后进行逻辑判断,这里使用了集合作为一个临时存储空间,比较相邻区间的内容,如前一个区间右端点的值和下一个区间左端点的值做比较,符合合并的时候进...

    后端Coder

扫码关注云+社区

领取腾讯云代金券