华为笔试华为笔试题 0507

笔试时间：2025年5月7日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：寻找智能汽车行驶距离最近的K个充电桩

一个超大智能汽车测试场有多个充电桩，每个充电桩的位置由其在二维平面上的坐标 (x, y) 表示。给定一辆智能汽车的当前位置 (car_x, car_y)，请设计一个高效的算法，找出给定智能汽车行驶到充电桩行驶距离最近的k个充电桩并输出相关充电桩信息（编号、坐标、行驶距离），且按行驶距离升序排序（最近行驶距离的排在最前面），如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。汽车到充电桩的行驶距离的计算方法为 abs(car_x - x) + abs(car_y - y) 注意：abs表示绝对值。

输入描述

第一行是2个整数k n，空格间隔，第1个整数k表示需要输出到的行驶距离最近的充电桩的数量（ 0 <= k <= 1000000），第2个整数n表示充电桩的总数量（0 < n <= 1000000）。

第2行是长度为2的整数数组car_x car_y，中间是空格间隔，表示智能汽车的当前位置坐标。

第3行到第n+2行是编号为1到n的充电桩的位置坐标。

注意：坐标数值大小区间为： [-2^32, 2^31-1]

输出描述

一个二维数组，每一行是一个长度为4 的数组：编号 x y distance，编号表示充电桩的编号（介于1到n之间）、x y表示充电桩的坐标, distance表示智能汽车到充电桩的行驶距离，从第1行开始往下是按距离从小到大排序的。如果存在行驶距离相等的充电桩则按照充电桩的编号从小到大输出。如果k为0或者k大于n，输出字符串null。

样例输入

3 5

0 0

1 4

5 6

2 3

7 8

3 -1

样例输出

5 3 -1 4

1 1 4 5

3 2 3 5

解释：到汽车行驶距离最近的三个充电桩的编号分别为5、1、3，充电桩的坐标分别是3 -1、1 4、2 3，到智能汽车坐标[0,0]的行驶距离分别为4、5、5。距离都为5的充电桩1的编号小于编号3的充电桩，输出结果中编号小的在前。

参考题解

数据存储与预处理使用结构体存储每个充电桩的编号、坐标和曼哈顿距离，计算公式为 distance = |car_x - x| + |car_y - y|。所有充电桩信息存入数组，时间复杂度为 *O(n)*。排序策略对充电桩数组进行排序，排序规则为：优先按距离从小到大排序若距离相同，则按编号从小到大排序使用快速排序算法。边界处理若 k=0 或 k>n，直接输出 null；否则截取排序后的前k个元素输出。

C++：

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    vector<string> input;
    string token;
    while (cin >> token) {
        input.push_back(token);
    }
    
    int ptr = 0;
    int k = stoi(input[ptr++]);
    int n = stoi(input[ptr++]);
    
    if (k == 0 || k > n) {
        cout << "null" << endl;
        return 0;
    }
    
    int car_x = stoi(input[ptr++]);
    int car_y = stoi(input[ptr++]);
    
    vector<tuple<int, int, int, int>> chargers;
    for (int i = 0; i < n; i++) {
        int x = stoi(input[ptr++]);
        int y = stoi(input[ptr++]);
        int distance = abs(car_x - x) + abs(car_y - y);
        chargers.push_back(make_tuple(distance, i+1, x, y));
    }
    
    sort(chargers.begin(), chargers.end(), [](const auto& a, const auto& b) {
        if (get<0>(a) != get<0>(b))
            return get<0>(a) < get<0>(b);
        return get<1>(a) < get<1>(b);
    });
    
    for (int i = 0; i < k; i++) {
        auto [d, idx, x, y] = chargers[i];
        cout << idx << " " << x << " " << y << " " << d << endl;
    }
    
    return 0;
}

Java：

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<String> input = new ArrayList<>();
        while (scanner.hasNext()) {
            input.add(scanner.next());
        }
        
        int ptr = 0;
        int k = Integer.parseInt(input.get(ptr++));
        int n = Integer.parseInt(input.get(ptr++));
        
        if (k == 0 || k > n) {
            System.out.println("null");
            return;
        }
        
        int car_x = Integer.parseInt(input.get(ptr++));
        int car_y = Integer.parseInt(input.get(ptr++));
        
        List<Charger> chargers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(input.get(ptr++));
            int y = Integer.parseInt(input.get(ptr++));
            int distance = Math.abs(car_x - x) + Math.abs(car_y - y);
            chargers.add(new Charger(distance, i+1, x, y));
        }
        
        Collections.sort(chargers, (a, b) -> {
            if (a.distance != b.distance)
                return a.distance - b.distance;
            return a.idx - b.idx;
        });
        
        for (int i = 0; i < k; i++) {
            Charger c = chargers.get(i);
            System.out.printf("%d %d %d %d%n", c.idx, c.x, c.y, c.distance);
        }
    }
    
    static class Charger {
        int distance;
        int idx;
        int x;
        int y;
        
        Charger(int distance, int idx, int x, int y) {
            this.distance = distance;
            this.idx = idx;
            this.x = x;
            this.y = y;
        }
    }
}

Python：

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    k = int(input[ptr])
    ptr +=1
    n = int(input[ptr])
    ptr +=1
    
    if k ==0or k > n:
        print("null")
        return
    
    car_x = int(input[ptr])
    ptr +=1
    car_y = int(input[ptr])
    ptr +=1
    
    chargers = []
    for i in range(n):
        x = int(input[ptr])
        ptr +=1
        y = int(input[ptr])
        ptr +=1
        distance = abs(car_x - x) + abs(car_y - y)
        chargers.append( (distance, i+1, x, y) )  # i+1是编号
    
    # 按距离升序，距离相同按编号升序
    chargers.sort(key=lambda x: (x[0], x[1]))
    
    for i in range(k):
        d, idx, x, y = chargers[i]
        print(f"{idx} {x} {y} {d}")

if __name__ == "__main__":
    main()

第二题：建设基站

有一棵二叉树，每个节点上都住了一户居民。现在要给这棵树上的居民建设基站，每个基站只能覆盖她所在与相邻的节点，请问信号覆盖这棵树最少需要建设多少个基站

输入描述

一个整数数组 nums(1<=num.length<=3000)，用空格分隔，表示二叉树的节点值，正整数表示存在节点，N 表示不存在节点，如[1 2 3 4 N 5 6]表示一颗如下所示的树，最少需要建设2个基站

输出描述

最少需要建设的基站个数

样例输入

1 2 3 4 N 5 6

样例输出

2

参考题解

树形dp，步骤如下：构建二叉树：根据输入的层序遍历数组构建二叉树结构。递归处理节点：使用深度优先搜索（DFS）递归处理每个节点，计算其三种状态的最小基站数目。状态转移：状态0：当前节点放置基站，覆盖自身及其子节点。状态1：当前节点未被覆盖，需要父节点覆盖，子节点必须被覆盖。状态2：当前节点被覆盖，未放置基站，覆盖来自子节点。结果计算：根节点的最终结果为状态0和状态2的最小值，确保整棵树被覆盖。

C++：

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(const vector<string>& nums) {
    if (nums.empty()) return nullptr;
    TreeNode* root = new TreeNode(stoi(nums[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < nums.size()) {
        TreeNode* node = q.front(); q.pop();
        if (nums[i] != "N") {
            node->left = new TreeNode(stoi(nums[i]));
            q.push(node->left);
        }
        i++;
        if (i < nums.size() && nums[i] != "N") {
            node->right = new TreeNode(stoi(nums[i]));
            q.push(node->right);
        }
        i++;
    }
    return root;
}

int minStationCover(const vector<string>& nums) {
    const int INF = INT_MAX;

    function<tuple<int, int, int>(TreeNode*)> dfs = [&](TreeNode* node) {
        if (!node) return make_tuple(INF, INF, 0);
        auto [l0, l1, l2] = dfs(node->left);
        auto [r0, r1, r2] = dfs(node->right);

        // 状态0: 当前节点放置基站
        int minL0 = min({l0, l1, l2});
        int minR0 = min({r0, r1, r2});
        int dp0 = 1 + minL0 + minR0;

        // 状态1: 当前节点未被覆盖，父节点必须覆盖
        int dp1 = l2 + r2;

        // 状态2: 当前节点被覆盖，未放置基站，覆盖来自子节点
        int option1 = l0 + min(r0, r2);
        int option2 = r0 + min(l0, l2);
        int option3 = l0 + r0;
        int dp2 = min({option1, option2, option3});

        return make_tuple(dp0, dp1, dp2);
    };

    TreeNode* root = buildTree(nums);
    if (!root) return 0;
    auto [dp0, dp1, dp2] = dfs(root);
    return min(dp0, dp2);
}

int main() {
    vector<string> nums;
    string token;
    while (cin >> token) {
        nums.push_back(token);
    }
    cout << minStationCover(nums) << endl;
    return 0;
}

Java：

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public static TreeNode buildTree(String[] nums) {
        if (nums.length == 0) return null;
        TreeNode root = new TreeNode(Integer.parseInt(nums[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < nums.length) {
            TreeNode node = q.poll();
            if (!nums[i].equals("N")) {
                node.left = new TreeNode(Integer.parseInt(nums[i]));
                q.add(node.left);
            }
            i++;
            if (i < nums.length && !n

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

2025 春招笔试合集文章被收录于专栏

2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南