华为秋招机试三道编程题（2021-09-01）

柔光的暖阳◎ 2022-09-09 14:43 142阅读 0赞

> 通知：**华为**、**阿里**最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在微信公众号【TechGuide】了，私信公众号回复【华为】或者【阿里】即可获得最实时、最详细的笔试题解啦！

> 通知：**华为**、**阿里**最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在微信公众号【TechGuide】了，私信公众号回复【华为】或者【阿里】即可获得最实时、最详细的笔试题解啦！  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]

### 文章目录 ###

*  第一道：缓存转发数据包统计（100%）
 *   *  题目描述
     *  参考代码：
 *  第二道： 查找知识图谱中的实例知识（100%）
 *   *  题目描述
     *  参考代码
 *  第三道：湖泊连通（100%）
 *   *  题目描述
     *  参考代码

# 第一道：缓存转发数据包统计（100%） #

## 题目描述 ##

有k个节点的转发队列，每个节点转发能力为m，缓存能力n(表示此节点可立即转发m个包，剩余的缓存，最多缓存n个包，再剩余的丢弃，缓存的包在下一轮继续转发)。另外，此队列中某些节点可能因故障需要直接跳过转发，但不会有两个连续故障的节点。  
现分两轮操作，第一轮向此队列发送a个数据包让其转发;第二轮，直接驱动让缓存的数据包继续转发。

求两轮最后可能收到的最少数据包总个数(如果第二轮缓存仍有数据包缓存包按丢弃处理)  
1 <= k <= 40  
1 <= m,n <= 1000  
1 <= a <= 1000

例如:有两个节点，节点1(转发能力m:50，缓存能力n:60) 和节点2(m:30，n:25)，发送包数为120。

在没有节点故障时:  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_20_color_FFFFFF_t_70_g_se_x_16]  
**输入描述：**  
第一行队列长度k  
第二行为k个节点转发能力数组，以空格分隔。m,n以逗号分隔，例如10,20 11,21 12,22  
第三行数据包个数a

2
    50,60 30,25
    120

**输出描述：**

**解释:**  
参见题目中的图例，当第一个节点故障时，仅第二个节点转发，此时收到的包最少。

## 参考代码： ##

// 关注TechGuide！ 大厂笔经面经闪电速递！

# 第二道： 查找知识图谱中的实例知识（100%） #

## 题目描述 ##

知识图谱是一种结构化的语义网络，用于描述物理世界中的概念及其实例的相关关系。可以把知识图谱看成是一种有向图，图中的点是概念或实例，图中的边是概念及其实例的相关关系。

现定义一种简单的知识图谱

概念：包括父概念及其子概念，通过subClassOf关系关联，父子概念可以有多个层级；  
实例:仅和概念之间通过instanceOf关系关联:  
关系:以三元组的形式表示，三元组是一个以空格为成员间分隔符的字符串。例如"student subClassOf person"表示student是person的子概念，“apple instanceOf fruit"表示apple是概念fruit的实例。  
给定一个知识图谱，请编写一个方法，可以根据一个概念查找其所有的实例。如果一个概念拥有子概念，那么返回的结果需要包含其所有子概念的实例;如果输入的概念没有实例，则返回字符串"empty”(说明:输出字符串文本不需要包含引号)。

给定的图谱满足以下限制:  
1、有向图中不存在环路  
2、所有点和关系的定义对大小写敏感

**输入描述：**  
输入第1行，表示图谱中关系的数量n，取值范围\[1,10000\]  
从第2行到n+1行，表示图谱中的关系，每一行是一个关系三元组第n+2行，表示待查找的元节点，是关系三元组中存在的点。  
每行字符的长度不超过100。

3
    student subClassOf person 
    Tom inslenceOf student 
    Marry instanceOf person 
    person

**输出描述**  
按字典序升序排列的字符串数组，其内容是概念及其子概念的所有实例。

Marry Tom

**解释:**  
student是person的子概念，Tom是student的实例，Marry是person的  
实例，Marry的字典序小于Tom，所以返回Marry Tom。

## 参考代码 ##

根据instanceOf查找它的父节点是否为target。不管是 subClassOf还是instancOf，左边的是子节点，右边的是父节点，然后利用hash\_set存储是instancOf，最后根据hash\_set遍历其父节点是否到达目标节点即可，若满足则存入到set中，默认字典排序

#include <bits/stdc++.h>
    using namespace std;
    
    int main(int argc,char* argv[]){ 
        int n;
        cin>>n;
        unordered_map<string,string> hash;//val是父节点
        unordered_set<string> instance;//存储instacnOf
    
        string s1,s2,s3;
        for(int i=0;i<n;++i){ 
            cin>>s1>>s2>>s3;
            if(s2=="instanceOf")
                instance.insert(s1);
            hash[s1]=s3;
        }
        string ss;
        cin>>ss;
        set<string> ret;
        for(auto s:instance){ 
            string s1=s;
            while(hash.count(s1)){ 
                if(hash[s1]==ss){ 
                    ret.insert(s);
                    break;
                }
                s1=hash[s1];
            }
        }
        if(ret.size()==0){ 
            cout<<"empty"<<endl;
        }else{ 
            int i=0;
            for(auto s:ret){ 
                if(i==0) cout<<s;
                else cout<<" "<<s;
                ++i;
            }
        }
        return 0;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第三道：湖泊连通（100%） #

## 题目描述 ##

地图上有多个湖泊，为增强湖泊的抗暴雨能力，需要在湖泊间挖出通道使得湖泊之间能够连通(对角线视为不连通)。有的陆地是坚硬的石头，挖通需要耗费的精力是普通陆地的2倍，即一个普通格子的长度为1，一个有坚硬石头的格子的长度为2。  
地图用二维矩阵表示，每个位置只有三种可能，0为湖泊，1为普通陆地，2为坚硬的石头，地图最大为MN。需要返回挖通所有湖泊的最短通道，如果通道不存在的话，返回0  
限制:M、N最大为20,湖泊个数不超过11

**输入描述：**  
第一行为M  
第二行为N  
第三行开始为M\*N的地图矩阵

5 
    4
    0 1 1 0
    0 1 0 0
    0 1 0 0
    0 1 0 1
    1 1 1 1

**输出描述：**  
返回挖通所有湖泊的最短通道

**解释:**  
地图上共有2片湖泊，只需要挖通1块陆地，2片湖泊即可连通。

## 参考代码 ##

这道题是【斯坦纳树】的经典例题。斯坦纳树是这样一类问题：带边权无向图上有几个（一般约10个）点是【关键点】，要求选择一些边使这些点在同一个联通块内，同时要求所选的边的边权和最小。

怎么解决斯坦纳树问题？……其实，就是一种状压DP。

dp\[i\]\[j\]表示以i号节点为根，当前状态为j（j的二进制中已经与i连通的点对应位置为1）。

这个“以i为根”是哪来的呢？其实i可以是联通块中任意一个点，没有额外限制，只是引入这个i就可以DP了。

当根i不改变时（即合并两个都包含i的联通块）状态转移方程是：  
![在这里插入图片描述][79467d599a2a43ae9641dacb7e6ff0d6.png_pic_center]

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <iostream>
    #include <queue>
    #define space putchar(' ')
    #define enter putchar('\n')
    using namespace std;
    typedef long long ll;
    template <class T>
    void read(T &x){ 
        char c;
        bool op = 0;
        while(c = getchar(), c < '0' || c > '9')
        if(c == '-') op = 1;
        x = c - '0';
        while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
        if(op) x = -x;
    }
    template <class T>
    void write(T x){ 
        if(x < 0) putchar('-'), x = -x;
        if(x >= 10) write(x / 10);
        putchar('0' + x % 10);
    }
    
    const int INF = 0x3f3f3f3f;
    int n, m, K, root, f[101][1111], a[101], ans[11][11];
    bool inq[101];
    typedef pair<int, int> par;
    typedef pair<par, int> rec;
    #define fi first
    #define se second
    #define mp make_pair
    #define num(u) (u.fi * m + u.se)
    rec pre[101][1111];
    const int dx[] = { 0, 0, -1, 1};
    const int dy[] = { 1, -1, 0, 0};
    queue<par> que;
    
    bool legal(par u){ 
        return u.fi >= 0 && u.se >= 0 && u.fi < n && u.se < m;
    }
    void spfa(int now){ 
        while(!que.empty()){ 
    	par u = que.front();
    	que.pop();
    	inq[num(u)] = 0;
    	for(int d = 0; d < 4; d++){ 
    	    par v = mp(u.fi + dx[d], u.se + dy[d]);
    	    int nu = num(u), nv = num(v);
    	    if(legal(v) && f[nv][now] > f[nu][now] + a[nv]){ 
    		f[nv][now] = f[nu][now] + a[nv];
    		if(!inq[nv]) inq[nv] = 1, que.push(v);
    		pre[nv][now] = mp(u, now);
    	    }
    	}
        }
    }
    void dfs(par u, int now){ 
        if(!pre[num(u)][now].se) return;
        ans[u.fi][u.se] = 1;
        int nu = num(u);
        if(pre[nu][now].fi == u) dfs(u, now ^ pre[nu][now].se);
        dfs(pre[nu][now].fi, pre[nu][now].se);
    }
    
    int main(){ 
    
        read(n), read(m);
        memset(f, 0x3f, sizeof(f));
        for(int i = 0, tot = 0; i < n; i++)
    	for(int j = 0; j < m; j++){ 
    	    read(a[tot]);
    	    if(!a[tot]) f[tot][1 << (K++)] = 0, root = tot;
    	    tot++;
    	}
        for(int now = 1; now < (1 << K); now++){ 
    	for(int i = 0; i < n * m; i++){ 
    	    for(int s = now & (now - 1); s; s = now & (s - 1))
    		if(f[i][now] > f[i][s] + f[i][now ^ s] - a[i]){ 
    		    f[i][now] = f[i][s] + f[i][now ^ s] - a[i];
    		    pre[i][now] = mp(mp(i / m, i % m), s);
    		}
    	    if(f[i][now] < INF)
    		que.push(mp(i / m, i % m)), inq[i] = 1;
    	}
    	spfa(now);
        }
        write(f[root][(1 << K) - 1]), enter;
        dfs(mp(root / m, root % m), (1 << K) - 1);
        for(int i = 0, tot = 0; i < n; i++){ 
    	for(int j = 0; j < m; j++)
    	    if(!a[tot++]) putchar('x');
    	    else putchar(ans[i][j] ? 'o' : '_');
    	enter;
        }
    
        return 0;
    }

> 恭喜发现宝藏！微信搜索公众号【TechGuide】关注更多新鲜好文和互联网大厂的笔经面经。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/dbcb1ba046b245d8875891c3b8b1469d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/341e739646d64e9080442495c1f0a23b.png
[79467d599a2a43ae9641dacb7e6ff0d6.png_pic_center]: /images/20220829/4c7c8d61ec984d2b9e91fd1329ba998a.png