当前位置:网站首页>【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
2022-07-06 09:26:00 【火焰车】
Broken Keyboard
Description
You’re typing a long text with a broken keyboard. Well it’s not so badly broken. The only problem with the keyboard is that sometimes the “home” key or the “end” key gets automatically pressed (internally).
You’re not aware of this issue, since you’re focusing on the text and did not even turn on the monitor! After you finished typing, you can see a text on the screen (if you turn on the monitor).
In Chinese, we can call it Beiju. Your task is to find the Beiju text.
Input
There are several test cases. Each test case is a single line containing at least one and at most 100,000 letters, underscores and two special characters ‘[’ and ‘]’. ‘[’ means the “Home” key is pressed internally, and ‘]’ means the “End” key is pressed internally. The input is terminated by end-of-file (EOF).
Output
For each case, print the Beiju text on the screen.
Samples
Input
This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University
Output
BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University
翻译一下:
你有一个破损的键盘。键盘上的所有键都可以正常工作,但有时Home键或者End键会自动按下。你并不知道键盘存在这一问题,而是专心地打稿子,甚至连显示器都没打开。当你打开显示器后,展现在你面前的是一段悲剧的文本。你的任务是再打开显示器之前计算出这段悲剧文本。
嗯,这道题是用链表做。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
int main()
{
string s;
while(cin>>s)
{
int len = s.size();
s = '0'+s;
int next[N]={
0},last,pin;
last = pin = 0;
for(int i=1;i<=len;i++)
{
char ch=s[i];
if(ch=='[')
pin=0;
else if(ch==']')
pin=last;
else
{
next[i]=next[pin];
next[pin]=i;//这两句对应着思路4
if(last == pin)
last = i;
pin = i;
}
}
for(int i=next[0];i!=0;i=next[i])
cout<<s[i];
cout<<endl;
}
}
Tip:Home键会让光标跳转到第一个字符之前,End键会让光标跳转到最后一个字符之后。
思路:
①我们要知道光标的位置用pin来记录。
②我们要知道末尾的字符位置用last来记录。
③当’['时光标跳转到最前面0的位置,当‘]’时光标跳转到末尾的位置last。
④在中间插入字符时,应该是:让该字符的next是前一个字符的next,并把前一个字符的next修改为该字符。(末尾的时候也可以这样,只不过该字符的next是0也就是结束)
我为什么要让字符串s变成‘0’+s呢……因为我要想输出这个链表,我就要有一个起始位置,但是我不知道我的起始位置是什么地方,所以我就假定了一个起始位置(位置0且不会改变),这样的话让字符串整体后退一个会更好操作。
==》(思路④的中间插入的思想可以用在末尾,但不能用在最前面,如果之前没有字符,那么他的next也就不存在,该字符也不能变成前一个字符的next,因此我们假定有一个不会改变的队首,输出的时候可以直接i = next[0])
边栏推荐
- VS2019初步使用
- China's earthwork tire market trend report, technical dynamic innovation and market forecast
- Research Report on market supply and demand and strategy of China's Medical Automation Industry
- Borg Maze (BFS+最小生成树)(解题报告)
- Perinatal Software Industry Research Report - market status analysis and development prospect forecast
- 0-1背包問題(一)
- China's PCB connector market trend report, technological innovation and market forecast
- 信息安全-安全编排自动化与响应 (SOAR) 技术解析
- Cost accounting [13]
- Eslint--- error: newline required at end of file but not found (EOL last) solution
猜你喜欢
Eslint--- error: newline required at end of file but not found (EOL last) solution
JS --- all basic knowledge of JS (I)
JS --- detailed explanation of JS DOM (IV)
Borg Maze (BFS+最小生成树)(解题报告)
【高老师软件需求分析】20级云班课习题答案合集
学习记录:USART—串口通讯
基于web的照片数码冲印网站
FSM and I2C experiment report
Learning record: Tim - Basic timer
用C语言写网页游戏
随机推荐
动态规划前路径问题优化方式
ucore lab 6
Cost accounting [23]
HDU-6025-Coprime Sequence(女生赛)
X-Forwarded-For详解、如何获取到客户端IP
B - 代码派对(女生赛)
ucorelab4
STM32 learning record: input capture application
0-1 knapsack problem (I)
编程到底难在哪里?
nodejs爬虫
Accounting regulations and professional ethics [1]
STM32学习记录:输入捕获应用
STM32 learning record: LED light flashes (register version)
Shell脚本编程
Es6---es6 content details
【练习-11】4 Values whose Sum is 0(和为0的4个值)
Market trend report, technical innovation and market forecast of Chinese hospital respiratory humidification equipment
学习记录:USART—串口通讯
China potato slicer market trend report, technical dynamic innovation and market forecast