vlambda博客
学习文章列表

第二周的算法讲解

·开始本周的算法学习！·

“栈”

栈算是一种非常有趣的数据结构，如果用一个词概括它，那就是先入后出，不过，这样好像不是很形象，这里我用图画让大家对于栈的运作模式有个更加直观的了解

上面这张图把栈，包括入栈push，出栈pop的过程都模拟了一遍，相信你现在应该有大概的印象。

而c++里也有对应的stl容器，也就是stack，头文件是: stack.h [具体用法大家可以自行百度]

而平时我们也可以用数组模拟stack。

下面是用数组模拟stack的过程

设置对应的尾指针，存放最近插入的数的下标，记为idx，初始值为0；

每当push一个进来x时，stack[idx++] = x;

要查看第一个数时，stack[idx-1]

要pop[即将最后一个数出栈], idx--;

下面用一道题让大家熟悉栈的使用

题目链接：

https://www.luogu.com.cn/problem/P1165

我们可以看出来，题目的目的是：

让我们边模拟栈操作，同时告诉他们栈里的最大数是多少。

这里推荐大家先做完这道题再来看我的写法，注意可以利用栈的特点。

题目分析

首先我们先分析题目的要求，选择0时，将一个数入栈；选择1时，则将最后加入的去掉，那就是出栈；选择2时，输出此时库里的最重的东西是什么。

其中比较麻烦的问题是如何随时输出库里的最大的重量。

看到这个你可能会想，我拿一个变量存放最大值不就行了么，但是当我取出时，这个最大值可能就会发生变化，难道我要每取出一次就遍历一遍么，这明显太浪费时间了。

那我们该怎么办呢？其实我们可以这样想，当每放进去一个东西时，我记住每个时刻最重的东西不就行了么？

那么我取出多少件东西的时候，我就把每一时刻最重的东西更新为前一时刻最重的东西不就行了么？

确实，我们可以这样做，但是这其实也是另一种形式的栈！

当我们每次放入东西时，我们可以拿另一个栈存放放入东西那一时刻我们最大的重量，当取出物品的同时，我们也把存放每一时刻最大重量的栈出栈，这样我们栈顶就永远显示我们放入每个物品时所对应的最大重量。

下面是自己写的代码：

这里其实用一个maxn栈也行，但是为了方便大家，所以使用两个栈，表现出来更加直观。

“深度优先搜索(DFS)”

DFS，即深度优先搜索，也被称为暴搜，是一种利用递归特点的搜索方法。

和我们走迷宫有点相似，当我们不知道能不能另一端时，我们可能就会把所有路都走一遍，说不定会走到迷宫的终点呢？

那DFS是如何实现的呢？

这里用走迷宫的道理来教你。

走迷宫的时候，每走一步，就要抉择该走哪个方向，那就走一步我就标记(防止自己重新走一遍浪费时间)，标记了的就是我走过了的；当我发现走到绝境了，那就原路返回到前一个交叉口(递归回去)。返回了就往其他没走过的方向走，又走到绝境就又返回，直到无路可走为止。

看完之后是不是觉得就是一个递归的过程。

那就先拿一道题来练练手吧

题目链接：

http://poj.org/problem?id=1426

可能有的小伙伴会觉得，我天，这就放一道英文题目，好可怕。我表示别慌，静下来，有翻译软件。

这里给下题意：给一个两百以内的整数，要求找到由0和1组成的可以被其整除的整数

这题其实就是一道典型的dfs题目

这次我先放我的做法

大家看到之后可能会想，这不就是递归么？

是的，我也认为这就是递归而言，但是dfs其实还有各种剪枝之类，但无疑它就是一种暴力搜索。

别跑题，我们来分析下为啥要这样写哦。

首先，d是用来防止数字超过long long的，如果超过了就返回去找其他方法。其次flag是找到的标记，毕竟找到就没必要找了，所以return。

然后每一位都有两种可能，所以我们要列出来进行判断，才有最后面两个自我调用。

然后放我自己写的解法(其实是n久之前的了)：

“DFS(2)”

第二部分其实也是做题。

题目链接：

https://vjudge.csgrandeur.cn/problem/LightOJ-1012

题意：

给你一个由起始点'@', 空地'.', 水'#'，问你王子可以居住的是哪几个块，注意水'#'是不能居住的，空地才可以，起始点也包括。

之前有讲过，我们需要把每个走过的地方标记一下，这里有个取巧的方法，就是把走过的地方都当成不能走的地方即可。然后每走一个我们都要num++，而且还要往四个方向看看能不能走，也就是+b[k][0], +b[k][1]这一部分，这里其实是把四个方向存在一个数组里面了，具体看完整代码。

然后注意搜索过程中的边界问题要记得判断，然后遇到空地才能调用下一步，不断继续find，直到找到的时候return，不过此处让它简单的终结即可，要不要遇到终点才返回都可以。

本人写法：

最后放两道题让大家自行学习下

https://vjudge.csgrandeur.cn/problem/LightOJ-1049

https://vjudge.csgrandeur.cn/problem/LightOJ-1111