1、简单模拟队列排队
#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;queue<int>q;string str;while(true){cin>>str;if(str=="#")break;if(str=="In"){int t;cin>>t;if(q.size()<n){q.push(t);cout<<t<<" joined. Total:"<<q.size()<<endl;}else{cout<<t<<" rejected."<<endl;}}if(str=="Calling"){if(q.empty()){cout<<"No one!"<<endl;}else{int t=q.front();q.pop();cout<<t<<" called. Total:"<<q.size()<<endl;}}}return 0;
}
2、表达式转换
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;// 判断字符是否为运算符
bool isOperator(char c) {return c == '+' || c == '-' || c == '*' || c == '/';
}// 获取运算符优先级
int precedence(char op) {if (op == '+' || op == '-')return 1;if (op == '*' || op == '/')return 2;return 0;
}// 处理负数情况，判断当前字符是否为负号而非减号
bool isNegativeSign(const string& expr, int pos) {if (expr[pos] != '-') return false;if (pos == 0) return true;if (expr[pos-1] == '(') return true;return isOperator(expr[pos-1]);
}int main() {string infix;cin >> infix;stack<char> operators;string postfix;for (int i = 0; i < infix.length(); i++) {char c = infix[i];// 处理数字（包括小数和负数）if (isdigit(c) || c == '.') {if (!postfix.empty()) postfix += ' ';postfix += c;// 继续读取完整数字while (i+1 < infix.length() && (isdigit(infix[i+1]) || infix[i+1] == '.')) {postfix += infix[++i];}}// 处理负数符号else if (isNegativeSign(infix, i)) {if (!postfix.empty()) postfix += ' ';postfix += c;// 继续读取负数的数值部分if (i+1 < infix.length() && (isdigit(infix[i+1]) || infix[i+1] == '.')) {postfix += infix[++i];while (i+1 < infix.length() && (isdigit(infix[i+1]) || infix[i+1] == '.')) {postfix += infix[++i];}}// 特殊情况：负号后直接跟括号，表示负数乘以括号内表达式else if (i+1 < infix.length() && infix[i+1] == '(') {postfix += ' ';postfix += '0'; // 补充0，将负号视为0-的操作operators.push('-');}}// 处理左括号else if (c == '(') {operators.push(c);}// 处理右括号else if (c == ')') {while (!operators.empty() && operators.top() != '(') {postfix += ' ';postfix += operators.top();operators.pop();}operators.pop(); // 弹出左括号}// 处理运算符else if (isOperator(c)) {while (!operators.empty() && precedence(operators.top()) >= precedence(c)) {postfix += ' ';postfix += operators.top();operators.pop();}operators.push(c);}}// 弹出剩余运算符while (!operators.empty()) {postfix += ' ';postfix += operators.top();operators.pop();}cout << postfix << endl;return 0;
}
3、出入栈
#include<bits/stdc++.h>
using namespace std;bool bmg1(string str){stack<char>s;int t=0;for(int i=0;i<str.length();i++){char c=str[i];while(s.empty()||s.top()!=c){if(t>=26)return false;s.push('a'+t);t++;}s.pop();}return true;
}
int main(){int n;cin>>n;for(int i=0;i<n;i++){string str;cin>>str;if(bmg1(str)){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}}return 0;
}
4、公路村村通
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;struct node{int start;int end;int weight;
} a[N];int parent[N]; //使用int数组作为并查集
int n, m;//移除多余的参数
int find(int x){if(parent[x] != x){parent[x] = find(parent[x]);}return parent[x];
}// 新增：比较函数，用于边的排序
bool cmp(const node& a, const node& b) {return a.weight < b.weight;
}int main(){cin >> n >> m;for(int i = 0; i < m; i++){cin >> a[i].start >> a[i].end >> a[i].weight;}//使用数组范围和比较函数sort(a, a + m, cmp);for(int i = 1; i <= n; i++){parent[i] = i;}int cnt1 = 0; // 总权重int cnt2 = 0; // 边的数量for(int i = 0; i < m; i++){int r1 = find(a[i].start);int r2 = find(a[i].end);if(r1 != r2){parent[r2] = r1;cnt1 += a[i].weight;cnt2++;if(cnt2 == n - 1) break;}}if(cnt2 == n - 1){cout << cnt1 << endl;}else{cout << -1 << endl;}return 0;
}
5、繁忙的都市
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct node{int start;int end;int weight;
}a[N];
int n,m;
int b[N];bool cmp(node a,node b){return a.weight<b.weight;
} int find(int x){while(b[x]!=x){b[x]=b[b[x]];x=b[x];}return x;
}
void unite(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy){b[fx]=fy;}
}
int main(){cin>>n>>m;for(int i=0;i<m;i++){int u,v,c;cin>>u>>v>>c;a[i]={u,v,c};}sort(a,a+m,cmp);for(int i=1;i<=n;i++){b[i]=i;}int cnt=0,max_c=0;for(int i=0;i<m;i++){int u=a[i].start;int v=a[i].end;if(find(u)!=find(v)){unite(u,v);cnt++;max_c=a[i].weight;if(cnt==n-1)break;}}cout<<cnt<<" "<<max_c<<endl;return 0;
}
6、局域网
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
struct node{int u;int v;int w;
}a[N];
int n,k;
int b[N];
bool cmp(node a,node b){return a.w<b.w;
}
int find(int x){while(b[x]!=x){b[x]=b[b[x]];x=b[x];}return x;
}
int main(){cin>>n>>k;int sum1=0;for(int i=0;i<k;i++){int u,v,w;cin>>u>>v>>w;a[i]={u,v,w};sum1+=w;}sort(a,a+k,cmp);for(int i=1;i<=n;i++){b[i]=i;}int sum2=0;int cnt=0;for(int i=0;i<k;i++){int u=a[i].u;int v=a[i].v;int w=a[i].w;int root_u=find(u);int root_v=find(v);if(root_u!=root_v){b[root_u]=root_v;sum2+=w;cnt++;if(cnt==n-1)break;}}cout<<sum1-sum2<<endl;return 0;
}
7、列出叶子结点
#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct node{int left;int right;
}a[N];
int n;// 将字符串转换为整数的函数（修改为传统for循环）
int strToInt(string s){int result=0;for(int i=0; i<s.length(); i++){result = result * 10 + (s[i] - '0');}return result;
}int main(){cin>>n;vector<int> boots(n+1,1); // 标记每个节点是否为根节点for(int i=0;i<n;i++){string l,r; // 输入应为字符串类型cin>>l>>r;if(l=="-"){a[i].left=-1;}else{a[i].left=strToInt(l);boots[strToInt(l)]=0; // 修正为方括号访问}if(r=="-"){a[i].right=-1;}else{a[i].right=strToInt(r);boots[strToInt(r)]=0;}}int root=0;for(int i=0;i<n;i++){if(boots[i]){root=i;break;}}vector<int> st; // 存储叶节点queue<int> q;if(root!=-1){ // 根节点不可能为-1，因为n>=1且必定存在根节点q.push(root);while(!q.empty()){int t=q.front();q.pop();if(a[t].left==-1 && a[t].right==-1){st.push_back(t);}if(a[t].left!=-1){q.push(a[t].left);}if(a[t].right!=-1){q.push(a[t].right);}}}for(int i=0;i<st.size();i++){if(i>0) cout<<" ";cout<<st[i];}cout<<endl;return 0;
}
8、最短路径迪杰斯特拉算法
#include<bits/stdc++.h>
using namespace std;
const int N=105;
const int INF=1e9;
int vis[N];
int dis[N];
int a[N][N];
int vexnum;
void dij(int u,int v){for(int i=0;i<vexnum;i++){vis[i]=0;dis[i]=a[u][i];}vis[u]=1;for(int i=0;i<vexnum-1;i++){int minn=INF;int t;for(int j=0;j<vexnum;j++){if(vis[j]==0&&dis[j]<minn){minn=dis[j];t=j;}}vis[t]=1;for(int j=0;j<vexnum;j++){if(vis[j]==0&&dis[t]+a[t][j]<dis[j]){dis[j]=dis[t]+a[t][j];}}}cout<<dis[v];
}
int main(){int n,m;cin>>n>>m;vexnum=n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j){a[i][j]=0;}else{a[i][j]=INF;}}}for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;a[u][v]=w;}int p;cin>>p;dij(0,p);return 0;
}
