华为OD新系统机试真题 - 操作历史管理器的撤销/重做能力

操作历史管理器的撤销/重做能力

华为OD机试真题 华为OD上机考试真题 4月29号 100分题型

华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解

题目描述

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

功能说明:

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

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

输入描述

每一行输出一个命令

输出描述

1. 执行完所有命令后，返回当前操作的描述
2. 若执行 undo时，当前状态是从未执行过任何操作的状态，立即返回 “undo failed”，不继续执行后续命令。（注意：undo可以撤销到从未执行过任何操作的状态）
3. 若执行 redo 时无下一个操作，立即返回 “redo failed”，不继续执行后续命令
4. 若当前状态是从未执行过任何操作，当前操作描述为空字符串 “”

用例1

输入

execute,insert hello execute,newline execute,insert woo undo execute,insert world undo

输出

newline

说明

1. 执行insert hello ->当前insert hello
2. 执行newline -> 当前newline
3. 执行insert woo -> 当前 insert woo
4. 撤销 -> 当前newline
5. 执行insert world -> 当前insert world
6. 撤销 -> 当前newline

用例2

输入

execute,insert hello undo

输出

说明

执行insert hello -> 当前insert hello

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

用例3

输入

execute,insert hello undo redo

输出

insert hello

说明

1. 执行insert hello,当前为insert hello
2. 撤销，当前状态为""
3. 重做，当前为insert hello

题解

思路：模拟

1. 这道题可以使用数组模拟链表，使用history记录操作序列，cur表示当前状态，初始设置为-1.
2. 对于不同命令的处理如下:
   • 执行execte 操作描述：
     • 删除cur之后的在history的记录
     • 将操作添加到history尾部
     • cur+1
   • 执行undo操作
     • 如果cur == -1，说明当前已经是初始状态，无法回退，返回undo failed
     • 否则更新cur = cur - 1即可
   • 执行redo操作
     • 如果cur == history.size()-1, 说明无可重做操作，范围redo failed
     • 否则更新cur += 1
3. 按照上述逻辑处理之后，如果cur == -1, 返回空字符串。当cur != -1,返回history[cur]即可。

c++

#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vector<string> split(const string& str, const string& delimiter) { vector<string> result; size_t start = 0; size_t end = str.find(delimiter); while (end != string::npos) { result.push_back(str.substr(start, end - start)); start = end + delimiter.length(); end = str.find(delimiter, start); } // 添加最后一个部分 result.push_back(str.substr(start)); return result; } string executeCommand(vector<vector<string>>& commands) { if (commands.empty()) { return ""; } vector<string> history; int cur = -1; for (auto& command : commands) { if (command.empty()) { continue; } if (command[0] == "execute") { // 清除之后的历史记录 while (history.size() > cur + 1) { history.pop_back(); } history.push_back(command[1]); cur++; } else if (command[0] == "undo") { if (cur == -1) { return "undo failed"; } cur -= 1; } else { if (cur + 1 >= history.size()) { return "redo failed"; } cur++; } } if (cur == -1) { return ""; } return history[cur]; } int main() { vector<string> inputs; string input; while (getline(cin, input)) { inputs.push_back(input); } vector<vector<string>> commands; for(int i = 0; i < inputs.size(); i++) { commands.push_back(split(inputs[i], ",")); } string res = executeCommand(commands); cout << res; return 0; }

JAVA

import java.util.*; import java.io.*; public class Main { // 执行命令 public static String executeCommand(List<List<String>> commands) { if (commands.size() == 0) return ""; List<String> history = new ArrayList<>(); int cur = -1; for (List<String> command : commands) { if (command.size() == 0) continue; String op = command.get(0); // execute if (op.equals("execute")) { // 清除 redo 历史 while (history.size() > cur + 1) { history.remove(history.size() - 1); } history.add(command.get(1)); cur++; } // undo else if (op.equals("undo")) { if (cur == -1) return "undo failed"; cur--; } // redo else { if (cur + 1 >= history.size()) return "redo failed"; cur++; } } if (cur == -1) return ""; return history.get(cur); } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); List<List<String>> commands = new ArrayList<>(); String line; while ((line = br.readLine()) != null && line.length() > 0) { commands.add(Arrays.asList(line.split(","))); } System.out.print(executeCommand(commands)); } }

Python

importsys# 执行命令defexecuteCommand(commands):ifnotcommands:return""history=[]cur=-1forcmdincommands:ifnotcmd:continue# executeifcmd[0]=="execute":# 清除 redowhilelen(history)>cur+1:history.pop()history.append(cmd[1])cur+=1# undoelifcmd[0]=="undo":ifcur==-1:return"undo failed"cur-=1# redoelse:ifcur+1>=len(history):return"redo failed"cur+=1return""ifcur==-1elsehistory[cur]inputs=sys.stdin.read().strip().split("\n")commands=[line.split(",")forlineininputsifline]print(executeCommand(commands))

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});// 执行命令functionexecuteCommand(commands){if(commands.length===0)return"";lethistory=[];letcur=-1;for(letcmdofcommands){if(!cmd.length)continue;// executeif(cmd[0]==="execute"){// 清除 redo 历史while(history.length>cur+1){history.pop();}history.push(cmd[1]);cur++;}// undoelseif(cmd[0]==="undo"){if(cur===-1)return"undo failed";cur--;}// redoelse{if(cur+1>=history.length)return"redo failed";cur++;}}returncur===-1?"":history[cur];}letlines=[];// readline 逐行读取rl.on('line',(line)=>{if(line.trim().length>0){lines.push(line.trim());}});rl.on('close',()=>{letcommands=lines.map(line=>line.split(','));console.log(executeCommand(commands));});

Go

packagemainimport("bufio""fmt""os""strings")// 执行命令funcexecuteCommand(commands[][]string)string{iflen(commands)==0{return""}history:=[]string{}cur:=-1for_,cmd:=rangecommands{iflen(cmd)==0{continue}ifcmd[0]=="execute"{// 清除 redoforlen(history)>cur+1{history=history[:len(history)-1]}history=append(history,cmd[1])cur++}elseifcmd[0]=="undo"{ifcur==-1{return"undo failed"}cur--}else{ifcur+1>=len(history){return"redo failed"}cur++}}ifcur==-1{return""}returnhistory[cur]}funcmain(){scanner:=bufio.NewScanner(os.Stdin)varcommands[][]stringforscanner.Scan(){line:=strings.TrimSpace(scanner.Text())ifline==""{continue}commands=append(commands,strings.Split(line,","))}fmt.Print(executeCommand(commands))}

C语言

#include<stdio.h>#include<string.h>#defineMAXN1000#defineMAXLEN100// 历史记录charhistory[MAXN][MAXLEN];intcur=-1;intsize=0;// executevoidexecute(char*cmd){// 清除 redowhile(size>cur+1){size--;}strcpy(history[++cur],cmd);size=cur+1;}intmain(){charline[200];char*cmds[10];while(fgets(line,sizeof(line),stdin)){line[strcspn(line,"\n")]=0;intcnt=0;char*p=strtok(line,",");while(p){cmds[cnt++]=p;p=strtok(NULL,",");}if(cnt==0)continue;// executeif(strcmp(cmds[0],"execute")==0){execute(cmds[1]);}// undoelseif(strcmp(cmds[0],"undo")==0){if(cur==-1){printf("undo failed");return0;}cur--;}// redoelse{if(cur+1>=size){printf("redo failed");return0;}cur++;}}if(cur==-1){printf("");}else{printf("%s",history[cur]);}return0;}