阅读量:2
🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员
✨ 本系列打算持续跟新华为近期的春秋招笔试题汇总～
💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。
💻 前言
🍭 关于华为
- 据说今晚有华为的机试啦，华为的春招也算是正式开始了，关于华为的笔试，大家可以自由选时间去安排，大致时间就是每周三，具体哪一周需要自己去做决定，和 HR 沟通或者邮件📧反馈，一般会有 HR 联系你修改信息，包括后面笔试的成绩，也可以问 HR ，华为的 HR 是真滴很不错 👍
📓 笔试要求
- 华为的笔试有个硬性规定，笔试分是需要达到 150/600 分才算是通过，三道题目的构成分数构成为
100，200，300分，后续的面试流程会根据笔试成绩来进行排序哦。
🪜 笔试技巧
笔试的思维破局
- 之前写别的公司机试的小伙伴一般都是按照顺序来写的，因为越往后的题目难度越高，这样会形成一个惯性，做每家公司的笔试都这么干。
- 但华为题目的代码编写难易度并不一定是递进的，比如
第一题可能是题意很简单，但是码量很大。第三题可能代码随便写几行就能拿到很多分，大家在机试的时候需要把把握好做题的顺序，每道题可以都先过一遍。
骗分技巧
- 适当使用暴力骗分，如果对于当前这题没有什么想法，不要多想直接写暴力或许能拿到不少的分数。
- 对于题目要求输出
YesorNo，或者无解输出-1的情况，那么可以试试直接输出，一般也能拿到一些分数 - 这里捞一点那里骗一点，说不定就够
150分了哦
🥰 题目练手
那么本次就给大家带来今年春招提前批的华为的真题练练手，祝大家今晚发挥超长，笔试 AK ！！ ！！
文章目录
_________________________________________
✈️ 笔试题目
🍟 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=" ") print(last) if __name__ == "__main__": Main.main() 🍍 写在最后
📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。
