HJ77火车进站

一.题目描述

给出一组序列,请求输出其所有的出栈的合法序列。

alt

二.算法二(暴力)

开始看到题目感觉很熟悉却又很懵,该怎么去判断出栈顺序呢?我们不妨想到无论怎么样,出栈的顺序一定被包含于所给数列的全排列中,所以问题就转换为了怎么去判断一个序列是不是合法的出栈序列?

alt

对于如何判断序列是不是合法的出栈序列我们有了一定认识,下面给出完整的代码和注释:

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int st[N],a[N];
int n;
bool check(){
    stack<int>s;
    int cnt=1;
    for(int i=1;i<=n;i++){
        s.push(a[i]);
        //栈顶元素和出栈元素相等 下标后移一位
        while(s.size()&&st[cnt]==s.top()){
            s.pop();
            cnt++;
        }
    }
    if(s.size()){
        return false;
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i]=a[i];
    }
    //需要对a进行全排列,先对其进行排序
    sort(st+1,st+1+n);
    do{
        if(check()){
            for(int i=1;i<=n;i++){
                cout<<st[i]<<" ";
            }
            cout<<endl;
        }
    } while(next_permutation(st+1,st+1+n));//利用next_permutation实现全排列
    return 0;
}

时间复杂度:O(nn!)O(n∗n!),全排列的复杂度为O(n!)O(n!),所以时间复杂度是O(nn!)O(n∗n!)

空间复杂度:O(n)O(n),需要空间来存储全排练的数列。

三.算法二(dfs搜索)

前面我们是依赖于next_permutation函数来实现全排练,我们也可以用dfs来构建全排列,每次都有着两个分支,要么实现出栈,要么实现入栈,每次操作完都需要回溯才能够实现检查全排列,如果某一种输出长度到了n说明这种序列结束了,可以输出。但是由于遍历过程中存在重复的现象,我们可以使用set去重,然后输出,下面是完整代码:

#include<bits/stdc++.h>
using namespace std;
int n;
//now表示当前序列中的顺序
//num表示入栈顺序
//st表示栈的情况
//mp用来去重和储存所有的出栈序列
//idex用来表示入栈序列的下标
//n表示排列需要到达的数目
void dfs(vector<int>& num,stack<int> st,vector<int> now,set<vector<int>> &mp,int idex,int &n){
    if(now.size() == n){
        mp.insert(now);
        return;
    }
    for(int i=1;i<=2;i++){
        //对于栈的两种选择
        if(i==1){//出栈
            if(!st.empty()){
                int ans = st.top();
                st.pop();
                now.push_back(ans);
                dfs(num,st,now,mp,idex,n);
                //回溯
                st.push(ans);
                now.pop_back();
            }

        }else if(i==2){//入栈
            if(idex<n){
                int ans=num[idex];
                st.push(ans);
                idex++;
                dfs(num,st,now,mp,idex,n);
                idex--;
                st.pop();
            }

        }
    }
}
int main(){
        cin>>n;
        vector<int> num(n);
        set<vector<int> > mp;
        stack<int> st;
        vector<int> now;
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        st.push(num[0]);
        dfs(num,st,now,mp,1,n);
    //输出set去重后的排序
        for(auto it=mp.begin();it!=mp.end();it++){
            for(int i=0;i<n;i++){
                cout << (*it)[i] << " ";
            }
            cout<<endl;
        }
    return 0;
}

时间复杂度:O(n!log2(n!))O(n!log2(n!)),dfs遍历整个全排列,最坏情况下全排列都要输出,那么时间复杂度就达到了O(n!log2(n!))O(n!log2(n!))

空间复杂度:O(nn!)O(n∗n!),set集合存储序列