UVA11988 Broken Keyboard 鏈表

UVA11988 Broken Keyboard 鏈表

題目描述：

你在輸入文章的時候，鍵盤上的Home鍵和End鍵出了問題，會不定時的按下。

給你一段按鍵的文本，其中'['表示Home鍵，']'表示End鍵，輸出這段悲劇的文本。

解題思路

用順序結構儲存會超時 所以用模擬鏈表來儲存

cur表示光標的位置 last表示當前最後一個字符的編號 next[i]表示s[i]後面的字符的編號 為了方便起見在數組的最前面虛擬一個s[0]。代碼如下

#include 
#include 
#include 
using namespace std;
const int maxn = 100005;
char s[maxn];
int last,cur,next[maxn];
int main()
{
    while(scanf("%s",s+1) == 1) {
        int n = strlen(s+1);
        last = cur = 0;
        next[0] = 0;
        for(int i = 1 ; i <= n ; i ++) {
            char ch = s[i];
            if(ch == '[') cur = 0;
            else if(ch == ']') cur = last;
            else {
                next[i] = next[cur];//先把指針直到下一個去
                next[cur] = i;//再指過來
                if(cur == last) last = i;//更新最後一個字符的編號
                cur = i;
            }
        }
        for(int i = next[0] ; i != 0 ; i = next[i]) {
            printf("%c",s[i]);
        }
        printf("\n");
    }
    return 0;
}