Pop Sequence (栈)

Pop Sequence (25)

我淦!!!什么叫做菜,这题调3个小时

题目描述(翻译)

M(栈的最大容量),N(序列元素都为1~N,序列长度为N),K(序列出栈情况个数)。给定K种出栈顺序,判断这种出栈顺序是否正确,是则输出“YES”,否则输出“NO”(如果描述得不太清楚可以自己搜搜翻译)

思路

以出栈序列 3 2 1 5 4 为例

①1!=3,栈:1
②2!=3,栈:1 2
③3==3,栈:1 2 ---> 2==2,栈;1 ---> 1==1,栈:
④4!=5,栈:4
⑤5==5,栈: ---> 4==4,栈: 

思路很好理解,但是代码我调了半天,为什么呢?我去ta的STL STL真香,最开始用的STL,但是调了大概两个多小时没搞出来,后来我旁边的大哥给我看了他的手写栈过了,我又开始调STL的,发现一个很重要的问题

关于&&的问题,我们平常只是理解了一点,就是只知道在两边的情况同时满足的时候,才是TURE,但其实这有一个先后顺序。在前面的情况为TRUE的情况才会去判断后面的情况,不然后面的情况不会管。所以我在最开始写错了,我后判断的是栈为空的情况,所以一直出错,换到前面之后就对了,所以在用queue和stack的时候,判断最好都先判断为空,算是经验吧

//STL栈 
#include<bits/stdc++.h>
using namespace std;
int main() {
    int m,n,k;
    int b[1000];
    cin>>m>>n>>k;
    for(int o=1;o<=k;o++){
        stack<int> a;
        for(int i=1; i<=n; i++) cin>>b[i];
        int now=1;
        for(int i=1; i<=n; i++) {
            a.push(i);
            if(a.size()>m) break;
            while((!a.empty())&&(a.top()==b[now])) {
                a.pop();
                now++;
            }
        }
        if(a.empty()) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
//手写栈 
#include <bits/stdc++.h>
using namespace std;
int n,m,k,a[1001],b[1001];
stack<int> num;

int main() {
    scanf("%d%d%d",&m,&n,&k);
    for(register int i=1;i<=k;i++) {
        int start=1;
        bool p=true;
        for(register int j=1;j<=n;j++) {
            scanf("%d",&a[j]);
            num.push(j);
            if(num.size()>m) break;
            else {
                for(register int z=start;z<=j;z++){
                    if(num.empty()) break;
                    if(num.top()==a[z]){
                        start++;
                        num.pop();
                    }else break;
                }
            }
        }
        if(!num.empty()) puts("NO");
        else puts("YES");
        while(!num.empty()) num.pop();
    }
    return 0;
}

原文链接: https://www.cnblogs.com/Poetic-Rain/p/13067842.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬

    Pop Sequence (栈)

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/353854

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月2日 上午8:17
下一篇 2023年3月2日 上午8:17

相关推荐