目录

题目

思路

Code

题目

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

功能说明:

执行操作（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
输入
execute,insert hello
undo
输出

说明
执行insert hello -> 当前insert hello

撤销，当前状态为"",空字符串
 

思路

“双向链表 + 当前指针” 模拟整个逻辑即可。

首先把“从未执行过任何操作的状态”也当成链表里的一个特殊节点，作为头哨兵：

之后三种操作分别这样处理：

1. execute

• 在当前节点后面插入一个新节点
• 当前指针移动到这个新节点
• 同时要把当前节点后面的旧历史全部断开

2. undo

• 如果当前已经在头哨兵，说明已经是“空状态”，不能再撤销，立即返回 undo failed
• 否则当前指针移动到 prev

3. redo

• 如果当前节点没有 next，说明不存在可重做的操作，立即返回 redo failed
• 否则当前指针移动到 next

Code

import sys


class Node:
    def __init__(self, desc: str = "") -> None:
        self.desc = desc
        self.prev = None
        self.next = None


def solve(text: str) -> str:
    commands = [line.strip() for line in text.splitlines() if line.strip()]

    # 头哨兵表示“尚未执行任何操作”的状态。
    head = Node("")
    current = head

    for command in commands:
        if command.startswith("execute,"):
            desc = command[len("execute,") :]

            # 执行新操作时，要清掉当前节点之后所有可重做历史。
            current.next = None

            new_node = Node(desc)
            new_node.prev = current
            current.next = new_node
            current = new_node

        elif command == "undo":
            # 当前已经处于空状态，再撤销就是失败。
            if current is head:
                return "undo failed"

            current = current.prev

        elif command == "redo":
            # 没有后继节点，说明不存在可重做的操作。
            if current.next is None:
                return "redo failed"

            current = current.next

    # 如果当前回到了头哨兵，题目要求输出空字符串。
    return current.desc


if __name__ == "__main__":
    print(solve(sys.stdin.read()))

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    char *desc;
    struct Node *prev;
    struct Node *next;
} Node;

char *copy_string(const char *s) {
    char *p = (char *)malloc(strlen(s) + 1);
    strcpy(p, s);
    return p;
}

int main() {
    char line[2000];

    // 头哨兵表示“尚未执行任何操作”的状态。
    Node *head = (Node *)malloc(sizeof(Node));
    head->desc = copy_string("");
    head->prev = NULL;
    head->next = NULL;

    Node *current = head;

    while (fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        if (strlen(line) == 0) {
            continue;
        }

        if (strncmp(line, "execute,", 8) == 0) {
            char *desc = line + 8;

            // 执行新操作时，清除当前节点之后的所有重做历史。
            current->next = NULL;

            Node *newNode = (Node *)malloc(sizeof(Node));
            newNode->desc = copy_string(desc);
            newNode->prev = current;
            newNode->next = NULL;
            current->next = newNode;
            current = newNode;

        } else if (strcmp(line, "undo") == 0) {
            // 当前已经在空状态，再撤销则失败。
            if (current == head) {
                printf("undo failed");
                return 0;
            }

            current = current->prev;

        } else if (strcmp(line, "redo") == 0) {
            // 没有后继节点，说明没有可重做的操作。
            if (current->next == NULL) {
                printf("redo failed");
                return 0;
            }

            current = current->next;
        }
    }

    printf("%s", current->desc);
    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

type Node struct {
	desc string
	prev *Node
	next *Node
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	// 头哨兵表示空状态。
	head := &Node{desc: ""}
	current := head

	for scanner.Scan() {
		command := strings.TrimSpace(scanner.Text())
		if command == "" {
			continue
		}

		if strings.HasPrefix(command, "execute,") {
			desc := command[len("execute,"):]

			// 执行新操作时，清除当前节点之后的所有重做历史。
			current.next = nil

			newNode := &Node{
				desc: desc,
				prev: current,
			}
			current.next = newNode
			current = newNode

		} else if command == "undo" {
			// 当前已经在空状态，再撤销则失败。
			if current == head {
				fmt.Print("undo failed")
				return
			}

			current = current.prev

		} else if command == "redo" {
			// 没有后继节点，说明没有可重做的操作。
			if current.next == nil {
				fmt.Print("redo failed")
				return
			}

			current = current.next
		}
	}

	fmt.Print(current.desc)
}

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。