华为笔试 华为笔试题 0522
笔试时间:2024年05月22日
历史笔试传送门:2023秋招笔试合集
第一题
题目:获取公共链表片段
给定两个链表,获取两者中相同节点值的最大连续片段。如果没有公共片段,返回-1。
输入描述
第一行表示链表1,第二行表示链表2,每条链表长度不超过20个元素,链表不会为空。
输出描述
公共链表片段。
样例输入
1 2 2 3 9 1 5
9 2 2 3 6 8
样例输出
2 2 3
参考题解
模拟。找到第一个数组的所有子数组,放入哈希表。遍历第二个数组的所有子数组,判断是否存在于哈希表即可。
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <unordered_set> #include <string> int main() { std::string nums1, nums2; std::cin >> nums1 >> nums2; std::unordered_set<std::string> s; int n = nums1.size(), m = nums2.size(); // 找到所有子串并放入集合 for (int i = 0; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { s.insert(nums1.substr(i, j - i + 1)); } } std::string res = ""; // 检查nums2中的子串是否存在于集合中 for (int i = 0; i < m; ++i) { for (int j = i + 1; j <= m; ++j) { std::string sub = nums2.substr(i, j - i + 1); if (s.find(sub) != s.end() && (j + 1 - i) > res.size()) { res = sub; } } } if (!res.empty()) { std::cout << res << std::endl; } else { std::cout << -1 << std::endl; } return 0; }
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.Scanner; import java.util.HashSet; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String nums1 = scanner.nextLine(); String nums2 = scanner.nextLine(); HashSet<String> set = new HashSet<>(); int n = nums1.length(), m = nums2.length(); // 找到所有子串并放入集合 for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { set.add(nums1.substring(i, j + 1)); } } String res = ""; // 检查nums2中的子串是否存在于集合中 for (int i = 0; i < m; i++) { for (int j = i + 1; j <= m; j++) { String sub = nums2.substring(i, j + 1); if (set.contains(sub) && (j + 1 - i) > res.length()) { res = sub; } } } if (!res.isEmpty()) { System.out.println(res); } else { System.out.println(-1); } scanner.close(); } }
Python:[此代码未进行大量数据的测试,仅供参考]
nums1 = input() nums2 = input() # 找到最长公共子数组 s = set() n,m = len(nums1),len(nums2) for i in range(n): for j in range(i+1,n+1): s.add(nums1[i:j+1]) res = "" for i in range(m): for j in range(i+1,m+1): if nums2[i:j+1] in s and j+1-i > len(res): res = nums2[i:j+1] if res: print(res.strip()) else: print(-1)
第二题
题目:矿车运输成本
露天矿采矿作业的特点是规模大,矿石和废料的移动量达到百万吨,运输成本开销较大,需要寻求一种最优的运输路径节省成本。已知矿场可以划分成N*M的网格图,每个网格存在地形的差异,因此通过不同网格时,成本开销存在差异。网格有以下5种类型:
1、标志为'S’的网格为运输起点;
2、标志为'E”的网格时运输终点;
3、标志为'B’的网格为阻塞点,不允许通行;
4、标志为'C'的网格为检查点,矿车在运输路径中,至少需要进入一次检查点。
5、标志为‘数字”的网格,其数字表示经过该网格的成本开销。
运输矿车只能上下左右4个方向运行,不允许斜对角进入其他网格。必要时可重复进入网格。
请根据输入的网格图,寻求一条从S网格到E网格,并且至少经过一次检查点的最低成本运输路径,并输出其成本开销。
输入描述
第一行:网格图的行数N[3,200]和网格图的列数M[3,200],使用空格隔开。
第二行至第N+1行:网格图每一行的元素,可以为'S’,E’,'B',‘C'或者数字[0,100],并且有且仅有一个'S’和一个'E’,同时存在一个或者多个‘C',并依次使用空格隔开。
输出描述
第一行:输出运输最低成本开销。
如果不存在可达通路,请输出-1
样例输入
3 3
S 4 5
7 B 3
C 9 E
样例输出
16
参考题解
逆向思维+迪杰斯特拉。枚举所有的C点,从C点出发跑一次迪杰斯特拉,找到C->S和C->E的最短距离即可。
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <vector> #include <queue> #include <tuple> #include <climits> using namespace std; int n, m; vector<vector<string>> matrix; vector<vector<int>> solve(int st_i, int st_j) { vector<vector<int>> distance(n, vector<int>(m, INT_MAX)); vector<vector<bool>> visited(n, vector<bool>(m, false)); distance[st_i][st_j] = 0; priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> h; h.push(make_tuple(0, st_i, st_j)); while (!h.empty()) { int d, i, j; tie(d, i, j) = h.top(); h.pop(); if (visited[i][j]) continue; visited[i][j] = true; vector<pair<int, int>> directions = {{i+1, j}, {i, j+1}, {i-1, j}, {i, j-1}}; for (auto [ni, nj] : directions) { if (ni < 0 || nj < 0 || ni >= n || nj >= m || visited[ni][nj] || matrix[ni][nj] == "B") continue; int w = 0; if (matrix[ni][nj] == "C" || matrix[ni][nj] == "E" || matrix[ni][nj] == "S") { w = 0; } else { w = stoi(matrix[ni][nj]); } if (distance[ni][nj] > distance[i][j] + w) { distance[ni][nj] = distance[i][j] + w; h.push(make_tuple(distance[ni][nj], ni, nj)); } } } return distance; } int main() { cin >> n >> m; matrix.resize(n, vector<string>(m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> matrix[i][j]; } } vector<pair<int, int>> C; int
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。