[数据结构与算法]12.15学习总结

晚自习19：00——22：00：刷题

刷题量：2

第二周：栈+队列+搜索模板

栈：栈是一种先进后出的数据结构，限定只能在一端进行插入和删除操作，允许操作的一端称为栈顶，不允许操作的称为栈底。

dfs：有点类似于递归，较为暴力。通俗一点说就是一条路走到黑，如果走到一个地方，发现无法继续走下去，就反回原来的地方，寻找新的路径，直到走通为止。

bfs：dfs类似，不在过多阐述。

第一题：

给出一个由1到n组成的无序数列，如果我们把这个序列看成是数字1~n出栈的顺序，并且入栈顺序是1, 2, 3, ..., n，请问操作时，栈内最多能有多少个元素？

Input

输入有多组数据。

每组数据的第一行为一个整数n代表由1到n的序列。 1<= n ?<=100。

第二行为n个用空格隔开的整数，范围是[1,n]。

Output

若此序列能由进栈，出栈得到，输出所使用的最小栈容，否则输出-1

Sample Input

5
1 2 3 4 5
4
3 2 1 4
6
6 5 4 1 3 2

Sample Output

1
3
-1

题意：如果我们把这个序列看成是数字1~n出栈的顺序，并且入栈顺序是1, 2, 3, ..., n。以本题第二个输入示例为例：3代表1这个数第三个出列，为第一个入列的数，2代表2这个数第二个出列，第二个入列。

题解：进行多组输入，使用循环让小于a[i]的数入栈（即题意中的入列，让stack[top++]=m的原因为题意中的出列），由于为多组输入，要更新每一次栈容。代码如zh

#include <stdio.h>
int main ()
{
    int n,a[150],i,stack[150];
    while(scanf("%d",&n)!=EOF)
    {
        int max=0;
        int m=1,top=0;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
            for(i=0;i<n;i++)
            {
                while(m<=a[i])
                {
                    stack[top++]=m;//让小于a[i]的数入栈
                    ++m;
                }
                if(top>max)
                    max=top;
                if(a[i]==stack[top-1])
                    {
                         top--;
                    }
            }
                  if(top==0)
                        printf("%d\n",max);
                    else
                        printf("-1\n");
    }
    return 0;
}

ps：这道题刚开始不知道直接让小于a[i]的数入栈，还是一个hxd告诉我这个处理方法?，hxd牛皮。

第二题：

定义一个二维数组：

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

#include <stdio.h>
int mp[10][10];//现在的位置
int vis[10][10];//标记走过的点
int ans=99999;
int fx[4]={0,0,-1,1};//可以走的方向
int fy[4]={1,-1,0,0};
int flag=0;
int r=0;
int min(int a,int b)
{
    if(a>b)
        return b;
    else
        return a;
}
void dfs(int xx,int yy,int step)
{
    int i;
	if(xx==4&&yy==4)//已经走到右下角
    {
		ans=min(ans,step);
		return;
	}
	for(i=0;i<4;i++)
	{
		int x=xx+fx[i];
		int y=yy+fy[i];
		if(x>4||x<0||y>4||y<0) continue;
		if(vis[x][y]) continue;
		if(mp[x][y]==1) continue;
		vis[x][y]=1;//对走过的点进行标记
		dfs(x,y,step+1);//递归
		vis[x][y]=0;//将走过的点归回未走过的状态
	}
}struct node
{
	int x,y;
}a[1000];
void dfs1(int xx,int yy,int step)
{
    int i;
	if(xx==4&&yy==4)
        {
		if(step==ans)
		{
			flag=1;
		}
		return;
        }
	for(i=0;i<4;i++)
	{
		int x=xx+fx[i];
		int y=yy+fy[i];
		if(x>4||x<0||y>4||y<0)
            continue;
		if(vis[x][y])//已经走过了的地方不能走
		continue;
		if(mp[x][y]==1)//1的时候不能走
		continue;
		vis[x][y]=1;//对走过的点进行标记
		dfs1(x,y,step+1);
		vis[x][y]=0;//将走过的点归回未走过的状态
		if(flag==1)
		{
			 a[r].x=x;
			 a[r++].y=y;//保存路径
                return;
		}
	}
}
int main()
{
    int i,j;
	for(i=0; i<5;i++)
    {
		for(j=0; j<5;j++)
		{
			scanf("%d",&mp[i][j]);
		}
	}
	dfs(0,0,1);
	dfs1(0,0,1);
    for(i=ans-1;i>=0;i--)
	{
		printf("(%d, %d)\n",a[i].x,a[i].y);
	}
	return 0;
}

今日学习成果如上。