华为笔试 华为笔试题 0927
笔试时间：2024年09月27日 秋招
历史笔试传送门：2023秋招笔试合集
第一题
题目：绩效互评人员分配
公司组织绩效互评，为了避免有同学或者同团队的人互相打高分，需要将员工分成两组分别打分。给定一个整数n和一个数组GoodRelationShips[][]，其中，n表示人数，数组GoodRelationShips[][]是一个邻接表，GoodRelationShips[i]的元素[a,b,c]代表员工i和员工a，b，c是同学或者同团队。请将这 n个人分成两组，使其每组不再有同学或者同团队的人。GoodRelationShips[][] 的长度范围为 [1,100]。GoodRelationShips[i] 中的元素的范围为 [0,GoodRelationShips.length-1]。GoodRelationShips[i] 不会包含i或者有重复的值.图是无向的: 如果j 在 GoodRelationships[i]里边,那么i也会在GoodRelationShips[j]里边。
解答要求：时间限制: C/C++1000ms,其他语言:2000ms内存限制: C/C++256MB,其他语言:512MB
输入描述
数组形式的员工关系邻接表；
第一行数字代表有N个顶点，顶点编号从0开始；
后续接N行，第i行代表第i-1个顶点和他有关系的同学的顶点编号。
输出描述
分组方案按照节点编号从小到大排序，如两个方案第一个节点相同则按照第二个节点排序，以此类推;方案内部也按照编号从小到大排序。输出排序最靠前的一种方案，如无法分成符合条件的两组，则输出-1如输出如下两种方案时，选择第一种方案，因为方案一的分组2第一个节点编号更小:
分组1:1
分组2:2 3 4 5
和
分组1:1 2
分组2:3 4 5
如输出如下两种方案时，选择第二种方案，因为方案二的分组2第一个
节点编号更小:
分组1:1 2
分组2:3 4 5
和
分组1:1 3
分组2:2 4 5
样例输入一
4
1 3
0 2
1 3
0 2
样例输出一
0 2
1 3
样例输入二
4
1 2 3
0 2
0 1 3
0 2
样例输出二
-1
参考题解
将员工关系建模为无向图，每个员工对应一个节点，关系对应边。通过广度优先搜索（BFS）对图进行二染色，尝试将节点分为两组，确保相邻节点颜色不同。如果在染色过程中发现相邻节点颜色相同，则说明图不是二分图，无法满足分组要求，输出 -1。如果成功染色，则根据颜色将员工分为两组，并对每组中的员工编号进行排序，最后选择字典序最小的分组方案输出。
C++：[此代码未进行大量数据的测试，仅供参考]
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
string toStr(const vector<int>& list) {
if (list.empty()) return "";
stringstream ss;
for (size_t i = 0; i < list.size(); ++i) {
if (i > 0) ss << " ";
ss << list[i];
}
return ss.str();
}
int compare(const vector<int>& a, const vector<int>& b) {
size_t len = min(a.size(), b.size());
for (size_t i = 0; i < len; ++i) {
if (a[i] < b[i]) return -1;
if (a[i] > b[i]) return 1;
}
if (a.size() < b.size()) return -1;
if (a.size() > b.size()) return 1;
return 0;
}
int main() {
int n;
if (!(cin >> n)) {
cout << "-1" << endl;
return 0;
}
cin.ignore();
vector<vector<int>> g(n);
for (int i = 0; i < n; ++i) {
string line;
getline(cin, line);
stringstream ss(line);
int x;
while (ss >> x) {
g[i].push_back(x);
}
}
vector<int> col(n, -1);
bool bip = true;
vector<int> g1, g2;
for (int i = 0; i < n && bip; ++i) {
if (col[i] == -1) {
queue<int> q;
q.push(i);
col[i] = 0;
vector<int> comp = {i};
bool valid = true;
while (!q.empty() && valid) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (col[v] == -1) {
col[v] = col[u] ^ 1;
q.push(v);
comp.push_back(v);
} else if (col[v] == col[u]) {
valid = false;
break;
}
}
}
if (!valid) {
bip = false;
break;
}
int minNode = *min_element(comp.begin(), comp.end());
if (col[minNode] == 1) {
for (int node : comp) {
col[node] ^= 1;
}
}
}
}
if (!bip) {
cout << "-1" << endl;
return 0;
}
for (int i = 0; i < n; ++i) {
if (col[i] == 0) g1.push_back(i);
else g2.push_back(i);
}
sort(g1.begin(), g1.end());
sort(g2.begin(), g2.end());
if (compare(g1, g2) > 0) {
cout << toStr(g2) << endl;
cout << toStr(g1) << endl;
} else {
cout << toStr(g1) << endl;
cout << toStr(g2) << endl;
}
return 0;
}
Java：[此代码未进行大量数据的测试，仅供参考]
import java.util.*;
public class Bipartition {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
System.out.println("-1");
return;
}
int n = sc.nextInt();
sc.nextLine();
List<List<Integer>> g = new ArrayList<>();
for(int i = 0; i < n; i++) {
String line = sc.hasNextLine() ? sc.nextLine().trim() : "";
List<Integer> lst = new ArrayList<>();
if(!line.isEmpty()) {
String[] parts = line.split("\\s+");
for(String p : parts) {
if(!p.isEmpty()) {
lst.add(Integer.parseInt(p));
}
}
}
g.add(lst);
}
int[] col = new int[n];
Arrays.fill(col, -1);
boolean bip = true;
List<Integer> g1 = new ArrayList<>();
List<Integer> g2 = new ArrayList<>();
for(int i = 0; i < n && bip; i++) {
if(col[i] == -1) {
Queue<Integer> q = new LinkedList<>();
q.offer(i);
col[i] = 0;
List<Integer> comp = new ArrayList<>();
comp.add(i);
boolean valid = true;
while(!q.isEmpty() && valid) {
int u = q.poll();
for(int v : g.get(u)) {
if(col[v] == -1) {
col[v] = col[u] ^ 1;
q.offer(v);
comp.add(v);
}
else if(col[v] == col[u]) {
valid = false;
break;
}
}
}
if(!valid) {
bip = false;
break;
}
int min = Collections.min(comp);
if(col[min] == 1) {
for(int node : comp) {
col[node] ^= 1;
}
}
}
}
if(!bip) {
System.out.println("-1");
return;
}
for(int i = 0; i < n; i++) {
if(col[i] == 0) g1.add(i);
else g2.add(i);
}
Collections.sort(g1);
Collections.sort(g2);
if(compare(g1, g2) > 0) {
System.out.println(toStr(g2));
System.out.println(toStr(g1));
}
else {
System.out.println(toStr(g1));
System.out.println(toStr(g2));
}
}
private static String toStr(List<Integer> list) {
if(list.isEmpty()) return "";
StringBuilder sb = new StringBuilder();
for(int i = 0; i < list.size(); i++) {
if(i > 0) sb.append(" ");
sb.append(list.get(i));
}
return sb.toString();
}
private static int compare(List<Integer> a, List<Integer> b) {
int len = Math.min(a.size(), b.size());
for(int i = 0; i < len; i++) {
if(a.get(i) < b.get(i)) return -1;
if(a.get(i) > b.get(i)) return 1;
}
if(a.size() < b.size()) return -1;
if(a.size() > b.size()) return 1;
return 0;
}
}
Python：[此代码未进行大量数据的测试，仅供参考]
def to_str(lst):
return " ".join(map(str, lst))
def compare(a, b):
len_a, len_b = len(a), len(b)
for i in range(min(len_a, len_b)):
if a[i] < b[i]:
return -1
if a[i] > b[i]:
return 1
return (len_a > len_b) - (len_a < len_b)
def main():
try:
n = int(input())
except ValueError:
print("-1")
return
g = []
for _ in range(n):
line = input().strip()
g.append(list(map(int, line.split())) if line else [])
col = [-1] * n
bip = True
g1, g2 = [], []
for i in range(n):
if col[i] == -1 and bip:
queue = [i]
col[i] = 0
comp = [i]
valid = True
while queue and valid:
u = queue.pop(0)
for v in g[u]:
if col[v] == -1:
col[v] = col[u] ^ 1
queue.append(v)
comp.append(v)
elif col[v] == col[u]:
valid = False
break
if not valid:
bip = False
break
if min(comp, key=lambda x: col[x]) == 1:
for node in comp:
col[node] ^= 1
if not bip:
print("-1")
return
for i in range(n):
(g1 if col[i] == 0 else g2).append(i)
g1.sort()
g2.sort()
if compare(g1, g2) > 0:
print(to_str(g2))
print(to_str(g1))
else:
print(to_str(g1))
print(to_str(g2))
if __name__ == "__main__":
main()
第二题
题目：最好的通勤体验
小王是一名环保爱好者，每天选择乘坐公交车上班。不同线路上的公交车会在规定的路线上单向循环行驶，例如708路公交的路线为[2,5,8]，那么公交车会按照2->5->8->2->5->8->…的路线循环行驶，其中路线中的数字为公交站台编号。小王每天上班会从离他家里最近的公交站台上车，然后在他最喜欢的早餐店所在的站台下车买好早餐然后再上车，最后在离公司最近的公交站台下车，允许不限次数地在中途下车换乘其他路线的公交。现在分别给定小王上车、早餐店、下车的公交站台编号，请帮他选择最佳的乘车路线使乘坐的公交车总数最少(如果在同1条公交路线中下车再上车，仍然视为乘坐的同一辆车)，从而获得最好的通勤体验。
解答要求：时间限制: C/C++1000ms,其他语言:2000ms内存限制: C/C++256MB,其他语言:512MB
输入描述
第一行有3个数字，分别表示上车的公交站台编号、早餐店的公交站台编号、下车公交站台编号，依次用空格隔开；
第二行表示公交路线数量，后续的每一行中第1个数字代表该路线的总站台数，剩余的数字表示每条公交路线经过的站点编号，所有数字用空格隔开；
公交路线数量范围在[1,500]，公交站台的编号范围在[1,1000000]，每条公交路线经过的站台数量范围在[2,1500]，路线中的站台编号按升序顺序排序，且每条路线中不包含重复的站台。6.起点站台、购买早餐的站点、终点站台不重复。
输出描述
乘坐的公交路线总数，如果没有匹配的路线请返回-1。
样
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解，包含python、C++、Java多种语言版本，持续更新中。
投递华为等公司10个岗位 >