华为2022-03-30笔试3题

// P1 85% 
// 5 6
// A B A B A A
// 输出 1 4
//#include<iostream>
//#include<algorithm>
//#include<cstring>
//#include<unordered_map>
//#include<vector>
//using namespace std;
//
//int main() {
//	int n, y; cin >> n >> y;
//	char c;
//	vector<int> id(n+1, 0);
//	vector<bool> used(n+1, 0);
//	bool suc = 1;
//	while (y--) {
//		cin >> c;
//		if (c == 'A') {
//			bool get = 0;
//			for (int i = 1; i <= n; i++) {
//				if (!used[i]) {
//					id[i]++;
//					get = 1;
//					if (id[i] == 4) {
//						used[i] = true;
//					}
//					if (suc && y == 0) {
//						cout << i << endl << id[i];
//						return 0;
//					}
//					break;
//				}
//			}
//			if (!get)suc = 0;
//		}
//		else {
//			bool get = 0;
//			for (int i = 1; i <= n; i++) {
//				if (id[i]==0) {
//					used[i] = true;
//					get = 1;
//					id[i] = 4;
//					if (suc&&y == 0) {
//						cout << i << endl << 1;
//						return 0;
//					}
//					break;
//				}
//			}
//			if (!get)suc = 0;
//		}
//	}
//	if(!suc)
//		cout << 0 << endl << 0;
//	system("pause");
//	return -1;
//}

// P2 100%
//5 5
//0 1
//3 3
//1
//2 2
// output: 4 5 
//#include<iostream>
//#include<algorithm>
//#include<cstring>
//#include<unordered_map>
//#include<vector>
//using namespace std;
//
//int minDis, nPath = 0;
//int m, n, startx, starty, endx, endy, g, t1, t2;
//const vector<vector<int>> d = { {-1,0},{1,0},{0,-1},{0,1} };
//
//void dfs(const vector<vector<int>>& e, vector<vector<bool>>& vis, int dis, int x, int y) {
//	if (x == endx && y == endy) {
//		if (minDis > dis) {
//			minDis = dis;
//			nPath = 1;
//		}else if(minDis== dis)
//			nPath++;
//		return;
//	}
//	if (dis == minDis)return;
//	vis[x][y] = 1;
//	dis++;
//	for (int i = 0; i < 4; i++) {
//		int dx = x + d[i][0], dy = y + d[i][1];
//		if (dx >= 0 && dx < m && dy >= 0 && dy < n && e[dx][dy]==0&&vis[dx][dy] == 0) {
//			dfs(e, vis, dis, dx, dy);
//		}
//	}
//	vis[x][y] = 0;
//}
//
//int main() {
//	cin >> m >> n >> startx >> starty >> endx >> endy >> g;
//	vector<vector<int>> e(m, vector<int>(n, 0));
//	vector<vector<bool>> vis(m, vector<bool>(n, 0));
//	while (g--) {
//		cin >> t1 >> t2;
//		e[t1][t2] = 1;
//	}
//	minDis = m + n;
//	dfs(e, vis, 0, startx, starty);
//	cout << nPath << " " << minDis;
//	system("pause");
//	return 0;
//}

// P3 90% 最后5s第一次通过
#include<iostream>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;
//[1,2,3,1,null,2,null,null,null,null,null,1,null,null,null]
// 输出[2,1,null]
unordered_map<int, vector<vector<int>>> m;
int getH(const vector<int>& t, int root) {
	if (root>=t.size()||t[root] == 0)return 0;
	int maxH = 1 + max(getH(t, root * 2 + 1), getH(t, root * 2 + 2));
	//return maxH;
}
pair<int, vector<int>> getLayer(const vector<int>& t, int root) {
	int height = getH(t, root);
	if (height < 2)return { 0,vector<int>(0) };
	queue<int> q;
	vector<int> subTree;
	q.push(root);
	int h = height;
	while (h>0&&!q.empty()) {
		h--;
		queue<int> q2;
		while (!q.empty()) {
			int index = q.front();
			q.pop();
			subTree.push_back(t[index]);
			if (h) {
				q2.push(2 * index + 1);
				q2.push(2 * index + 2);
			}
		}
		q = q2;
	}
	return make_pair(height, subTree);
}
int main() {
	vector<int> t;
	string a;
	cin >> a;
	for (int i = 1; i < a.length();) {
		if (isdigit(a[i])) {
			t.push_back(a[i] - '0');
			i += 2;
		}
		else {
			t.push_back(0);
			i += 5;
		}
	}

	int n = t.size();
	int maxHeight;
	int ans_maxH = 1;
	vector<int> ans_subTree;
	for (int i = 0; i < n; i++) {
		pair<int, vector<int>> p = getLayer(t, i);
		if (p.first < 2)continue;
		if (i == 0)
			maxHeight = p.first;
		else {
			if (m.count(p.first) && p.first > ans_maxH) {
				for (int j = 0; j < m[p.first].size(); j++)
					if (p.second == m[p.first][j]) {
						ans_maxH = p.first;
						ans_subTree = p.second;
						break;
					}
			}
			m[p.first].push_back(p.second);
		}
	}
	cout << "[";
	for (int i = 0; i < ans_subTree.size(); i++) {
		if (ans_subTree[i] > 0)
			cout << ans_subTree[i];
		else cout << "null";
		if (i != ans_subTree.size() - 1)
			cout << ",";
	}
	cout << "]";
	system("pause");
	return 0;
}