当前位置：首页 > article >正文

机试准备第12天

article 2025/3/10 10:52:26

首先学习队列，队列有先进先出的特性。广度优先遍历需要基于队列实现，C++中的stl引入了队列的实现方式。队列支持push()，进入队尾，pop()出队，队头出队，front()获取队首元素，back()获取队尾元素，empty()判断队列是否为空。

第一题是约瑟夫环问题。

#include <stdio.h>
#include <queue>
using namespace std;
int main()
{
    queue<int> myqueue;
    int n,p,m;
    while(scanf("%d%d%d", &n,&p,&m)!=EOF){
        if(n ==0&&p==0&&m==0) break;
        //生成第一轮报数的队列
        //p, p+1,p+2,...,n,1,2,....
        int no = p;//孩子编号
        for(int i = 0; i < n;i++){
            myqueue.push(no);
            no++;
            if(no>n) no=1;
        }
        
        //开始报数
        int say = 1;
        while(1){
            int cur = myqueue.front();
            myqueue.pop();
            if(say == m){
                say = 1;
                if(myqueue.empty()){
                    printf("%d\n", cur);
                    break;
                }
                else{
                     printf("%d,", cur);
                }
            }
            else {
                say++;
                myqueue.push(cur);
            }
        }
    }

    return 0;
}

第二题是排队打饭，分情况讨论即可，主要注意time是long long类型，使用int这题过不了。

#include <stdio.h>
#include <queue>
using namespace std;
struct Student{
    int a;//到达时刻
    int t;//打饭耗时
    int b;//最大等待时间
};
int main(){
    queue<Student> que;
    int n;
    scanf("%d", &n);
    for(int i = 0; i<n;i++){
        int ai,ti,bi;
        scanf("%d%d%d", &ai, &ti,&bi);
        Student s1;
        s1.a = ai;
        s1.b = bi;
        s1.t = ti;
        que.push(s1);//读入学生序列
    }
    long long time = 1;//记录当前时刻
    while(!que.empty()){
        Student stu = que.front();
        if(time>(stu.a+stu.b)){
            printf("-1 ");
            que.pop();
        }
        else if(time>=stu.a&&time<=(stu.a+stu.b)){
            printf("%d ", time);
            time += stu.t;
            que.pop();
        }
        else if(time<stu.a){
            time = stu.a;
            printf("%lld ", time);
            time += stu.t;
            que.pop();
        }
    }
}

下面学习栈，后进先出。深度优先遍历、表达式解析、递归会使用栈。stack支持push()入站，pop()出栈，top()获取栈顶元素，栈只支持获取栈顶元素，empty()获取栈是否为空。

第三题是编排字符串。栈的简单应用。

#include <stdio.h>
#include <stack>
#include <string>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    stack <string> st1;
    for(int i = 0; i<n;i++){
        char mid[20];
        scanf("%s", mid);
        string str = mid;
        st1.push(str);
        stack<string> mystack;
        mystack = st1;
        int num = 1;
        while(!mystack.empty()){
            if(num>4) break;
            string str1 = mystack.top();
            printf("%d=%s ", num, str1.c_str());
            num++;
            mystack.pop();
        }
        printf("\n");
    }
    
}

第四题是括号匹配，经典题目。

#include <stdio.h>
#include <stack>
#include <string>
using namespace std;
int main()
{
    char arr[20000];
    scanf("%s", arr);
    string str = arr;
    stack<char> mystack;
    mystack.push(str[0]);
    for(int i = 1;i < str.size();i++){
        if(str[i] == '<'||str[i] == '('||str[i] == '{'||str[i] == '['){
            mystack.push(str[i]);
        }
        else if(str[i]=='>'){
            if(mystack.empty()) {
                printf("no");
                return 0;
            }
                char res = mystack.top();
                if(res == '<') mystack.pop();
                else {
                    printf("no");
                    return 0;
            }
        }
        else if(str[i]==')'){
            if(mystack.empty()) {
                printf("no");
                return 0;
            }
            char res = mystack.top();
            if(res == '(') mystack.pop();
            else {
                printf("no");
                return 0;
            }
        }
        else if(str[i]=='}'){
            if(mystack.empty()) {
                printf("no");
                return 0;
            }
            char res = mystack.top();
            if(res == '{') mystack.pop();
            else {
                printf("no");
                return 0;
            }
        }
        else if(str[i]==']'){
            if(mystack.empty()) {
                printf("no");
                return 0;
            }
            char res = mystack.top();
            if(res == '[') mystack.pop();
            else {
                printf("no");
                return 0;
            }
        }
    }
    if(mystack.empty()==true) printf("yes");
    else printf("no");

    return 0;
}

第五题是堆栈的使用，简单模拟。

#include <stdio.h>
#include <string>
#include <stack>
using namespace std;
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        stack <int> mystack;
        for (int i = 0; i < n; i++) {
            char op[2];
            scanf("%s", op);
            string op2=op;
            if (op2 == "A") {
                if (mystack.empty()) printf("E\n");
                else printf("%d\n", mystack.top());
            } else if (op2 == "O") {
                if (!mystack.empty()) mystack.pop();
            } else if (op2 == "P") {
                int num;
                scanf("%d", &num);
                mystack.push(num);
            }
        }
    }
    return 0;
}

第六题是计算表达式，写了半天代码逻辑不对，气完了。建立运算符栈与运算数栈。从左向右扫描表达式，遇到操作数就加入操作数栈，扫描到运算符，若运算符栈为空，则直接压入运算符栈，若运算符栈不为空但当前运算符优先级大于栈顶运算符，也执行压栈操作。若运算符栈不为空但当前运算符优先级低于栈顶运算符，则弹出栈内的运算符，同时弹出操作数，直到当前运算符优先级再次大于栈顶运算符，压入栈中。

#include <stdio.h>
#include <string>
#include <stack>
#include <map>
using namespace std;
int main() {
    char str[1000] = {0};
    map<char, int> prio = {{'\0', 0}, {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    while (scanf("%s", str) != EOF) {
        string numstr = "";
        stack <char> opstack;
        stack <double> numstack;
        for (int i = 0;; i++) {
            if (str[i] >= '0' && str[i] <= '9') {
                numstr.push_back(str[i]);
            } else {
                double num = stod(numstr);
                numstr = "";//数值提取
                numstack.push(num);

                //什么时候弹栈？栈非空&&新的op的优先级不高于栈顶的优先级
                //循环弹栈和计算
                while (!opstack.empty() && prio[str[i]] <= prio[opstack.top()]) {
                    double right = numstack.top();
                    numstack.pop();
                    double left = numstack.top();
                    numstack.pop();
                    char curop = opstack.top();
                    opstack.pop();

                    if (curop == '+') numstack.push(left + right);
                    else if (curop == '-') numstack.push(left - right);
                    else if (curop == '*') numstack.push(left * right);
                    else if (curop == '/') numstack.push(left / right);
                }
                //栈为空或者新运算符的优先级大于栈顶运算符
                if (str[i] == '\0') {
                    printf("%d\n", (int)numstack.top());
                    break;
                } else opstack.push(str[i]);
            }


        }
    }

    return 0;
}

第七题是模拟出入栈。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        stack<char> stk;
        int j = 0; //j用来扫描出栈序列s的
        for (char i = 'a'; i <= 'z'; ++ i) {
            stk.push(i); //每次按顺序入栈一个
            while (stk.size() && stk.top() == s[j]) {
                j++; //出栈序列向后走匹配下一个
                stk.pop(); //出栈
            }
        }
        if (stk.empty()) cout << "yes\n"; //栈空了，就是匹配的
        else cout << "no\n";
    }
    return 0;
}

查看全文

http://www.kler.cn/a/576766.html