首页 > 华为4月7日机考
头像
isACaiB
编辑于 2021-04-10 16:23
+ 关注

华为4月7日机考


第一题
并查集,并查集的特点用于合并集合,但是集合元素必须用数字,所以先把string名字用map映射为数字,然后根据小朋友的意愿逐个合并即可。

/*
    题目描述:
    幼儿园老师安排小朋友做游戏,现在需要给N个小朋友进行分组,老师让每个同学写一个名字,代表这位小朋友想和谁分到一组,请问老师在满足所有小朋友意思的情况下,最多可以将班级分为几组?

    输入描述:
    第一行输入N,0<N<=100000
    接下来是N行代表每个小朋友希望和谁分到一组,如:”John Jack”,代表John希望和Jack分到一组,两个名字之间以空格分割,名字本身不存在空格。

    输出描述:
    分组的最多数量

    输入:
    6
    Jack Tom
    Alice John
    Jessica Leonie
    Tom Alice
    John Jack
    Leonie Jessica

    输出:
    2
*/
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<vector>
using namespace std;

int findRoot(vector<int>& parent, int x){
    // return x == parent[x] ? x : findRoot(parent, parent[x]);  // 路径折叠后如下
    if(x != parent[x]){
        parent[x] = findRoot(parent, parent[x]);
    }
    return parent[x];
}

void unionElement(vector<int>& parent, vector<int>& rank, int a, int b){
    int aRoot = findRoot(parent, a);
    int bRoot = findRoot(parent, b);

    if(rank[aRoot] < rank[bRoot]){
        parent[aRoot] = bRoot;
    }else{
        parent[bRoot] = aRoot;
        if(rank[aRoot] == rank[bRoot]){
            rank[aRoot]++;
        }
    }

}

bool isSame(vector<int>& parent, int a, int b){
    return findRoot(parent, a) == findRoot(parent, b);
}

int main(){
    int n;
    cin >> n;
    string name1, name2;
    map<string, int> nameIdMap;
    vector<pair<string, string> > vec;
    vector<int> parent(n);
    vector<int> rank(n,0);
    set<int> retSets;
    int i = 0;
    while(n--){
        cin >> name1 >> name2;
        nameIdMap[name1] = i;
        parent[i] = i;
        i++;
        vec.emplace_back(pair<string, string>(name1, name2));
    }

    for(pair<string, string> p : vec){
        int a = nameIdMap[p.first];
        int b = nameIdMap[p.second];
        if(isSame(parent, a, b)){
            continue;
        }
        unionElement(parent, rank, a, b);
    }

    for(int index = 0; index < vec.size(); index++){
        retSets.insert(findRoot(parent, index));
    }

    cout <<  retSets.size() << endl;
    return 0;
}

第二题
我认为类似于实现一个调度器,理清思路,按照题意逐步实现即可。这不是最好的方法,其他方法我也没想出来。

/*
    输入:第一行输入以逗号分隔的一行数,表示任务编号从零开始的任务耗时
    第二行用逗号分隔的依赖关系,如:0->2,2->4,2->6 表示任务号为0的任务依赖任务号为2的任务,以此类推。
    任务执行存在多重依赖(任务2依赖任务4和任务6)但不会循环依赖,如果任务存在依赖且依赖未完成,则从新到任务队列对位排队。

    输出:任务编号从零开始的实际任务耗时,用逗号隔开

    例子:
    输入:
            1,3,4,5,8,5,3,6
            0->2,2->4,2->6

    输出:   35,3,34,8,16,21,24,30

*/

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

using namespace std;

static int totleWastTime = 0;

class TaskInfo
{   public:
        int needTime;
        set<int> idependWho;
        set<int> whoDependMe;
        TaskInfo() : idependWho(), whoDependMe(){
        }
};

using namespace std;
int main(){


    string line;

    vector<TaskInfo> taskInfoMap;
    queue<int> qTask;

    getline(cin, line);
    stringstream ss1(line);
    string time;
    while(getline(ss1, time, ',')){
        TaskInfo tempTaskInfo;
        tempTaskInfo.needTime = stoi(time);
        taskInfoMap.emplace_back(tempTaskInfo);
    }
    for(TaskInfo tempTaskInfo : taskInfoMap){
        cout << tempTaskInfo.needTime << " ";
    }
    cout << endl;

    getline(cin, line);
    stringstream ss2(line);
    string depend;
    vector<int> tempV;
    while(getline(ss2, depend, ',')){

        cout << depend << endl;

        for(char ch : depend){
            if(isdigit(ch)){
                tempV.push_back(ch-'0');
            }
        }
        taskInfoMap[tempV[0]].idependWho.insert(tempV[1]);
        taskInfoMap[tempV[1]].whoDependMe.insert(tempV[0]);
        tempV.clear();
    }
    cout << "--" << endl;

    vector<int> ret(taskInfoMap.size());
    for(int taskId = 0; taskId < taskInfoMap.size(); taskId++){
        qTask.push(taskId);
    }
    cout << "Schedul Begin!" << endl;



    while(!qTask.empty()){
        int taskId = qTask.front();
        cout << "**Cureent queue Head is Task " << taskId  << " ** "<< endl;
        qTask.pop();
        TaskInfo taskInfo = taskInfoMap[taskId];
        if(taskInfo.idependWho.size() == 0){

            totleWastTime += taskInfo.needTime;
            ret[taskId] = totleWastTime;
            cout << "Do Task " << taskId << ",Task" << taskId << " has wait for " << totleWastTime <<endl;
            set<int> dependMeSet = taskInfoMap[taskId].whoDependMe;
            for(int dependMeId : dependMeSet){
                taskInfoMap[dependMeId].idependWho.erase(taskId);
                cout << "Task " << dependMeId << " not depend " << "Task " << taskId << " any more." << endl;
            }

        }else{
            set<int> dependMeSet = taskInfoMap[taskId].idependWho;
            cout << "Task " << taskId << " is still depend " << "Task ";
            for(int iDependWhoId : dependMeSet){
                 cout << iDependWhoId << ",";
            } 
            cout << "so, we put Task " << taskId << " in queue Tail." << endl;
            qTask.push(taskId);

        }
        cout << endl;
    }


    for(int t : ret){
        cout << t << " ";
    }
    cout << endl;

    return 0;
}

第三题
dfs,如果坐标超出边界直接返回,否则把当前坐标位置的耗时加到当前路径耗时中,如果超出总时间直接返回进行剪枝。如果没超出总时间判断当前坐标是否到达右下角了,如果是,尝试用当前路径耗时更新游玩耗时最大值。如果当前还没到右下角,继续dfs右侧和下边的坐标。

/*
    第一行输入三个数据:m代表矩阵行数,n代表矩阵列数,t代表最长玩时间
    接下来输入m*矩阵,矩阵元素的值为该景点需要的游玩时间。

    要求:从左上角出发,只能向下或向右,最终到达右下角,游玩用时最接近t且不超过t
    输出最长的游玩用时,不存在合适的用时返回-1

    例:
    输入 :

*/

#include<iostream>
#include<vector>
using namespace std;

static int totleTime;
static int curWasteTimeMax = -1;
static int m;
static int n;

void dfs(const vector<vector<int> >& matrix, int i, int j, vector<int> rout, int curWasteTime){
    if(i > n-1 || j > m-1){
        return;
    } 

    curWasteTime += matrix[i][j];
    if(curWasteTime > totleTime){
        return;
    } 
    rout.push_back(matrix[i][j]);

    if(i == n-1 && j == m-1){

        cout << "cur root : ";
        for(int a : rout){
            cout << a << " ";
        }
        cout << " --curWasteTime : " << curWasteTime << " --curWasteTimeMax : " << curWasteTimeMax ;
        cout << endl;

        curWasteTimeMax = curWasteTimeMax < curWasteTime ? curWasteTime : curWasteTimeMax;

    }
    dfs(matrix, i+1, j, rout, curWasteTime);
    dfs(matrix, i, j+1, rout, curWasteTime);
}


int main(){

    cin >> m >> n >> totleTime;
    vector<vector<int> > matrix(m ,vector<int>(n));

    int val;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            cin >> val;
            matrix[i][j] = val;
        }
    }
    vector<int> rout;
    dfs(matrix, 0, 0, rout, 0);
    cout << curWasteTimeMax << endl;


    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐