操作历史管理器的撤销/重做能力华为OD机试真题 华为OD上机考试真题 4月29号 100分题型华为OD机试真题目录点击查看: 华为OD机试真题题库目录机考题库 算法考点详解题目描述实现一个操作历史管理器使用双向链表存储执行过的操作。支持执行新操作、撤销和重做功能。功能说明:执行操作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撤销当前状态为,空字符串用例3输入execute,insert hello undo redo输出insert hello说明执行insert hello,当前为insert hello撤销当前状态为重做当前为insert hello题解思路模拟这道题可以使用数组模拟链表使用history记录操作序列cur表示当前状态初始设置为-1.对于不同命令的处理如下:执行execte 操作描述删除cur之后的在history的记录将操作添加到history尾部cur1执行undo操作如果cur -1说明当前已经是初始状态无法回退返回undo failed否则更新cur cur - 1即可执行redo操作如果cur history.size()-1, 说明无可重做操作范围redo failed否则更新cur 1按照上述逻辑处理之后如果cur -1, 返回空字符串。当cur ! -1,返回history[cur]即可。c#includeiostream #includevector #includestring #include utility #include sstream #includealgorithm #includecmath #includemap using namespace std; // 通用 切割函数 函数 将字符串str根据delimiter进行切割 vectorstring split(const string str, const string delimiter) { vectorstring 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(vectorvectorstring commands) { if (commands.empty()) { return ; } vectorstring 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() { vectorstring inputs; string input; while (getline(cin, input)) { inputs.push_back(input); } vectorvectorstring commands; for(int i 0; i inputs.size(); i) { commands.push_back(split(inputs[i], ,)); } string res executeCommand(commands); cout res; return 0; }JAVAimport java.util.*; import java.io.*; public class Main { // 执行命令 public static String executeCommand(ListListString commands) { if (commands.size() 0) return ; ListString history new ArrayList(); int cur -1; for (ListString 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)); ListListString commands new ArrayList(); String line; while ((line br.readLine()) ! null line.length() 0) { commands.add(Arrays.asList(line.split(,))); } System.out.print(executeCommand(commands)); } }Pythonimportsys# 执行命令defexecuteCommand(commands):ifnotcommands:returnhistory[]cur-1forcmdincommands:ifnotcmd:continue# executeifcmd[0]execute:# 清除 redowhilelen(history)cur1:history.pop()history.append(cmd[1])cur1# undoelifcmd[0]undo:ifcur-1:returnundo failedcur-1# redoelse:ifcur1len(history):returnredo failedcur1returnifcur-1elsehistory[cur]inputssys.stdin.read().strip().split(\n)commands[line.split(,)forlineininputsifline]print(executeCommand(commands))JavaScriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});// 执行命令functionexecuteCommand(commands){if(commands.length0)return;lethistory[];letcur-1;for(letcmdofcommands){if(!cmd.length)continue;// executeif(cmd[0]execute){// 清除 redo 历史while(history.lengthcur1){history.pop();}history.push(cmd[1]);cur;}// undoelseif(cmd[0]undo){if(cur-1)returnundo failed;cur--;}// redoelse{if(cur1history.length)returnredo failed;cur;}}returncur-1?:history[cur];}letlines[];// readline 逐行读取rl.on(line,(line){if(line.trim().length0){lines.push(line.trim());}});rl.on(close,(){letcommandslines.map(lineline.split(,));console.log(executeCommand(commands));});Gopackagemainimport(bufiofmtosstrings)// 执行命令funcexecuteCommand(commands[][]string)string{iflen(commands)0{return}history:[]string{}cur:-1for_,cmd:rangecommands{iflen(cmd)0{continue}ifcmd[0]execute{// 清除 redoforlen(history)cur1{historyhistory[:len(history)-1]}historyappend(history,cmd[1])cur}elseifcmd[0]undo{ifcur-1{returnundo failed}cur--}else{ifcur1len(history){returnredo failed}cur}}ifcur-1{return}returnhistory[cur]}funcmain(){scanner:bufio.NewScanner(os.Stdin)varcommands[][]stringforscanner.Scan(){line:strings.TrimSpace(scanner.Text())ifline{continue}commandsappend(commands,strings.Split(line,,))}fmt.Print(executeCommand(commands))}C语言#includestdio.h#includestring.h#defineMAXN1000#defineMAXLEN100// 历史记录charhistory[MAXN][MAXLEN];intcur-1;intsize0;// executevoidexecute(char*cmd){// 清除 redowhile(sizecur1){size--;}strcpy(history[cur],cmd);sizecur1;}intmain(){charline[200];char*cmds[10];while(fgets(line,sizeof(line),stdin)){line[strcspn(line,\n)]0;intcnt0;char*pstrtok(line,,);while(p){cmds[cnt]p;pstrtok(NULL,,);}if(cnt0)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(cur1size){printf(redo failed);return0;}cur;}}if(cur-1){printf();}else{printf(%s,history[cur]);}return0;}