2021.5.19 华为实习机试题解：1 令牌 2 Huffman数的WPL 3 防火墙

短命女 2023-01-23 02:50 27阅读 0赞

第一题是一个模拟，编号为1-n的n个人做成一圈，
    编号为i的人手上的令牌是i个，如果他被选出，
    就把令牌交给下一个人
    选择人的方式有正序和逆序两种，
    正着数的第几个出局
    倒着数的第几个出局

直接模拟，但是容易出bug

第二题：构建哈夫曼树，并返回最小代价WPL
    WPL计算，使用优先队列，将所有节点看做单独的树，这样就构成了一个森林
    每次从森林里面挑出最小的两个进行合并直到变成一个树
    
    WPL = 所有叶子的权重*叶子深度求和
    其实就是所有非叶子节点的权重求和，证明省略
    其实在构建的过程中每次形成新的节点的时候将权重累加即可

// 本题为考试单行多行输入输出规范示例，无需提交，不计分。
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <sstream>
    #include <queue>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    int help(vector<int>& a) { 
    
        priority_queue<int,vector<int>,greater<int>> q;
    
        int t;
        for (int i : a) { 
            q.push(i);
        }
    
        t = 0;
        while (q.size()>1){ 
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            t += a + b;
            q.push(a + b);
        }
        cout << t << endl;
        return t;
    }
    
    int main() { 
    
        // [2,4,5,7]
    
        string s = "[2,4,5,7]";
        s = s.substr(1);
        s.pop_back();
        
        stringstream ss;
        ss << s;
        vector<int>a;
        a.reserve(100);
        string str;
        while (getline(ss,str,',')){ 
            a.push_back(stoi(str,0,10));
        }
    
        help(a);
    
        return 0;
    }

第三题
    
    区间查询
    
    区间有左右端点和id
    三种操作，插入 删除 查询
    要求查询的复杂度不高于logn
    
    查询给一个数，看这个数落在了哪一个区间 如果有多个选择id小的那个

感觉是二分查找，但是没有做出来