剑指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 条评论
登录 后参与评论

相关文章

来自专栏java小白

LinkedHashMap的accessOrder

2069
来自专栏流媒体

C++ string

862
来自专栏python读书笔记

《算法图解》NOTE 2 数组、链表及选择排序1.数组2.链表3.选择排序法

1413
来自专栏HTML5学堂

PHP入门-常量基本规则

PHP入门-常量基本规则 HTML5学堂:本文是PHP的入门用文章,主要介绍PHP的常量的基本规则以及定义和获取方法。 前几天把PHP的基本语法以及变量的基本规...

38515
来自专栏黑泽君的专栏

JDK5中Lock锁的使用

(1)JDK5中Lock锁的使用   虽然我们可以理解同步代码块和同步方法的锁对象问题,但是我们并没有直接看到在哪里加上了锁,在哪里释放了锁,为了更清晰的...

1131
来自专栏北京马哥教育

17个案例带你3分钟搞定Linux正则表达式

正则表达式是一种字符模式,用于在查找过程中匹配制定的字符。 元字符通常在Linux中分为两类: Shell元字符,由Linux Shell进行解析; 正则表达式...

3564
来自专栏http://www.cnblogs.com

python 反射

通过字符串映射或修改程序运行时的状态、属性、方法, 有以下4个方法: hasattr(obj,name_str) 判断一个对象obj里是否有对应的name...

3869
来自专栏nummy

python双端队列deque

由于deque是一种序列容器,因此同样支持list的一些操作,如用getitem()检查内容,确定长度,以及通过匹配标识从序列中间删除元素。

892
来自专栏程序员互动联盟

【专业技术第十二讲】void的妙用

存在问题: 遇到微信好友询问关于void *的用法,这里做一个总结性的回复。 解决方案: void的字面意思是空类型,void *的意思是空类型指针,void ...

36910
来自专栏GreenLeaves

C# this关键字(给底层类库扩展成员方法)

本文参考自唔愛吃蘋果的C#原始类型扩展方法—this参数修饰符,并在其基础上做了一些细节上的解释 1、this作为参数关键字的作用 使用this关键字,可以向t...

2397

扫码关注云+社区

领取腾讯云代金券