昨天 21:18 香港大学推荐算法发布于上海

关注

华为笔试华为笔试题华为秋招 1029

笔试时间：2025年10月29日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：二叉树最长严格交替路径

给定一棵二叉树的根节点 root 和一个整数 k，定义一条严格交替路径如下：

路径方向：只能从父节点向子节点方向延伸（即路径必须自上而下）。
严格交替条件：路径中相邻节点的值必须交替递增和递减。例如，路径可以是 3 → 7 → 5 → 9（即 3 < 7 > 5 < 9）。
差值限制：每一步的绝对差值必须严格大于等于 k。例如，若 k = 2，则 3 → 7 是合法的（差值为 |7 - 3| = 4 ≥ 2），但 3 → 4 不合法（差值为 |4 - 3| = 1 < 2）。
"先减小后增加"和"先增加后减少"都算交替。

请编写一个函数，返回这棵二叉树中最长严格交替路径的长度。路径长度定义为路径中节点的数量。

输入描述

第 1 行：N K

N 为树的元素数量，范围为 [1, 10000]
K 为阈值，范围为 [1, 100]

第 2 到第 N + 1 行：按 X Y Z 表示一个二叉树节点和子节点的关系，其中：

X 为父节点
Y 为左节点
Z 为右节点
缺失的叶子节点用 -1 表示
树的节点值 X, Y, Z 的取值范围为 [1, 100000]，且元素的值不重复
输入顺序为树的先序遍历顺序

输出描述

输出一个整数，表示最长严格交替路径的长度。

样例输入

6 10

20 10 -1

10 21 -1

21 -1 11

11 -1 22

22 12 -1

12 -1 -1

样例输出

6

解释：

满足条件的最长严格交替路径为：20 → 10 → 21 → 11 → 22 → 12

路径长度为 6。

参考题解

解题思路：

使用树形动态规划（树形DP）结合深度优先搜索（DFS）来解决此题。

核心思想：

对于每个节点，我们需要知道以它为起点的两条路径：

递增路径：从该节点开始，下一步是递增的路径
递减路径：从该节点开始，下一步是递减的路径

递归定义：

设 dfs(node) 返回一个元组 (inc, dec)：

inc：以当前节点为起点，下一步是递增的最长交替路径长度
dec：以当前节点为起点，下一步是递减的最长交替路径长度

状态转移：

对于当前节点 n 和它的子节点 child：

如果当前节点值 < 子节点值（递增关系）：且差值 ≥ k：可以用子节点的递减路径来延长当前节点的递增路径即：inc = max(inc, 1 + child_dec)
如果当前节点值 > 子节点值（递减关系）：且差值 ≥ k：可以用子节点的递增路径来延长当前节点的递减路径即：dec = max(dec, 1 + child_inc)

路径长度的计算：

路径长度就是路径中的节点数。对于单个节点，路径长度至少为1。

全局最大值：

在递归过程中，用全局变量记录遇到的所有 inc 和 dec 的最大值。

时间复杂度：O(N)

空间复杂度：O(N)

C++：

#include <iostream>
#include <unordered_map>
#include <sstream>
#include <algorithm>
#include <vector>
using namespace std;

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

int maxLen = 0;

TreeNode* buildTree(int n) {
    if (n == 0) return nullptr;
    
    unordered_map<int, TreeNode*> nodes;
    int rootVal = -1;
    
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        
        if (i == 0) rootVal = x;
        
        if (nodes.find(x) == nodes.end()) {
            nodes[x] = new TreeNode(x);
        }
        TreeNode* parent = nodes[x];
        
        if (y != -1) {
            if (nodes.find(y) == nodes.end()) {
                nodes[y] = new TreeNode(y);
            }
            parent->left = nodes[y];
        }
        
        if (z != -1) {
            if (nodes.find(z) == nodes.end()) {
                nodes[z] = new TreeNode(z);
            }
            parent->right = nodes[z];
        }
    }
    
    return nodes[rootVal];
}

pair<int, int> dfs(TreeNode* node, int k) {
    if (!node) return {0, 0};
    
    int maxInc = 1;
    int maxDec = 1;
    
    if (node->left) {
        auto [leftInc, leftDec] = dfs(node->left, k);
        
        if (node->val < node->left->val && abs(node->val - node->left->val) >= k) {
            maxInc = max(maxInc, 1 + leftDec);
        } else if (node->val > node->left->val && abs(node->val - node->left->val) >= k) {
            maxDec = max(maxDec, 1 + leftInc);
        }
    }
    
    if (node->right) {
        auto [rightInc, rightDec] = dfs(node->right, k);
        
        if (node->val < node->right->val && abs(node->val - node->right->val) >= k) {
            maxInc = max(maxInc, 1 + rightDec);
        } else if (node->val > node->right->val && abs(node->val - node->right->val) >= k) {
            maxDec = max(maxDec, 1 + rightInc);
        }
    }
    
    maxLen = max({maxLen, maxInc, maxDec});
    
    return {maxInc, maxDec};
}

int main() {
    int N, K;
    cin >> N >> K;
    
    TreeNode* root = buildTree(N);
    
    if (root) {
        dfs(root, K);
    }
    
    cout << maxLen << endl;
    
    return 0;
}

Java：

import java.util.*;

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

public class Main {
    static int maxLen = 0;
    
    public static TreeNode buildTree(int n, Scanner sc) {
        if (n == 0) return null;
        
        Map<Integer, TreeNode> nodes = new HashMap<>();
        int rootVal = -1;
        
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            
            if (i == 0) rootVal = x;
            
            if (!nodes.containsKey(x)) {
                nodes.put(x, new TreeNode(x));
            }
            TreeNode parent = nodes.get(x);
            
            if (y != -1) {
                if (!nodes.containsKey(y)) {
                    nodes.put(y, new TreeNode(y));
                }
                parent.left = nodes.get(y);
            }
            
            if (z != -1) {
                if (!nodes.containsKey(z)) {
                    nodes.put(z, new TreeNode(z));
                }
                parent.right = nodes.get(z);
            }
        }
        
        return nodes.get(rootVal);
    }
    
    public static int[] dfs(TreeNode node, int k) {
        if (node == null) return new int[]{0, 0};
        
        int maxInc = 1;
        int maxDec = 1;
        
        if (node.left != null) {
            int[] leftResult = dfs(node.left, k);
            int leftInc = leftResult[0];
            int leftDec = leftResult[1];
            
            if (node.val < node.left.val && Math.abs(node.val - node.left.val) >= k) {
                maxInc = Math.max(maxInc, 1 + leftDec);
            } else if (node.val > node.left.val && Math.abs(node.val - node.left.val) >= k) {
                maxDec = Math.max(maxDec, 1 + leftInc);
            }
        }
        
        if (node.right != null) {
            int[] rightResult = dfs(node.right, k);
            int rightInc = rightResult[0];
            int rightDec = rightResult[1];
            
            if (node.val < node.right.val && Math.abs(node.val - node.right.val) >= k) {
                maxInc = Math.max(maxInc, 1 + rightDec);
            } else if (node.val > node.right.val && Math.abs(node.val - node.right.val) >= k) {
                maxDec = Math.max(maxDec, 1 + rightInc);
            }
        }
        
        maxLen = Math.max(maxLen, Math.max(maxInc, maxDec));
        
        return new int[]{maxInc, maxDec};
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        TreeNode root = buildTree(N, sc);
        
        if (root != null) {
            dfs(root, K);
        }
        
        System.out.println(maxLen);
    }
}

Python：

import sys
sys.setrecursionlimit(20000)

class TreeNode:
    def __init__(self, v=0, l=None, r=None):
        self.v = v
        self.l = l
        self.r = r

def build(n):
    if n == 0:
        return None
    d = {}
    rv = -1
    for i in range(n):
        t = list(map(int, sys.stdin.readline().split()))
        if not t:
            continue
        x, y, z = t
        if i == 0:
            rv = x
        if x not in d:
            d[x] = TreeNode(x)
        p = d[x]
        if y != -1:
            if y not in d:
                d[y] = TreeNode(y)
            p.l = d[y]
        if z != -1:
            if z not in d:
                d[z] = TreeNode(z)
            p.r = d[z]
    return d.get(rv)

m = 0

def dfs(n, k):
    global m
    if not n:
        return (0, 0)
    mi = 1
    md = 1
    if n.l:
        li, ld = dfs(n.l, k)
        if n.v < n.l.v and abs(n.v - n.l.v) >= k:
            mi = max(mi, 1 + ld)
        elif n.v > n.l.v and abs(n.v - n.l.v) >= k:
            md = max(md, 1 + li)
    if n.r:
        ri, rd = dfs(n.r, k)
        if n.v < n.r.v and abs(n.v - n.r.v) >= k:
            mi = max(mi, 1 + rd)
        elif n.v > n.r.v and abs(n.v - n.r.v) >= k:
            md = max(md, 1 + ri)
    m = max(m, mi, md)
    return (mi, md)

N, K = map(int, sys.stdin.readline().split())
rt = build(N)
if rt:
    dfs(rt, K)
print(m)

第二题：新能源汽车最高总续航里程

有从1到 n 按升序编号的 n 辆纯电的新能源汽车，给定一个总的电池容量 k，请根据每辆新能源汽车的电池容量和续航里程情况，选取对应的新能源汽车的组合，满足所选择的组合内的新能源汽车的电池容量总和不大于 k，总续航里程最高。

输入描述

第一行输入为整数 n，表示新能源汽车数量，范围为 [1, 50]；第二行输入为整数 k，表示给定的总的电池容量，范围为 [1, 1000]；接下来的 n 行输入，按照1到 n 按升序编号顺序，逐行表示对应编号的新能源汽车的电池容量和续航里程，以空格分隔；电池容量范围为 [1, 100]，续航里程范围为 [1, 1000]。

输出描述

按照编号从小到大输出所选组合中的新能源汽车编号，编号间以空格隔开。

样例输入

1 80 100 300

样例输出

-1

解释：该用例中不存在电量不大于80的组合，因此返回 -1。

参考题解

解题思路：

这是一个典型的0-1背包问题变种，需要从n辆车中选择若干辆，在总电池容量不超过k的前提下，最大化总续航里程。当里程相同时，优先选择总电量更少的组合；当总电量也相同时，优先选择车辆数量更少的组合。

核心推导过程：

问题转化：每辆车：重量=电池容量，价值=续航里程背包容量=k目标：在不超过背包容量的情况下，最大化总价值（续航里程）
特殊约束处理：当里程相同时，选择总电量更少的组合 → 在价值相同的情况下，选择重量更小的当总电量也相同时，选择车辆数量更少的组合 → 在价值和重量都相同的情况下，选择物品数量更少的
动态规划状态设计：定义 f[j] 表示容量为j时的最优状态每个状态存储四元组：(总里程, 总电量, 车辆数, 车辆编号集合)初始状态：f[0] = (0, 0, 0, ∅)，其他为无效状态 (-1, m+1, n+1, ∅)
状态转移：对于每辆车(容量a, 里程b, 编号idx)从大到小遍历容量j（避免重复选择）如果 f[j-a] 有效，考虑选择当前车辆比较新状态与当前 f[j] 的状态，按照优先级选择更优的
比较规则：第一优先级：里程更高第二优先级：电量更少（里程相同时）第三优先级：车辆数更少（里程和电量都相同时）
结果提取：遍历所有容量下的最优状态找出全局最优解如果没有有效解（里程≤0），输出-1否则输出按编号排序的车辆集合

时间复杂度：O(n × k)

空间复杂度：O(k)

C++：

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

struct State {
    long long range;
    long long capacity;
    int count;
    set<int> cars;
    
    State() : range(-1), capacity(1001), count(51) {}

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

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

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