华为2022-03-30笔试3题
第三题太恶心了,最后五秒钟第一次有通过,通过了90%。。。
// 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; }