心双2024数据结构1016-1020题解-xiwwwix's blog

1016. 铁路调度

我的做法是维护两个栈，一个trains自底向上放入n到1，一个st先置为空
遍历出站序列，假设遍历到的车号是train，核心就是比较train和st顶部的大小

如果trains不为空并且st为空或顶部小于train，则将trains中的火车逐一移动到st中
如果st不为空并且train和st顶部相同，则弹出st顶部
其他情况，说明序列不合法，直接跳出循环

判断单个序列的时间复杂度为O(N)，最多只需遍历一次trains中的元素

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

int main() {
	int k;
	cin >> k;
	while (k--) {
		bool flag = true;
		int n;
		cin >> n;
		string seq;
		cin >> seq;
		stack<int> st,trains;
		
		for (int i = n;i >= 1;i--) {
			trains.push(i);
		}
		
		for (int i = 0;i < seq.size();i++) {
			int train = seq[i] - '0';
			while (!trains.empty() && (st.empty() || st.top() < train)) {
				st.push(trains.top());
				trains.pop();
			}
			
			if (!st.empty() && train == st.top()) {
				st.pop();
			} else {
				flag = false;
				break;
			}
		}
		cout << (flag?"yes":"no") << endl;
	}
	return 0;
}

1017. 波兰表达式

可以这么递归地理解：只有当一个符号后面紧跟着两个数字时，这两个数字才是直接和这个符号进行计算的
举例- 5 * 6 7中的-号后面跟着一个数字和一个乘号，说明-号不直接执行计算，我们先往后看，发现*号后面紧跟着两个数字，所以计算6 * 7，并且将结果42放回式子，得到- 5 42，此时-号后面直接跟着两个数字，可以进行计算，5 - 42得到结果-37
代码实现的思路是，维护数字栈和符号栈，先读入一行，然后从右往左进行处理：

如果当前是数字，直接压入数字栈（使用了一个比较幽默的函数用于判断当前是否为数字，详见代码）
如果是符号，从数字栈中取出两个数，执行这个符号的运算，然后把结果压入数字栈，需要注意如果正着看，应该是左边的数字（符号）右边的数字，但是因为我们现在是在从右往左遍历，所以要调换顺序

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

bool isNum(string x) {
	return (isdigit(x[0]) || (x[0] == '-' && x.length() > 1));
}

double calculate(double num1,double num2,char t) {
	double ans;
	switch (t) {
		case '+':
			ans = num1 + num2;
			break;
		case '-':
			ans = num1 - num2;
			break;
		case '*':
			ans = num1 * num2;
			break;
		case '/':
			ans = num1 / num2;
			break;
		default:
			return -1;
	}
	return ans;
}

int main() {
	stack<string> tokens;
	stack<char> ope;
	stack<double> nums;
	string a;
	while (cin >> a) {
		tokens.push(a);
	} 
	while (!tokens.empty()) {
		string tmp = tokens.top();
		tokens.pop();
		if (isNum(tmp)) {
			nums.push(stod(tmp));
		} else {
			char t = tmp[0];
			double num1 = nums.top();
			double num2 = nums.top();
			nums.pop(); nums.pop();
			nums.push(calculate(num1,num2,t));
		}
	}
	printf("%lf",nums.top());
	return 0;
}

另一种做法使用了递归，来自网上的大佬，思路是利用函数的调用顺序同样是栈的方式，仅供参考

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

double solve(){
    char s[10005];
    cin >> s;
    switch(s[0])
    {
    case '+':
        return solve() + solve();
        break;
    case '-':
        return solve() - solve();
        break;
    case '*':
        return solve() * solve();
        break;
    case '/':
        return solve() / solve();
        break;
    default:
        return atof(s);
        break;
    }
}

int main(){
    printf("%.6lf\n", solve());
    return 0;
}

1018. 一元多项式乘法

幽默大模拟，感觉写了一年
总结几个思路：
1、用while(cin >> s1 >> s2)的方式，每次读入一行两个多项式
2、写一个函数，处理单个多项式s1，将它分割成若干个单项；开一个数组，用coef1[i]表示幂次为i的那一项的系数，s2同样处理

具体来说，你可以想象，一个完整单项的形式应该是+/- ax^b，特殊情况主要是：如果是第一项则不会有+号；如果是常数项则没有b，如果系数唯一不会有a

所以我采用的就是在遍历过程中分步判断有没有+/-号——判断有没有a，如果有，逐位计算直到得到系数——判断有没有x——判断有没有^，如果有，逐位计算直到得到指数的做法，应该涵盖了所有情况

3、要求两个多项式的乘积，可以再开一个数组coef，coef[k]同样表示幂次为k的那一项的系数

其实也就是要写一个两重循环遍历coef1和coef2，假设现在遍历到了coef1[i]和coef2[j]，那么就为coef[i+j]的值加上coef1[i]*coef2[j]，也就表示乘积的i+j次幂项的系数加上这个值（为什么是加上而不是赋值呢？因为可能有多种乘积的情况的指数是相同的~比如x^3 * x^2和x * x^4）

举例，coef1[2] = 3，coef2[4] = 5，分别表示3x^2和5x^4，它们的乘积也就是(3*5)x^(2+4)，即15x^6，你需要为coef[6]加上15

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

int coef1[53] = {0};
int coef2[53] = {0};
int coef[103] = {0};

void solve(const string& s,int* c) {
	int cf,poww,flag;
	int point = 0;
	while (point < s.size()) {
		cf = 0;
		poww = 0;
		flag = 1;
		if (s[point] == '+') {
			flag = 1;
			point++;
		} else if (s[point] == '-') {
			flag = -1;
			point++;
		}
		if (s[point] == 'x') {
			cf = 1;
		} else {
			while (isdigit(s[point])) {
				cf *= 10;
				cf += s[point] - '0';
				point++;
			}
		}

		if (s[point] == 'x') {
			point++;
			poww = 1;
		}
		
		if (s[point] == '^') {
			point++;
			poww = 0;
			while (isdigit(s[point])) {
				poww *= 10;
				poww += s[point] - '0';
				point++;
			}
		}
		
		c[poww] += cf * flag;
//		cout << flag << endl;
//		cout << "solve" << poww <<" "<< cf*flag << endl;
	}
}

int main() {
	string s1,s2;
	while (cin >> s1 >> s2) {
		memset(coef1,0,sizeof(coef1));
		memset(coef2,0,sizeof(coef2));
		memset(coef,0,sizeof(coef));
		solve(s1,coef1);
		solve(s2,coef2);
		for (int i = 0;i < 50;i++) {
			for (int j = 0;j < 50;j++) {
				coef[i+j] += coef1[i] * coef2[j];
			}
		}
		for (int i = 100;i >= 0;i--) {
			if (coef[i] != 0) {
				cout << coef[i] << " ";
			}
		}
		cout << endl;
	}
}

1019. 表达式

被恶心到了，实在不想写，csdn上有很多讲解，所以摆（）
放上代码以供参考

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

stack<int> nums;
stack<char> opes;
string expression;
int point = 0;

map<char, int> priority;

int getNum() {
	int res = 0;
	while (point < expression.size() && isdigit(expression[point])) {
		res = res * 10;
		res += expression[point] - '0';
		point++;
	}
	return res;
}

int Calculate(int num2, int num1, char op) {
	switch(op) {
		case '+':
			return num2 + num1;
		case '-':
			return num2 - num1;
		case '*':
			return num2 * num1;
		case '/':
			return num2 / num1;
		default:
			return 0;
	}
}

void processTop() {
	if (nums.size() < 2 || opes.empty()) return;
	int num1 = nums.top();
	nums.pop();
	int num2 = nums.top();
	nums.pop();
	char op = opes.top();
	opes.pop();
	nums.push(Calculate(num2, num1, op));
}

int main() {
	cin >> expression;

	priority['+'] = priority['-'] = 1;
	priority['*'] = priority['/'] = 2;
	priority['('] = 0;

	int n = expression.size();

	char last = 'o';

	while (point < n) {
		char ch = expression[point];

		if (ch == ' ') {
			point++;
			continue;
		}

		if (ch == '-' && (last == 'o' || last == '(')) {
			point++;
			int num = getNum();
			nums.push(-num);
			last = 'n';
		} else if (isdigit(ch)) {
			int num = getNum();
			nums.push(num);
			last = 'n';
		} else if (ch == '(') {
			opes.push(ch);
			point++;
			last = '(';
		} else if (ch == ')') {
			while(!opes.empty() && opes.top() != '(') {
				processTop();
			}
			if (!opes.empty()) {
				opes.pop();
			}
			point++;
			last = 'n';
		} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
			while (!opes.empty() && priority[opes.top()] >= priority[ch]) {
				processTop();
			}
			opes.push(ch);
			point++;
			last = 'o';
		} else {
			point++;
		}
	}
	while (!opes.empty()) {
		processTop();
	}
	if (!nums.empty()) {
		cout << nums.top() << endl;
	} else {
		cout << "0" << endl;
	}

	return 0;
}

1020. 迷宫（可以自己用栈实现，也可以用图的遍历算法实现）

很板的dfs/bfs题，建议学完图论再回来看

#include <bits/stdc++.h>

using namespace std;
int mapp[105][105] = {0};

bool visited[105][105] = {false};

bool flag = false;
int n,x1,x2,yy1,yy2;

int direction[8][2] = {
        {-1, 1}, {0, 1}, {1, 1}, {-1, 0}, {1, 0}, {-1, -1}, {0, -1}, {1, -1}
    };
    
void dfs(int x,int y) {
    
    if (flag) return;
    
	if(x == x2 && y == yy2) {
		flag = true;
		return;
	} 
	for (int i = 0;i < 8;i ++) {
		int* dir = direction[i];
		int xx = x + dir[0];
		int yy = y + dir[1];
		if (0 <= xx && xx < n && 0 <= yy && yy < n && (!visited[xx][yy]) && (mapp[xx][yy] == 0)) {
			visited[xx][yy] = true;
			dfs(xx,yy);
			if (flag) return;
		}
	}
}

int main() {
	cin>>n;
	cin>>x1>>yy1>>x2>>yy2;
	string line;
	
	for (int i = 0;i < n;i++) {
		cin>>line;
		for (int j = 0;j < n;j++) {
			mapp[i][j] = line[j] - '0';
		}
	}
	
	dfs(x1,yy1);
	if (flag) {
		printf("yes\n");
	}else{
		printf("no\n");
	}
	 
	return 0;
}