4.24华为笔试分享C++

腾个时间把代码贴一下

1.第一题: 无需实际建树,sort之后,进行二分查找即可,主要是到达叶节点后需要判断是否退出,否则会多一个L或者R

int main() {
    vector<int>nums;
    int temp;
    while (cin >> temp){
        nums.emplace_back(temp);
    }
    int target = nums.back();
    nums.pop_back();
//    nums = {1,2,3,4,5,6,7};
//    int target = 8;
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    int depth = 0;
    auto p = n + 1;
    while (p){
        depth++;
        p >>= 1;
    }
    if(target > nums.back()){
        cout << "S" + string(depth-2,'R') + "N";
        return 0;
    } else if(target < nums.front()){
        cout << "S" + string(depth-2,'L') + "N";
        return 0;
    }
    int l = 0;
    int r = n;
    int mid = 0;
    int d = 0;
    string ans = "S";
    while (l < r){
        mid = l + ((r-l)/2);
        if(nums[mid] == target){
            ans.push_back('Y');
            cout << ans << endl;
            return 0;
        }
        // 到达叶节点深度,进行判断
        if(d == depth - 2){
            break;
        }
        if(nums[mid] < target){
            ans.push_back('R');
            l = mid + 1;
        } else{
            ans.push_back('L');
            r = mid;
        }
        d++;
    }
    ans.push_back('N');
    cout << ans << endl;
    return 0;
}

2.第二题: 构造一个struct,其包含(int)总得分,(int)连续得分,(string)失分情况和(int)id.之后写一个cmp进行排序即可]

class player{
public:
    int total;
    int lianxu;
    string loss;
    int id;
    player() = default;
    player(int t,int l,string&& lo,int i):
        total(t),lianxu(l),loss(lo),id(i){};
};

int main()
{
    int n,m;
    cin >> n >> m;
    vector<string>arr;
    vector<player>players;
    for(int j = 0; j < n; j++){
        string temp;
        cin >> temp;
        int total = std::count(temp.begin(), temp.end(),'1');
        int cnt = 0;
        int lianxu = 0;
        string loss;
        for(int i = 0; i < temp.size(); i++){
            if(temp[i] == '1'){
                cnt++;
                lianxu = max(lianxu,cnt);
            } else{
                loss.push_back(i + '0');
                cnt = 0;
            }
        }
        players.emplace_back(total,lianxu,std::move(loss),j);
    }
    auto cmp = [&](const player& a,const player& b){
        if(a.total == b.total){
            if(a.lianxu == b.lianxu){
                if(a.loss == b.loss){
                    return a.id < b.id;
                }
                return a.loss > b.loss;
            }
            return a.lianxu > b.lianxu;
        }
        return a.total > b.total;
    };
    std::sort(players.begin(), players.end(),cmp);
    for(int i = 0; i < players.size(); i++){
        cout << players[i].id + 1;
        if(i != players.size() -1 ){
            cout << " ";
        }
    }
    return 0;
}

3.第三题.

读题可知: 这个有向图中的每个节点的出度都是1,并且edges[i] != i [关键条件]

那么,对于并查集的每个连通域来说,这个连通域内最多有一个环,最少有一个环

那么对于一个连通域,我们可以先任选一个点作为出发点,使用快慢指针,快慢指针相遇的位置肯定在环内.

之后从相遇处再绕着走一圈回到相遇处,并将遍历到的节点记录下来,这就是环.

H的计算方式就是 H = 环的长度 - (并查集的大小-环的长度)

int main()
{
    int n;
    cin >> n;
    vector<int>edges(n);
    for(int & edge : edges){
        int temp;
        cin >> temp;
        edge = temp;
    }
    vector<int>root(n,-1);
    vector<int>weight(n,1);
    vector<int>start;
    function<int(int )> find = [&](int x){
        if(root[x] == -1){
            return x;
        }
        return root[x] = find(root[x]);
    };
    auto to_union = [&](int x,int y){
        auto px = find(x);
        auto py = find(y);
        if(px == py){
            start.emplace_back(px);
        } else if(weight[px] > weight[py]){
            root[py] = px;
            weight[px] += weight[py];
        } else{
            root[px] = py;
            weight[py] += weight[px];
        }
    };
    for(int i = 0; i < n; i++){
        to_union(i,edges[i]);
    }
    int ans = INT_MIN;
    vector<int>vec;
    // y快指针,x慢指针
    for(auto x:start){
        auto y = edges[x];
        while (x != y){
            x = edges[x];
            y = edges[edges[y]];
        }
        vector<int>temp = {x};
        y = edges[y];
        while (x != y){
            temp.emplace_back(y);
            y = edges[y];
        }
        int H = (int)temp.size() - (weight[find(x)] - (int)temp.size());
        if(H > ans){
            ans = H;
            vec = temp;
        } else if(H == ans){
            auto k1 = *std::max_element(vec.begin(), vec.end());
            auto k2 = *std::max_element(temp.begin(), temp.end());
            if(k2 > k1){
                vec = temp;
            }
        }
    }
    rotate(vec.begin(), min_element(vec.begin(),vec.end()),vec.end());
    for(int i = 0; i < vec.size(); i++){
        cout << vec[i];
        if(i != vec.size() - 1){
            cout << " ";
        }
    }
    return 0;
}