10.25 s2c笔试
1、二叉树的最大路径和;66%
#include<bits/stdc++.h> using namespace std; struct node{ int val; vector<node*> childs; node(int val): val(val){}; node(): val(0){}; }; long ret = INT_MIN; long get_max_path(node* n){ if(n == NULL) return 0; if(n->childs.size() == 0) return n->val; long cur_path_len = 0; long left = 0, right = 0; left = get_max_path(n->childs[0]); if(n->childs.size()> 1) right = get_max_path(n->childs[1]); cur_path_len = left + right+ (long)n->val; cout << cur_path_len << ' ' << n->val << endl; ret = max(ret, cur_path_len); return max(left, right) + (long)n->val; } int main(){ int n; cin >> n; vector<node> e(n); for(int i=0; i< n; i++){ cin >> e[i].val; } for(int i=0; i< n; i++){ if(i == 0) continue; int father; cin >> father; e[father].childs.push_back(&e[i]); } for(int i=0; i< n; i++){ cout << e[i].childs.size() << endl; } node* root = &e[0]; get_max_path(root); cout << ret; return 0; }
2、能到达出口的最小操作次数;100%
#include<bits/stdc++.h> using namespace std; bool is_location(int x, int y, int m, int n){ return x>=0 && x< m && y>= 0 && y< n; } int main(){ int m, n; pair<int, int> start, end; cin>> m >> n; cin >> start.first >> start.second; cin >> end.first >> end.second; start.first -= 1; start.second -= 1; end.first -= 1; end.second -= 1; vector<string> maps(m); for(int i=0; i< m; i++){ cin >> maps[i]; } // 节点是否访问过 unordered_set<int> visited; visited.insert(start.first*n + start.second); queue<pair<int, int>> q; q.push(start); long ret = 0; vector<pair<int, int>> D = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; while(!q.empty()){ int size = q.size(); ret += 1; for(int i=0; i< size; i++){ auto front = q.front(); q.pop(); for(auto d: D){ pair<int, int> next = {front.first+d.first, front.second+d.second}; if(is_location(next.first, next.second, m, n)){ if(visited.find(next.first*n+next.second) != visited.end() || maps[next.first][next.second] == '*') continue; if(next.first == end.first && next.second == end.second){ cout << ret; return 0; } q.push(next); visited.insert(next.first*n+next.second); } } } } cout << -1; return 0; }
3、使用Bash写出0-n中所有7的倍数;
题目量太大了!!!一共一个半小时
1、视频题,说你在平常时间怎么做出重大的决定;
2、选择题20题,有C++问题,还有一些推理题
3、解答题:5题
4、编程题:3题;这个第一题的二叉树他用ACM模式说,并且自己的输入他都没有说清楚,结果搞了很多时间;
#S2C笔试#