本文最后更新于:2020年5月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;
}