小C的记事本(模拟)
小C的记事本
https://ac.nowcoder.com/acm/problem/15975
题目描述
小C最近学会了java小程序的开发，他很开心，于是想做一个简单的记事本程序练练手。
他希望他的记事本包含以下功能：
1、append(str)，向记事本插入字符串 str（英文字符）
2、delete(k)，删除记事本最后k个字符（保证不为空串）
3、print(k)，输出记事本第k个字符（保证不为空串）
4、undo()，撤销最近的1（或者）操作，使记事本回到1（或者2）操作之前的状态
可怜的小C琢磨了半天还是做不来，聪明的你能解决小C的问题吗？
他希望他的记事本包含以下功能：
1、append(str)，向记事本插入字符串 str（英文字符）
2、delete(k)，删除记事本最后k个字符（保证不为空串）
3、print(k)，输出记事本第k个字符（保证不为空串）
4、undo()，撤销最近的1（或者）操作，使记事本回到1（或者2）操作之前的状态
可怜的小C琢磨了半天还是做不来，聪明的你能解决小C的问题吗？
输入描述:
多组输入 第一行输入一个整数q，代表操作总数 以下q行每行描述了一个操作，每行以一个整数t开始（1 <= t <= 4）。 t表示上述问题陈述中定义的操作类型。 如果操作需要参数，则后跟空格分隔的参数。 题目保证所有操作均合法 1 <= q <= 10^6 1 <= k <= |记事本内容长度| 每个测试数据中str的总长度 <= 10^6 请使用 ios::sync_with_stdio(false); 对读写进行加速
输出描述:
所有操作类型3必须输出第k个字符，每行以换行符结束。
示例1
输入
8 1 ab 3 2 2 2 1 cd 3 1 4 4 3 1
输出
b c a
说明
**样例解释** 假设记事本用字符串S表示 1、插入ab，S="ab" 2、输出第2个字符，是b 3、删除最后2个字符，S="" 4、插入cd, S="cd" 5、输出第1个字符，是c 6、撤销，此时S="" 7、撤销，此时S="ab" 8、输出第1个字符，是a
思路
用栈去保存字符串的每一个状态，而当前字符串就是栈顶，增加或者删除都是一个新的状态，即新的字符串压入栈顶。所以说最后撤销只需要pop就行了。
代码
//小C的记事本(模拟)
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int n;
while(~scanf("%d" , &n))
{
int op , k;
string str , x;
stack<string> s;
s.push("");
while(n--)
{
scanf("%d" , &op);
switch(op)
{
case 1:
cin>>x;
s.push(s.top() + x);
break;
case 2:
scanf("%d" , &k);
x = s.top();
s.push(x.substr(0 , x.length() - k));
break;
case 3:
scanf("%d" , &k);
x = s.top();
cout<<x[k - 1]<<endl;
break;
default:
s.pop();
}
}
}
return 0;
} 牛客算法竞赛入门课第二节习题题解 文章被收录于专栏
入门课第二节习题题解
投递蚂蚁集团等公司10个岗位
查看17道真题和解析