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

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

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

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

第一道：缓存转发数据包统计（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。

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

2 50,60 30,25 120 

输出描述：

55 

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

参考代码：

// 关注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  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 

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

1 

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

参考代码

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

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

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

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

当根i不改变时（即合并两个都包含i的联通块）状态转移方程是：

#include  #include  #include  #include  #include  #include  #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】关注更多新鲜好文和互联网大厂的笔经面经。