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模式说，并且自己的输入他都没有说清楚，结果搞了很多时间；