算法竞赛入门第6章

数据结构基础

6-1 如果要在队列两端进行插入和删除，可以用STL中的双端队列deque
6-2 简单的表达式解析可以借助栈来完成，如矩阵链乘
6-3 在数组中频繁移动元素是很低效的，如有可能，可以使用链表
6-4 scanf("%s", s+1)将输入保存在s[1], s[2], ...中；n=strlen(s+1)
6-5 可以用new运算符申请空间并执行构造函数。如果返回NULL，说明空间不足，申请失败。eg. Node* newnode() { return new Node(); }
6-6 如果程序动态申请内存，请注意内存泄漏。程序执行完毕后，操作系统会回收该程序申请的所有内存（包括泄露的），所以在算法竞赛中内存泄漏问题往往不会造成什么影响。但是从专业素养的角度考虑，要对内存泄漏时刻保持警惕。
6-7 已知中序和先序或者已知中序和后序遍历可以唯一确定一棵二叉树，但是仅知先序和后序无法唯一确定一棵二叉树，因为它只反映了结点间的父子关系，没有反映出左右关系。
6-8 int dir[8][2]={{0,-1},{0,1},{-1,0},{1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
6-9 图有DFS遍历和BFS遍历，前者用递归实现，后者用队列实现。求多维数组连通块的过程也称为种子填充。
6-10 使用BFS求出图的最短路径之后，可以用递归的方式打印最短路的具体路径。如果最短路非常长，递归可能会引起栈溢出，此时可以改用循环，用vector保存路径。

链表： UVa 11988 破损的键盘

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100005;
char s[maxn];
int next[maxn];

int main()
{
    while(scanf("%s", s+1)==1)
    {
       int n=strlen(s+1); //存在s[1]...中
       int cur=0, last=0;   // s[0]作为第一个虚拟节点
       next[0]=0;

       for(int i=1; i<=n; i++)
       {
           if(s[i]=='[')
           {
               cur = 0; //当前光标位于s[cur]的右边
           }else if(s[i]==']')
           {
               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])
       {
           cout<<s[i];
       }
       cout<<endl;

    }
    return 0;
}

链表如图：

image.png