2026 华为OD机试真题 4月29日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

实现一个操作历史管理器，使用双向链表存储执行过的操作。支持执行新操作、撤销和重做功能。

输入描述

• 执行操作（$execute$ {操作描述}）：执行新操作，并清除当前操作之后的所有历史记录
• 撤销（$undo$）：回退到上一个操作状态（上一个操作状态可以为从未执行过任何操作的状态，若当前状态已经是从未执行过任何操作的状态，则 $undo$ 失败）
• 重做（$redo$）：前进到下一个操作状态（下一个操作状态是之前撤销过的操作，若没有进行过撤销操作（即链表的下一个操作状态不存在），则 $redo$ 失败）

说明

命令只会出现 $execute$ {操作描述}、$undo$、$redo$ 三种类型

输出描述

• 执行完所有命令后，返回当前操作的描述

• 若执行 $undo$ 时，当前状态是从未执行过任何操作的状态，立即返回 "$undo$ $failed$"，不继续执行后续命令。（注意：$undo$ 可以撤销到从未执行过任何操作的状态）

• 若执行 $redo$ 时无下一个操作，立即返回 "$redo$ $failed$"，不继续执行后续命令

• 若当前状态是从未执行过任何操作，当前操作描述为空字符串 ""

示例1

输入

[["execute", "insert hello"], ["execute", "newline"], ["execute", "insert woo"], ["undo"], ["execute", "insert world"], ["undo"]]

输出

"newline"

说明

• 执行 $insert$ $hello$ $→$ 当前：$insert$ $hello$

• 执行 $newline$ $→$ 当前：$newline$

• 执行 $insert$ $woo$ $→$ 当前：$insert$ $woo$

• 撤销 $→$ 当前：$newline$（当前回滚到上一步的状态）

• 执行 $insert$ $world$ $→$ 当前：$insert$ $world$（清除任何后续历史）

• 撤销 $→$ 当前：$newline$

示例2

输入

[[]]

输出

""

说明

当前状态是从未执行过任何操作，输出: ""

示例3

输入

[["execute", "insert hello"], ["undo"]]

输出

""

说明

• 执行 $insert$ $hello$ $→$ 当前：$insert$ $hello$

• 撤销 $→$ 当前：""（当前状态是从未执行过任何操作，输出: ""）

示例4

输入

[["execute","insert hello"],["undo"],["redo"]]

输出

"insert hello"

说明

• 执行 $insert$ $hello$ $→$ 当前：$insert$ $hello$

• 撤销 $→$ 当前：""

• 重做 $→$ 当前：$insert$ $hello$

解题思路

核心思想

本题要求实现一个操作历史管理器，核心在于维护一个操作序列和一个指向当前操作的指针（游标）。

1. 存储结构：可以使用动态数组（如 Java 的 ArrayList、Python 的 list）或双向链表来存储执行过的操作描述。
2. 指针维护：使用一个整数变量 cur 表示当前所处的操作索引。初始状态下，没有任何操作，cur = -1。
3. 操作处理：
   • execute {op}：
     • 首先需要清空当前指针 cur 之后的所有历史记录（因为新操作会覆盖掉撤销后的重做路径）。
     • 将新操作添加到序列末尾。
     • 将指针 cur 指向序列的最后一个元素。
   • undo：
     • 如果 cur == -1，说明已经回退到初始状态，无法再撤销，返回 "undo failed"。
     • 否则，将 cur 减 1。
   • redo：
     • 如果 cur 已经指向序列的最后一个元素，说明没有可以重做的操作，返回 "redo failed"。
     • 否则，将 cur 加 1。
4. 结果返回：
   • 遍历完所有指令后，根据 cur 的值返回对应的操作描述。如果 cur == -1，返回空字符串 ""。

复杂度分析

• 时间复杂度：$O(N \times M)$，其中 $N$ 是命令的数量，$M$ 是每次 execute 时清空后续历史的开销。在最坏情况下，如果频繁在中间位置执行 execute，清空操作可能达到 $O(N)$。不过在实际应用中，如果使用链表或者仅移动尾部索引，可以优化到 $O(1)$。
• 空间复杂度：$O(N \times L)$，其中 $N$ 是执行的操作数量，$L$ 是操作描述字符串的平均长度。我们需要存储所有的历史操作。