2020.05.11 字节跳动笔试题目:记事本程序

都5月份了，意外收到字节跳动的笔试链接，今天上午十点到十二点的笔试。

四个编程题目，换句话说就是考算法吧，一点不出意外的我只做出来一个题，另外三个题几乎都没时间看，实不相瞒做出一个题我都很激动了……第二个题目大概看了下，很显然的动态规划的题目，给我两个小时也不一定能做出来的那种……

啊啊啊，我真菜……😭

题目

忘了截图，题目大概是这样的~

一个记事本程序，里面的内容用字符串 S 表示。

可以执行以下四种命令：

• 1 W：表示添加字符串 W 到字符串 S 的末尾；
• 2 k：表示删除字符串 S 末尾的 k 个字符；
• 3 k：表示输出字符串 S 的第 k 个字符；
• 4：回滚上一步对字符串 S 的操作，操作 3 并没有对字符串进行更改，所以只回滚1、2两种操作。

输入规范：

• 第一行输入一个整数 N ，表示总共有多少步操作；
• 从第二行开始输入每一步具体的命令。

示例：

8
1 abc
3 3
2 3
1 xy
3 2
4 
4 
3 1

输出说明：

输出：

c
y
a

说明：

1 abc // 字符串S默认初始为空""，第一步插入"abc"后S变为"abc"
3 3 // 输出S的第三个字符，即输出'c'
2 3 // 删除字符串S的末尾3个字符，删除后S变为""
1 xy // 在字符串S末尾插入"xy"，插入后S为"xy"
3 2 // 输出字符串S的第二个字符，即输出'y'
4 // 回滚，即回滚对"xy"的插入，回滚后S为""
4 // 回滚，即回滚对字符串S末尾3个字符的删除操作，回滚后S为"abc"
3 1 // 输出字符串S的第一个字符，即输出'a'

解题思路

毕竟是笔试啊，有点慌。因为需要对一些操作步骤进行回滚，一开始我想着应该要把操作的步骤记录下来，所以我定义了一个 vector<pair<int, string>> 类型的数组用于保存输入的每一步命令，每个命令保存为 int 类型的整数，参数保存为 string 类型的字符串，主要是为了兼容不同的参数，如果是命令 4 则将其参数保存为空字符串 "" 。

最初的想法是遍历保存下来的命令数组一步一步执行就好了，但是到处理命令 4 的操作时就遇到问题了，感觉处理回滚操作很麻烦，同时觉得回滚这个操作完全就是回溯法相同的模式，想了想觉得应该可行，就改用了回溯法来执行每一步命令。

定义回溯函数 void execute(string S,vector<pair<int, string>>& vec, int& seq, bool& rollback) ，字符串 S 即题目中所述的字符串，数组 vec 即保存下来的命令数组，seq 为当前命令执行到的位置，回滚操作需要记录当前命令执行到的位置，所以 seq 采用引用传参的方式，布尔型的 rollback 用于判断当前命令是回滚操作还是正常的顺序执行。

seq 是递增的，当所有命令都执行完毕后 seq == vec.size() ，此时已经没有可执行的命令，退出回溯函数。

默认要执行当前的命令，对于命令1、2、3，当前命令执行完毕后，只需要将 seq + 1，递归执行下一条命令。对于命令4，回滚操作，对于回溯法来说也就是 return 就可以了，但也需要将 seq + 1，即当前回滚命令已执行。

具体的回滚操作需要交给具体的某一步操作去执行，对于命令3，不需要做任何处理，继续往上回溯，对于命令1、2，在执行递归的下一行，判断 rollback == true 则表明在后续命令中遇到了回滚操作，这里就需要进行回滚处理，对于命令1来说，即删除原本插入的字符串；对于命令2来说即恢复原本删除的字符串。回滚操作完毕需要将 rollback 重新置为 false 。

处理完回滚操作后，还需要继续顺序执行剩下的命令，我用一个 do {...}while(...) 循环来模拟递归执行命令的操作，也就是让命令的执行恢复到顺序执行。

代码

#include <iostream>
#include <vector>
using namespace std;

void execute(string S, vector<pair<int, string>>& vec, int& seq, bool& rollback) {
	if (seq == vec.size()) return;
	do {
		string str = vec[seq].second;//命令参数
		int k = 0;//将字符串参数vec[seq].second转换为整数k
		if (vec[seq].first == 2 || vec[seq].first == 3) {
			for (int i = 0; i < str.size(); i++) {
				k = k * 10 + (str[i] - '0');
			}
		}
		switch (vec[seq].first)
		{
		case 1:
			S += str;//末尾插入字符串str
			seq += 1;
			execute(S, vec, seq, rollback);
			if (rollback == true) {
				//回滚
				S.erase(S.begin() + S.size() - str.size(), S.end());//撤销插入
				rollback = false;
			}
			break;
		case 2: {
			string tmp = S.substr(S.size() - k, k);//临时记录要删除的k个字符
			S.erase(S.begin() + S.size() - k, S.end());//删除末尾k个字符
			seq += 1;
			execute(S, vec, seq, rollback);
			if (rollback == true) {
				//回滚
				S += tmp;//插销删除
				rollback = false;
			}
			break;
		}
		case 3:
			cout << S[k - 1] << endl;//输出第k个字符
			seq += 1;
			execute(S, vec, seq, rollback);
			if (rollback == true) return;//不处理回滚操作
			break;
		case 4:
			rollback = true;//回滚
			seq += 1;
			return;
		default:
			break;
		}
	} while (seq < vec.size());
}

int main() {
	string S = "";
	int N;//要执行的命令数
	cin >> N;
	vector<pair<int, string>> vec;//输入命令
	for (int i = 0; i < N; i++) {
		int seq;
		string str = "";
		cin >> seq;
		if (seq != 4) {
			cin >> str;
		}
		vec.push_back({ seq, str });
	}
	bool rollback = false;//是否回滚命令
	int q = 0;//命令序号
	execute(S, vec, q, rollback);//执行命令vec[q]，该命令不是回滚命令
	return 0;
}