🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

💻 前言

🍭 关于华为

据说今晚有华为的机试啦，华为的春招也算是正式开始了，关于华为的笔试，大家可以自由选时间去安排，大致时间就是每周三，具体哪一周需要自己去做决定，和 HR 沟通或者邮件📧反馈，一般会有 HR 联系你修改信息，包括后面笔试的成绩，也可以问 HR ，华为的 HR 是真滴很不错 👍

📓 笔试要求

华为的笔试有个硬性规定，笔试分是需要达到 150/600 分才算是通过，三道题目的构成分数构成为 <code>100，200， 300 分，后续的面试流程会根据笔试成绩来进行排序哦。

🪜 笔试技巧

笔试的思维破局

之前写别的公司机试的小伙伴一般都是按照顺序来写的，因为越往后的题目难度越高，这样会形成一个惯性，做每家公司的笔试都这么干。但华为题目的代码编写难易度并不一定是递进的，比如第一题可能是题意很简单，但是码量很大。第三题 可能代码随便写几行就能拿到很多分，大家在机试的时候需要把把握好做题的顺序，每道题可以都先过一遍。

骗分技巧

适当使用暴力骗分，如果对于当前这题没有什么想法，不要多想直接写暴力或许能拿到不少的分数。对于题目要求输出 Yes or No ，或者无解输出 -1 的情况，那么可以试试直接输出，一般也能拿到一些分数这里捞一点那里骗一点，说不定就够 150 分了哦

🥰 题目练手

那么本次就给大家带来今年春招提前批的华为的真题练练手，祝大家今晚发挥超长，笔试 AK ！！ ！！

文章目录

💻 前言🍭 关于华为📓 笔试要求🪜 笔试技巧笔试的思维破局骗分技巧

🥰 题目练手

_________________________________________✈️ 笔试题目🍟 01.K小姐的魔法药水问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码

🌭02.K小姐安排座位题目描述输入格式输出格式样例输入样例输出数据范围题解参考代码

🍔 03.K小姐的魔法材料问题描述输入格式输出格式样例输入样例输出数据范围题解参考代码

🍍 写在最后📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

_________________________________________

✈️ 笔试题目

🍟 01.K小姐的魔法药水

问题描述

K小姐是一位魔法师，她最近在研究一种神奇的魔法药水。这种药水由一系列魔法材料制成，每种材料都有一个正整数的魔法值。K小姐按照特定的规则将这些材料混合：每次她加入一种新的材料时，如果这种材料的魔法值与当前药水最上层材料的魔法值相同，她会取出这两种材料，将它们的魔法值相加后乘以

2

2

2，然后放回一种新的材料。此外，如果最上层材料的魔法值等于下面连续几种材料魔法值之和，她同样会取出这些材料，进行相同的操作。如果这两个条件都不符合，她就会简单地将新的材料加入到药水的最上层。

现在，K小姐按照一定顺序加入了一系列材料，请你计算最终药水中从上到下各层材料的魔法值。

输入格式

输入为一行，包含若干个由空格分隔的正整数，表示K小姐按顺序加入药水中的材料的魔法值。

输出格式

输出为一行，包含若干个由空格分隔的正整数，表示最终药水中从上到下各层材料的魔法值。

样例输入

55 66 121 5 5

样例输出

10 242

数据范围

每个正整数的范围为

1

1

1 到

2

31

−

1

2^{31}-1

231−1。正整数的个数范围为

1

1

1 到

1000

1000

1000。

题解

本题可以使用单调栈的思想来解决。可以维护一个栈，栈中存储药水中各层材料的魔法值的前缀和。每次加入一种新的材料时，判断：

如果新材料的魔法值等于栈顶元素与次栈顶元素的差，则将栈顶元素弹出，并将新材料的魔法值乘以

2

2

2 加到新的栈顶元素上。否则，将新材料的魔法值加到栈顶元素上，并将结果作为新的栈顶元素入栈。

最后，栈中的元素就是最终药水中从上到下各层材料的魔法值。

为了方便判断条件

1

1

1，可以用一个哈希表来存储每个前缀和第一次出现的位置。

时间复杂度

O

(

n

)

O(n)

O(n)，空间复杂度

O

(

n

)

O(n)

O(n)。其中

n

n

n 为材料的个数。

参考代码

Cpp

#include <iostream>

#include <vector>

#include <unordered_map>

using namespace std;

int main() {

vector<long long> sum = { 0};

unordered_map<long long, int> pos = { { 0, 0}};

int x;

while (cin >> x) {

long long curr = x;

while (pos.count(sum.back() - curr)) {

int idx = pos[sum.back() - curr];

int cnt = sum.size() - 1 - idx;

while (cnt--) {

pos.erase(sum.back());

sum.pop_back();

}

curr *= 2;

}

sum.push_back(sum.back() + curr);

pos[sum.back()] = sum.size() - 1;

}

for (int i = sum.size() - 1; i > 0; i--) {

cout << sum[i] - sum[i - 1] << " ";

}

return 0;

}

Java

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

List<Long> sum = new ArrayList<>();

Map<Long, Integer> pos = new HashMap<>();

sum.add(0L);

pos.put(0L, 0);

while (sc.hasNextInt()) {

int x = sc.nextInt();

long curr = x;

while (pos.containsKey(sum.get(sum.size() - 1) - curr)) {

int idx = pos.get(sum.get(sum.size() - 1) - curr);

int cnt = sum.size() - 1 - idx;

while (cnt-- > 0) {

pos.remove(sum.get(sum.size() - 1));

sum.remove(sum.size() - 1);

}

curr *= 2;

}

sum.add(sum.get(sum.size() - 1) + curr);

pos.put(sum.get(sum.size() - 1), sum.size() - 1);

}

for (int i = sum.size() - 1; i > 0; i--) {

System.out.print(sum.get(i) - sum.get(i - 1) + " ");

}

}

}

Python

from collections import defaultdict

sum = [0]

pos = defaultdict(int)

pos[0] = 0

for x in map(int, input().split()):

curr = x

while sum[-1] - curr in pos:

idx = pos[sum[-1] - curr]

cnt = len(sum) - 1 - idx

while cnt:

pos.pop(sum.pop())

cnt -= 1

curr *= 2

sum.append(sum[-1] + curr)

pos[sum[-1]] = len(sum) - 1

print(' '.join(map(str, (sum[i] - sum[i-1] for i in range(len(sum) - 1, 0, -1)))))

🌭02.K小姐安排座位

题目描述

K小姐是一名列车长，她负责管理一列从北京开往上海的列车。这列火车共有

m

m

m 个座位，途径

n

n

n 个站点（编号从

0

0

0 到

n

−

1

n-1

n−1）。在发车前，已经有

x

x

x 名乘客预定了座位。

为了让列车的运营效率最大化，K小姐需要合理安排乘客的座位。她定义了一个指标叫做"座位利用数"，即每个座位被使用的站数之和。例如，某列车有

2

2

2 个座位，第一个座位从第

0

0

0 站到第

10

10

10 站都有人坐（即从第

0

0

0 站上车，第

10

10

10 站下车，第

10

10

10 站本身不占座，利用数为

10

−

0

=

10

10-0=10

10−0=10），第二个座位从第

1

1

1 站到第

9

9

9 站都有人坐，则总的座位利用数为

(

10

−

0

)

+

(

9

−

1

)

=

18

(10-0)+(9-1)=18

(10−0)+(9−1)=18。

现在，K小姐希望设计一个算法，计算出如何分配座位，才能使得座位利用数最大。同时，她需要保证在任意时刻，列车上的乘客数都不超过座位数

m

m

m。乘客下车后，其他乘客可以立即使用该座位，不用考虑换座的问题。

你能帮助K小姐完成这个任务吗？

输入格式

第一行包含三个正整数

m

,

n

,

x

m,n,x

m,n,x，分别表示列车的座位数、经停站点数和预定乘客数。

接下来

x

x

x 行，每行包含两个整数

u

i

,

v

i

u_i,v_i

ui​,vi​，表示第

i

i

i 位乘客的上车站点编号和下车站点编号。

输出格式

输出一个整数，表示最大的座位利用数。

样例输入

2 11 4

0 1

1 9

0 10

3 8

样例输出

19

数据范围

1

≤

m

≤

9

1 \le m \le 9

1≤m≤9

2

≤

n

≤

20

2 \le n \le 20

2≤n≤20

1

≤

x

≤

9

1 \le x \le 9

1≤x≤9

0

≤

u

i

<

v

i

≤

n

−

1

0 \le u_i < v_i \le n-1

0≤ui​<vi​≤n−1

题解

本题可以使用递归的思路来解决。可以将问题转化为，在当前状态下，对于每个乘客，有两种选择：

不安排该乘客上车，直接考虑下一位乘客。如果当前乘客上车后，车上的乘客数不超过座位数，就安排该乘客上车，并更新座位利用数，然后考虑下一位乘客。

用一个长度为

n

n

n 的数组 curtrain 来表示列车在每一站的乘客数量。对于每个乘客，判断如果他上车后，从他的上车站到下车站的每一站，乘客数是否都不超过座位数

m

m

m，如果是，就可以安排他上车。

递归的终止条件是，当我们考虑完所有乘客后，就可以更新答案，即用当前的座位利用数 curvalue 去更新最大座位利用数 maxval。

时间复杂度为

O

(

2

x

×

n

)

O(2^x \times n)

O(2x×n)，空间复杂度为

O

(

x

+

n

)

O(x+n)

O(x+n)。

参考代码

Cpp

#include <vector>

#include <iostream>

using namespace std;

bool check(vector<int>& train, int max, int l, int r) {

for (int i = l; i < r; i++) {

if (train[i] >= max) {

return false;

}

}

return true;

}

void dfs(vector<vector<int>>& pass, vector<int> train, int value, int& ans, int idx, int m) {

if (idx == pass.size()) {

ans = max(ans, value);

return;

}

int l = pass[idx][0], r = pass[idx][1];

dfs(pass, train, value, ans, idx + 1, m);

if (check(train, m, l, r)) {

for (int i = l; i < r; i++) {

train[i]++;

}

dfs(pass, train, value + r - l, ans, idx + 1, m);

}

}

int main() {

int m, n, x;

cin >> m >> n >> x;

vector<vector<int>> pass(x, vector<int>(2));

for (int i = 0; i < x; i++) {

cin >> pass[i][0] >> pass[i][1];

}

int ans = 0;

vector<int> train(n);

dfs(pass, train, 0, ans, 0, m);

cout << ans << endl;

return 0;

}

Java

import java.util.Scanner;

public class Main {

static boolean check(int[] train, int max, int l, int r) {

for (int i = l; i < r; i++) {

if (train[i] >= max) {

return false;

}

}

return true;

}

static void dfs(int[][] pass, int[] train, int value, int[] ans, int idx, int m) {

if (idx == pass.length) {

ans[0] = Math.max(ans[0], value);

return;

}

int l = pass[idx][0], r = pass[idx][1];

dfs(pass, train, value, ans, idx + 1, m);

if (check(train, m, l, r)) {

for (int i = l; i < r; i++) {

train[i]++;

}

dfs(pass, train, value + r - l, ans, idx + 1, m);

}

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int m = sc.nextInt(), n = sc.nextInt(), x = sc.nextInt();

int[][] pass = new int[x][2];

for (int i = 0; i < x; i++) {

pass[i][0] = sc.nextInt();

pass[i][1] = sc.nextInt();

}

int[] ans = new int[1];

int[] train = new int[n];

dfs(pass, train, 0, ans, 0, m);

System.out.println(ans[0]);

}

}

Python

def check(train, max_seat, l, r):

for i in range(l, r):

if train[i] >= max_seat:

return False

return True

def dfs(pass_info, train, value, ans, idx, m):

if idx == len(pass_info):

ans[0] = max(ans[0], value)

return

l, r = pass_info[idx]

dfs(pass_info, train, value, ans, idx + 1, m)

if check(train, m, l, r):

for i in range(l, r):

train[i] += 1

dfs(pass_info, train, value + r - l, ans, idx + 1, m)

m, n, x = map(int, input().split())

pass_info = [list(map(int, input().split())) for _ in range(x)]

ans = [0]

train = [0] * n

dfs(pass_info, train, 0, ans, 0, m)

print(ans[0])

🍔 03.K小姐的魔法材料

问题描述

K小姐是一位魔法师，她正在研究一些魔法材料。这些材料之间存在着一些依赖关系，一种材料可以依赖于多种其他材料（不包括自己，被依赖的材料不会重复），一种材料也可以被多种材料所依赖。

在这些依赖关系中，总是存在唯一的循环依赖。K小姐想要找出这个循环依赖，你能帮助她吗？

输入格式

第一行包含一个正整数

N

N

N，表示依赖关系的个数。

接下来

N

N

N 行，每行表示一个依赖关系，包含若干个由空格分隔的正整数。第一个数

n

n

n 表示后面有

n

n

n 个材料，第二个数为材料编号

a

a

a，后面

n

−

1

n-1

n−1 个数为

a

a

a 所依赖的材料编号。任意材料编号

i

i

i 满足

0

<

i

<

10000

0 < i < 10000

0<i<10000。

输出格式

输出一行，包含若干个由空格分隔的正整数，表示找到的循环依赖。从最小的材料编号开始，按照依赖关系顺序输出，以最小的材料编号结束。

样例输入

3

3 1 2 5

3 2 3 4

2 3 1

样例输出

1 2 3 1

数据范围

1

≤

N

≤

10000

1 \le N \le 10000

1≤N≤10000

0

<

i

<

10000

0 < i < 10000

0<i<10000

题解

本题可以使用 DFS 来解决。我们可以建立一个有向图，每个材料为一个节点，如果材料

a

a

a 依赖材料

b

b

b，则在图中添加一条从

a

a

a 到

b

b

b 的有向边。

然后我们从每个节点开始做 DFS，同时维护一个栈，表示当前 DFS 经过的节点。如果我们再次访问到一个已经在栈中的节点，说明找到了一个循环依赖。此时，我们将栈中该节点之后的所有节点弹出，即为找到的循环依赖。

时间复杂度

O

(

N

)

O(N)

O(N)，空间复杂度

O

(

N

)

O(N)

O(N)。其中

N

N

N 为材料的个数。

参考代码

Cpp

#include <iostream>

#include <vector>

#include <stack>

using namespace std;

vector<int> res;

vector<int> ans;

vector<int> graph[10001];

int visited[10001];

bool dfs(int u) {

if (visited[u] == 1) {

if (!res.empty() && find(res.begin(), res.end(), u) != res.end()) {

while (!res.empty() && res.back() != u) {

ans.push_back(res.back());

res.pop_back();

}

ans.push_back(u);

res.pop_back();

return true;

} else {

return false;

}

}

visited[u] = 1;

res.push_back(u);

for (int v : graph[u]) {

if (dfs(v)) {

return true;

}

}

res.pop_back();

return false;

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

for (int i = 0; i < 10001; i++) {

graph[i].clear();

}

int n;

cin >> n;

for (int i = 0; i < n; i++) {

int k, cur;

cin >> k >> cur;

for (int j = 1; j < k; j++) {

int val;

cin >> val;

graph[cur].push_back(val);

}

}

for (int i = 0; i < 10001; i++) {

if (!graph[i].empty()) {

dfs(i);

}

}

int last = ans.back();

while (!ans.empty()) {

cout << ans.back() << " ";

ans.pop_back();

}

cout << last << "\n";

return 0;

}

Java

import java.util.*;

public class Main {

static LinkedList<Integer> res = new LinkedList<>();

static LinkedList<Integer> ans = new LinkedList<>();

static ArrayList<Integer>[] graph = new ArrayList[10001];

static int[] visited = new int[10001];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

for (int i = 0; i < 10001; i++) {

graph[i] = new ArrayList<>();

}

int n = sc.nextInt();

for (int i = 0; i < n; i++) {

int k = sc.nextInt();

int cur = sc.nextInt();

for (int j = 1; j < k; j++) {

graph[cur].add(sc.nextInt());

}

}

for (int i = 0; i < 10001; i++) {

if (!graph[i].isEmpty()) {

dfs(i);

}

}

int last = ans.peekLast();

while (!ans.isEmpty()) {

System.out.print(ans.pollLast() + " ");

}

System.out.println(last);

}

static boolean dfs(int u) {

if (visited[u] == 1) {

if (!res.isEmpty() && res.contains(u)) {

while (!res.isEmpty() && res.peek() != u) {

ans.add(res.pop());

}

ans.add(u);

res.pop();

return true;

} else {

return false;

}

}

visited[u] = 1;

res.push(u);

for (int v : graph[u]) {

if (dfs(v)) {

return true;

}

}

res.pop();

return false;

}

}

Python

class Main:

res = []

ans = []

graph = [[] for _ in range(10001)]

visited = [0] * 10001

@staticmethod

def dfs(u):

if Main.visited[u] == 1:

if Main.res and u in Main.res:

while Main.res and Main.res[-1] != u:

Main.ans.append(Main.res.pop())

Main.ans.append(u)

Main.res.pop()

return True

else:

return False

Main.visited[u] = 1

Main.res.append(u)

for v in Main.graph[u]:

if Main.dfs(v):

return True

Main.res.pop()

return False

@staticmethod

def main():

for i in range(10001):

Main.graph[i] = []

n = int(input())

for _ in range(n):

cur = list(map(int, input().split()))

for val in cur[2:]:

Main.graph[cur[1]].append(val)

for i in range(10001):

if Main.graph[i]:

Main.dfs(i)

last = Main.ans[-1]

while Main.ans:

print(Main.ans.pop(), end=" ")code>

print(last)

if __name__ == "__main__":

Main.main()

🍍 写在最后