5.19 华为算法笔试经验

华为机试一共三道题，对应的分值分别为100分、200分、300分。下面介绍这次笔试题目

第一题

一共有N个员工围成一个圆圈，分别是1，2，…，N每一个员工身上有对应数量的令牌，轮流从顺时针以及逆时针进行报数，顺时针报数周期为R，逆时针报数周期为L。顺时针从1开始报数，逆时针开始从N开始报数，被报到的员工K阵亡，并将令牌给下一个人（顺时针给K+1，逆时针给K-1，如果不存在的话，依次传递），游戏持续到只剩下M个人停止。其中，M=max(L,R)-1。例如，L=R=3，那么第一次报数到3号，3号阵亡，将令牌给4号，4号拥有7块令牌，第二次逆时针报数，8号阵亡，令牌给7号，游戏持续到只剩2名员工。最后返回拥有令牌数最多的员工编号，以及它的令牌数，如果最多的有多个，返回编号最小的那个。
例子：N = 10，L=R=3
第一轮：3号阵亡，4号令牌为7
第二轮：8号阵亡，7号令牌为15
第三轮：6号阵亡，7号令牌为21
第四轮：4号阵亡，2号令牌为9
第五轮：10号阵亡，1号令牌为11
第六轮：9号阵亡，7号令牌为30
第七轮：5号阵亡，7号令牌为35
第八轮：1号阵亡，7号令牌为46
剩于两人，2（9）、7（46）
7号获胜
思路：模拟题，可以采用双向循环链表，由于此题数据量不大，可以直接采用数组打标记的方式

第二题

题目太长，而且图很多，大致意思就是给你一个数组，让你求其构成的hufuman树的WPL
注意点：

• 输入格式：[2, 3, 4, 5]
• WPL为带权路径长度，构造树的过程中可以得到，因此不需要实际生成一颗树
• 优先队列的使用
  由于当时没有意识到WPL的计算不需要构建树，还是构建了树，并用了层次遍历的方法

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>

using namespace std;

struct Node {
    Node* left;
    Node* right;
    int w;
    Node(int num) {
        w = num;
        left = right = nullptr;
    }
   /* bool operator> (Node* other)const {
        return w < other->w;
    }
    bool operator< (Node* other)const {
        return w > other->w;
    }*/
};

int main() {
    auto cmp = [](Node* a, Node* b) {
        return a->w > b->w;
    };
    priority_queue<Node*, vector<Node*>, decltype(cmp)> q(cmp);
    string str;
    getline(cin, str);

    str = str.substr(1, str.size() - 2);

    stringstream ss(str);
    while (getline(ss,str,',')) {
        q.push(new Node(stoi(str)));
    }
    while (q.size() > 1) {
        Node* a = q.top();
        q.pop();
        Node* b = q.top();
        q.pop();
        Node* c = new Node(a->w + b->w);
        c->left = a;
        c->right = b;
        q.push(c);
    }
    Node* root = q.top();
    queue<Node*> t;
    int ans = 0;
    t.push(root);
    int level = 0;
    while (!t.empty()) {
        int len = t.size();
        for (int i = 0; i < len; ++i) {
            Node* cur = t.front();
            t.pop();
            if (cur->left == nullptr) {
                ans += cur->w * level;
            }
            else {
                t.push(cur->left);
                t.push(cur->right);
            }
        }
        level++;
    }
    cout << ans << endl;
    return 0;
}

第三题

给你很多个区间，区间之间有交集，主要操作有三种，增加一个区间，删除一个区间，查询一个点所在区间，每个区间都有个编号，要求查询时间复杂度为logn，如果所查询的点有多个区间，返回编号最小的区间编号。
解题思路：主要是查询比较复杂，由于区间数量很多（设为N），可以用一个set标记0-INT_MAX上所有点被覆盖区间的最小编号，然后查询时直接取出，但内存有限，所以考虑用离散化的方式，将所有区间端点进行映射映射到0-2N 范围中，然后对每个区间端点及其右边区域进行标记，采用二分查找查找所在点所离散的端点，即为最终答案，且复杂度为logN。需要注意的事，离散化后端点所代表的的区间为[n, n+1)，当所查询的点恰好为右端点时得不到正确答案，因此，需要一个额外的数组记录端点被覆盖的最小区间号。更新和删除复杂度为NlogN