大厂真题 / 蔚来

蔚来 2026-9-4 笔试真题

公式说明：数学公式保留为原始矢量图，避免抓取转换造成变量和约束缺失。

蔚来2026-9-4笔试真题

题解整理了这场考试的完整题解和代码，希望能帮助大家更好地准备后续笔试。

本场考试概述

考试时间 ：2026-9-4 考试岗位 ：通用 难度评级 ：简单偏易 考点分析 ：

1. 第一题：二叉树层序建树 + BFS（难度简单）
1. 第二题：奇偶性分析 + 贪心构造（难度简单）

建议策略 ：

1. 第一题真正的难点不是求深度，而是把 {1,2,3,#,#,4} 这种带 # 占位的层序串还原成树。这里千万别套完全二叉树的下标公式 $原题公式$ 、 $原题公式$ ，空节点会让后面所有位置整体前移，必须用队列一个一个发孩子。
1. 第一题还有一个隐藏的失分点： $原题公式$ 到 $原题公式$ ，输入可能是一条链，递归求深度必爆栈（Python 默认递归上限只有 $原题公式$ ）。老老实实写迭代版 BFS。
1. 第二题看到 $原题公式$ 先别急着两两枚举，先化简：乘积为偶等价于至少一个因子为偶，也就是至少有一个数与 $原题公式$ 同奇偶。条件一化简， $原题公式$ 个数就塌成两类，剩下的是纯贪心。
1. 第二题要求输出方案而不只是数量，别只算完对数就交卷。

第一题：二叉树最大深度

题目描述

给定一棵二叉树，求它的最大深度，即从根节点到最远叶子节点的路径上经过的节点个数。二叉树按层序给出，# 表示空节点。例如 {1,2,3,#,#,4} 对应的二叉树形态如下：

这棵树的最大深度为 $原题公式$ ，对应路径 $原题公式$ 。空树的最大深度为 $原题公式$ 。

输入描述

一行一个字符串 $原题公式$ ，表示二叉树的层序序列。序列被一对花括号包裹，元素之间用逗号分隔，# 表示空节点，序列末尾的空节点被省略，空树写作 {}。二叉树的节点个数 $原题公式$ ，每个节点的权值 $原题公式$ 。

输出描述

输出一个整数，表示这棵二叉树的最大深度。

样例1

输入

{1,2,3,#,#,4}

输出

样例解释 根节点 $原题公式$ 的左孩子是 $原题公式$ 、右孩子是 $原题公式$ ，节点 $原题公式$ 的两个孩子都为空，节点 $原题公式$ 的左孩子是 $原题公式$ 。最长的一条根到叶子的路径是 $原题公式$ ，经过 $原题公式$ 个节点，故最大深度为 $原题公式$ 。

样例2

输入

{}

输出

样例解释 空树没有任何节点，最大深度为 $原题公式$ 。

题解：层序建树 + BFS 逐层扩展

题目问题拆解

给一个层序序列，把二叉树还原出来，再求根到最远叶子的路径上有多少个节点。这是一道难点全在输入解析的树遍历题：求深度只要一趟遍历，真正会翻车的是层序串怎么对应父子关系，以及 $原题公式$ 到 $原题公式$ 时链状树会把递归压爆栈。

算法实现

层序序列的约定是：从根开始逐层写下每个位置，# 占位空节点，而只有非空节点才往下发两个元素当它的左右孩子。于是后面每个节点的位置都会因空节点整体前移，解析必须用队列，套不了完全二叉树的下标公式 $原题公式$ 与 $原题公式$ 。序列 {1,#,2,3} 里节点 $原题公式$ 排在第 $原题公式$ 位，它的左孩子 $原题公式$ 紧挨在第 $原题公式$ 位，而下标公式要去第 $原题公式$ 位找，早已越界。算法实现上分两步：第一步，建树。根编号 $原题公式$ 入队，读取指针指向第 $原题公式$ 个元素。每弹出一个节点就连取两个元素当它的左右孩子：是 # 就把这一侧记成 $原题公式$ ，否则新建节点并入队等着领自己的孩子。末尾被省略的空节点表现为元素提前耗尽，循环条件带上指针越界即可。第二步，求深度。仍用队列，但整层整层地弹：先让 $原题公式$ 加一，再固定住此刻的队列长度 $原题公式$ ，把这 $原题公式$ 个节点全弹完并把非空孩子入队，一轮正好走完一层。这里必须迭代而不能递归：输入若是一条左链，递归深度就等于 $原题公式$ ，Python 默认上限 $原题公式$ 会抛 RecursionError，C++ 与 Java 同样爆栈。空树 {} 一个元素都不剩，直接输出 $原题公式$ 。

时空复杂度分析

时间复杂度 ： $原题公式$ 。建树时每个元素只被扫一次，求深度时每个节点只进出队列一次。瓶颈在读入本身，序列长度与节点数同阶， $原题公式$ 已是下界。 空间复杂度 ： $原题公式$ 。左右孩子表各 $原题公式$ 项，队列最多同时装下最宽的一层，仍是 $原题公式$ 。 Python

# 二叉树最大深度 - 层序建树 + BFS 逐层扩展
from collections import deque


def build_tree(s):
    """把层序序列还原成左右孩子表，返回 (左孩子表, 右孩子表, 节点总数)。"""
    body = s.strip()
    # 去掉包裹整个序列的一对花括号，剩下的才是逗号分隔的元素
    if body.startswith("{"):
        body = body[1:-1]
    # 空树写作 {}，去掉花括号后什么都不剩
    if not body:
        return [], [], 0

    tokens = body.split(",")
    # left_son[u] / right_son[u] 存孩子编号，-1 表示这一侧是空的
    # 根节点固定编号 0，之后节点的编号按它在层序里出场的先后依次递增
    left_son = [-1]
    right_son = [-1]
    # 队列里放"已经建好、但还没领到孩子"的节点，层序序列正是按这个顺序把孩子发下来的
    q = deque([0])
    # 0 号 token 已经用作根节点，孩子从 1 号 token 开始往下发
    i = 1
    while q and i < len(tokens):
        u = q.popleft()
        # 只有非空节点才会消耗两个 token 当它的左右孩子，这是层序序列的关键约定
        for side in range(2):
            if i >= len(tokens):
                break
            token = tokens[i]
            i += 1
            # '#' 只是占位的空孩子，不产生新节点，也不会往下发孩子
            if token == "#":
                continue
            # 新节点的编号就是当前已建节点数，正好与它的出场顺序一致
            v = len(left_son)
            left_son.append(-1)
            right_son.append(-1)
            if side == 0:
                left_son[u] = v
            else:
                right_son[u] = v
            q.append(v)
    return left_son, right_son, len(left_son)


def max_depth(left_son, right_son, n):
    """从根出发按层扩展，一共走过多少层就是最大深度。"""
    # 空树一层都没有，深度是 0
    if n == 0:
        return 0
    depth = 0
    # 从根出发，队列里始终装着"下一层要展开的节点"
    q = deque([0])
    # 用队列迭代而不是递归：链状树深度可达 10^5，递归必爆栈
    while q:
        depth += 1
        # 先固定住当前层的节点数，把这些全弹完才算走完一层
        for _ in range(len(q)):
            u = q.popleft()
            if left_son[u] != -1:
                q.append(left_son[u])
            if right_son[u] != -1:
                q.append(right_son[u])
    return depth


# 整棵树压在一行里，可能有几十万字符，一次性读入整行
s = input()
# 先把序列还原成树，再在树上求深度，两步各管一件事
lson, rson, total = build_tree(s)
print(max_depth(lson, rson, total))

第二题：偶数配对

题目描述

AK机有一个长度为 $原题公式$ 的整数数组 $原题公式$ 和一个整数 $原题公式$ 。她想让数组 $原题公式$ 里的元素进行配对，配对的两个数 $原题公式$ 需要满足 $原题公式$ 是偶数。数组 $原题公式$ 的每个元素最多配对一次。 AK机想要尽可能多的配对，你能帮帮她吗？

输入描述

第一行两个整数 $原题公式$ 。第二行 $原题公式$ 个整数 $原题公式$ 。

输出描述

第一行先输出一个整数 $原题公式$ ，表示最大的配对数。接下来 $原题公式$ 行，每行两个整数，表示配对的两个数。答案可以按任意顺序输出。如果有多解，输出任意一解即可通过。

样例1

输入

7 5
1 5 4 4 3 6 3

输出

样例解释 $原题公式$ 是奇数。 $原题公式$ 是奇数、 $原题公式$ 是偶数，乘积 $原题公式$ 是偶数，所以 $原题公式$ 可以配对；同理 $原题公式$ 与 $原题公式$ 也都合法。这三对用掉了 $原题公式$ 共 $原题公式$ 个元素，只剩下 $原题公式$ 无法再配，因此最大配对数为 $原题公式$ 。

题解：奇偶分类贪心

题目问题拆解

从数组里挑出尽量多的元素对，每个元素至多用一次，每一对 $原题公式$ 要满足 $原题公式$ 为偶数，并把方案打印出来。这是一道把条件翻译成奇偶性之后就地化简的贪心题：难点不在配对本身，而在看出合法性只取决于元素与 $原题公式$ 是否同奇偶，从而把 $原题公式$ 个数压成两类。

算法实现

先化简条件。乘积为偶等价于两个因子里至少有一个是偶数，而 $原题公式$ 为偶等价于 $原题公式$ 与 $原题公式$ 同奇偶： $原题公式$ 或同奇偶指两数同为奇数或同为偶数。于是把与 $原题公式$ 同奇偶的元素叫好数、记 $原题公式$ 个，其余叫坏数、记 $原题公式$ 个。一对合法当且仅当里面至少有一个好数；坏数配坏数时两个因子全是奇数，乘积必为奇数，永远不合法。再看最多能配几对。每一对至少吃掉一个好数，故对数不超过 $原题公式$ ；每一对吃两个元素，故对数又不超过 $原题公式$ 。两条上界合起来： $原题公式$ 这个上界能取到，让好数先去带坏数即可：先配 $原题公式$ 对，剩下的好数彼此再两两成对。 $原题公式$ 时总数是 $原题公式$ ； $原题公式$ 时好数全部用来带坏数、得 $原题公式$ 对。两种情形都恰好顶到上界，贪心因此最优。落到实现上只需一趟扫描：按 $原题公式$ 把元素分进好数表与坏数表，前 $原题公式$ 个好数与同样多的坏数一一成对，好数表剩下的部分按相邻下标两两成对。输出的是元素值而不是下标，重复值也不影响，因为每个元素只被放进一张表一次。 $原题公式$ 时两轮循环一对都产生不了，输出 $原题公式$ 与空方案，正是答案。

时空复杂度分析

时间复杂度 ： $原题公式$ 。分类扫一趟，两轮配对合计不超过 $原题公式$ 次。瓶颈在读入这 $原题公式$ 个数本身， $原题公式$ 已是下界。 空间复杂度 ： $原题公式$ 。好数表与坏数表合起来正好装下全部 $原题公式$ 个元素，答案最多 $原题公式$ 对。 Python

# 偶数配对 - 奇偶分类贪心


def split_by_parity(a, k):
    """把元素分成好数与坏数：好数满足 x+k 为偶数，即 x 与 k 同奇偶"""
    good = []
    bad = []
    # (x+k) 的奇偶只由 x 与 k 的奇偶决定，取模判一次就能定类，不必真去做加法
    for x in a:
        if (x + k) % 2 == 0:
            good.append(x)
        else:
            bad.append(x)
    return good, bad


def match_pairs(good, bad):
    """(x+k)(y+k) 为偶等价于两数至少有一个是好数，据此贪心配对"""
    pairs = []
    # 每一对至少吃掉一个好数，故对数不超过好数个数，下面的构造正好顶到这个上界
    # 坏数配坏数永远是奇数乘奇数，只能靠好数带，所以先一对一带走尽量多的坏数
    t = min(len(good), len(bad))
    for i in range(t):
        pairs.append((good[i], bad[i]))
    # 好数彼此就能配对，把带完坏数后剩下的好数两两一组，一个都不浪费
    rest = good[t:]
    # 剩余好数为奇数个时最后一个会落单，步长 2 的循环条件自然把它跳过
    for i in range(0, len(rest) - 1, 2):
        pairs.append((rest[i], rest[i + 1]))
    return pairs


# 读入数组长度、参数 k 与整个数组
n, k = map(int, input().split())
a = list(map(int, input().split()))

# 先按奇偶分类，再在两张表上贪心配对，两步各管一件事
good, bad = split_by_parity(a, k)
pairs = match_pairs(good, bad)

# 先输出对数，再逐行输出每一对的两个元素值（不是下标）
print(len(pairs))
for x, y in pairs:
    print(x, y)

这篇文章有帮助吗？

| GitHub 留言