剣指Offer--022-スタックの圧入、イジェクトシーケンス

リンク
牛客OJ:スタックの圧入、ポップアップシーケンス
9度OJ:http://ac.jobdu.com/problem.php?pid=1366
GitHubコード:022-スタックの圧入ポップアップシーケンス
CSDN題解:剣指Offer–022桟の圧入、弾き出すシーケンス
牛客OJ
9度OJ
CSDN問題解
GitHubコード
スタックの圧入、ポップアップシーケンス
1366-スタックの押し込み、ポップアップシーケンス
剣指Offer–022スタックの圧入、ポップアップシーケンス
022-スタックの圧入ポップアップシーケンス
に言及
タイトルの説明
2つの整数シーケンスを入力します.最初のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序であるかどうかを判断してください.
スタックに押し込まれたすべての数字が等しくないと仮定します.
例えばシーケンス1,2,3,4,5はあるスタックの圧入順序であり、
シーケンス4,5,3,2,1は、このスタックシーケンスに対応するポップアップシーケンスであり、
しかし、4,3,5,1,2がスタックシーケンスのポップアップシーケンスであることは不可能である.
ぶんせき
補助スタックシミュレーション入スタック出スタックプロセス
考え方:
補助スタックを開き、スタックに入る戦過程をシミュレートする(paがスタックに入るシーケンスであり、pbが出戦シーケンスであると仮定する)
paの要素は補助スタックに順次圧入される
新しく押し込まれた要素はポップアップシーケンスのスタックの底と同じで、補助スタックはポップアップし、同時にpbは上へ移動します.
同じではありませんpaの要素は補助に入り続けます

次のポップアップされた数字がスタックトップの数字であれば、直接ポップアップします.

次のポップアップされた数字がスタックの上部にない場合、スタックのシーケンスにまだスタックに入っていない数字を、次のポップアップが必要な数字がスタックの上部に押し込まれるまで補助スタックに押し込む.

すべての数字がスタックに押し込まれても次のポップアップされた数字が見つからない場合、このシーケンスがポップアップされたシーケンスを滴下することはできないことを示します.

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

//     
#define __tmain main

#ifdef __tmain

#define debug cout

#else

#define debug 0 && cout

#endif // __tmain


class Solution
{
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV)
    {

        if(pushV.size( ) == 0 || popV.size( ) == 0)
        {
            return false;
        }
        stack<int> s;
        int push, pop;

        s.push(pushV[0]);
        debug <<"push" <<pushV[0] <<endl;

        for(push = 0, pop = 0;
            push < pushV.size() && pop < popV.size( );)
        {
            if(s.empty( ) != true && s.top( ) == popV[pop])        //                  
            {
                debug <<"pop"<<popV[pop] <<endl;
                //        
                s.pop( );
                pop++;
            }
            else
            {

                //        
                s.push(pushV[++push]);
                debug <<"push" <<pushV[push] <<endl;

            }
        }
        if(s.empty( ) == true)
        {
            return true;
        }
        else
        {
            return false;
        }




    }
};

int __tmain( )
{
    int nPush[5] = {1,2,3,4,5};
    int nPop1[5] = {4,5,3,2,1};
    int nPop2[5] = {4,3,5,1,2};
    int nPop3[5] = {5,4,3,2,1};
    int nPop4[5] = {4,5,2,3,1};

    Solution solu;

    cout <<solu.IsPopOrder(vector<int>(nPush, nPush + 5), vector<int>(nPop1, nPop1 + 5)) << endl;
    cout <<solu.IsPopOrder(vector<int>(nPush, nPush + 5), vector<int>(nPop2, nPop2 + 5)) << endl;
    cout <<solu.IsPopOrder(vector<int>(nPush, nPush + 5), vector<int>(nPop3, nPop3 + 5)) << endl;
    cout <<solu.IsPopOrder(vector<int>(nPush, nPush + 5), vector<int>(nPop4, nPop4 + 5)) << endl;

    return 0;
}

ここでは補助スタックを使ってスタックに入る過程をシミュレートしました.構想は簡単ではっきりしていますが、最適化できる場所はありませんか.
PushVインスタックシーケンスを補助スタックとして使用
実際には、現在のスタックの動作はpushVシーケンスを超えないことは間違いありません.そのため、PushVスタックシーケンスをシミュレーションスタックとして直接使用し、topでスタックアウトスタックの動作を維持することができます.
この方法は時間複雑度O(n),空間複雑度O(1)であるが,入力パラメータPushVの値を修正する必要がある.

class Solution
{
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV)
    {
        if(pushV.size( ) == 0 || popV.size( ) == 0)
        {
            return false;
        }
        int top = -1, push = 0, pop = 0;

        ++top;
        debug <<"push" <<pushV[top] <<endl;


        while(push < pushV.size() && pop < popV.size( ))
        {
            if(top != -1 && pushV[top] == popV[pop])        //                  
            {
                debug <<"pop"<<popV[pop] <<endl;
                //        
                top--;
                pop++;
            }
            else
            {

                //        
                pushV[++top] = pushV[++push];
                debug <<"push" <<pushV[push] <<endl;

            }
        }
        debug <<top <<push <<pop <<endl;
        return (top == -1);
    }
};

または直接使用

class Solution
{
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV)
    {
        if(pushV.empty( ) || popV.empty( ) || pushV.size( )!= popV.size( ))
        {
            return false;
        }

        for(int i = 0;i < pushV.size();)
        {
            if(pushV[i] == popV[0])
            {
                pushV.erase(pushV.begin( ) + i);
                popV.erase(popV.begin( ));
                i--;                                //     
            }
            else
            {
                i++;                                //     
            }
        }

        return pushV.empty( );
    }

};

法則を発見する.
これは見た人のやり方です
異なる考え方:

私はまずpopシーケンスの最初の(例えばpop【3,2,4,5,1】)を取り出して、pushシーケンスの中でこの位置を見つけて、push【1,2,3,4,5】,

この時私たちは3の位置を見つけました.次のpopの数字(この時の数字は2)は必然的にpushの中の3の前の数字、あるいは後ろの数字です.そうでなければFalseに戻って最後までループし,長さが等しいと判断するのがポップアップシーケンスである.そうでなければFalse.

に戻る

# -*- coding:utf-8-*-

classSolution:

    def IsPopOrder(self, pushV, popV):

        # write code here

        iflen(pushV) != len(popV):

            returnFalse

        elif len(pushV) ==0:

            returnFalse

        x = popV[0]

        ifx not in pushV:

            returnFalse

        fori in range(len(popV)):

            position = pushV.index(popV[i])

            iflen(pushV) ==1:

                ifpushV[0] == popV[i]:

                    returnTrue

            try:

                ifpopV[i+1] == pushV[position-1]:

                    pushV.remove(pushV[position])

                elif popV[i+1] in pushV[position:]:

                    pushV.remove(pushV[position])

                else:

                    returnFalse

            except IndexError:

                returnFalse

        else:

            returnTrue

リファレンス
スタックの圧入、ポップアップシーケンス
面接問題20:スタックの押し込み、ポップアップシーケンス
牛客網討論区-[プログラミング問題]スタックの圧入、ポップアップシーケンス
スタックの押し込みとポップアップシーケンス