首页 > 剑指offer > 剑指offer(13)-栈的压入、弹出序列 九度1366
2014
01-02

剑指offer(13)-栈的压入、弹出序列 九度1366

题目来自剑指offer系列 九度 1366:http://ac.jobdu.com/problem.php?pid=1367

题目描述:
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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

 


看到这个题太熟悉了,数据结构考试中会经常遇到。使用栈模拟一编即可。这里为了效率直接用数组模拟栈了。

//============================================================================
// Name        : 栈的序列判断.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <stdio.h>
using namespace std;
const int M=100001;
int n,stack[M],arr1[M];
char buf[M*10];
int main() {
    while(~scanf("%d", &n)){
        int top=0; //栈的顶端位置
        int cnt=0; //已入栈的个数
        int i, k, tmp;
        for(i=0; i<n; i++)
            scanf("%d", &arr1[i]);
        for(k=0; k<n; k++){
            scanf("%d", &tmp);
            //如果栈为空,或栈的顶端元素 不等于 要出栈的, 就一直入栈
            while( top==0 || tmp != stack[top-1] ){
                stack[top++] = arr1[cnt++];
                if(cnt>=n) break;
            }
            top--; //出栈
            if(cnt>=n) break;
        }
        k++;
        //所有元素已入栈,则出栈顺序唯一
        bool flag = true;
        for(; k<n; k++){
            scanf("%d", &tmp);
            if( tmp != stack[--top]){
                flag = false; break;
            }
        }
        gets(buf);//读取剩下多余的
        printf("%s\n", flag ? "Yes":"No");
    }
    return 0;
}
/**************************************************************
    Problem: 1366
    User: 从此醉
    Language: C++
    Result: Accepted
    Time:140 ms
    Memory:3276 kb
****************************************************************/

附上用Java超时的版本:

import java.util.Scanner;
import java.util.Stack;

public class Main{
    static int n,arr1[] = new int[100001], arr2[] = new int[100001];
    public static void main(String[] args) {
        Scanner scan =new Scanner(System.in);
        while(scan.hasNextInt()){
            n = scan.nextInt();
            Stack<Integer> stack = new Stack<Integer>();
            for(int i=0; i<n; i++)arr1[i] = scan.nextInt();
            for( int i=0; i<n; i++)
                arr2[i] = scan.nextInt();
            int k = 0 ,i=0;
            for( i=0; i<n; i++){
                while (stack.size() == 0 || arr2[i] != stack.peek()){
                    stack.add(arr1[k++]);
                    if(k >= n) break;
                }
                int p = stack.pop();
                //System.out.println(p);
                if(k >= n) break;
            }
            i++;
            //System.out.println(i + "  " + k);
            boolean flag = true;
            for(; i<n; i++){
                //System.out.println( arr2[i] + "  :  "  + stack.peek());
                if( arr2[i] != stack.pop()) {
                    flag = false;
                    break;}
            }
            System.out.println(flag ? "Yes":"No");

        }
    }
}
/**************************************************************
    Problem: 1366
    User: 从此醉
    Language: Java
    Result: Time Limit Exceed
****************************************************************/

 


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }