cctvkill1/aha

一本入门算法书，闲来无事敲敲代码

啊哈！算法

上传一些代码及自己的看法

###2016-7-11 快速排序
数组中找个基数，将基数定位，然后基数左右两边的递归此方法，知道两边都排序
时间复杂度最差的时候和冒泡排序一样 都是O(N²) 平均是O(NlogN) 差不多是6点几(N为10)
找到原书18页有个left>right的bug 应该是>=
php有个简单写法 但是速度不快
###2016-7-12 队列、栈 ###2016-7-13 链表 ###2016-7-14 火柴棍等式 就是枚举
全队列 和 □□□+□□□=□□□等式 简单的深度优先
这节主要是理解depth first search.DFS 深度优先搜索的基本理念
关键在于‘当下这一步该怎么做’，‘至于下一步怎么做’ 则与 ‘当下这一步该怎么做’ 一样
注意book[x] = 0的那一步 ###2016-7-19 解救小哈
一张二维数组中找小哈(深度优先搜索)，0为空地，1为障碍
第一步 出发点都尝试上下左右走一步，然后每一步再作为出发点，dfs 一直递归 一条路走到头
直到找到小哈并比较最短路径是不是最小 没找到则退回上一个点 然后重新尝试第一步 深度优先搜索: 约翰·霍普克洛夫特和罗伯特·陶尔扬在1971年发明此算法 ###2016-7-20 解救小哈 题目和昨天一样
一张二维数组中找小哈(广度优先搜索)，0为空地，1为障碍
通过 一层一层的扩展，扩展时每发现一个点就加入队列，直到找打小哈
第一步 出发点 扩展 尝试上下左右走一步 将每一步加入队列 ，判断找到小哈
没有继续 扩散 重复第一步 走过的和出界的不加入队列 直到找到小哈
广度优先搜索：Edward F.Moore 在1959年率先提出 ###2016-7-21 炸弹人 （上次炸弹人解出来地图上哪一点灭最多，但是没有判断这个点是否可以走过去）
利用广度优先搜索 探路 然后再计算每一步炸多少敌人 记录最多的位置 ###2016-7-30 宝岛探险 广度、深度优先搜索 (队列版) 小哈掉在一个岛上 一步一格 算这个岛的面积（加了个队列版和数组版）
利用广度优先搜索 以降落点为出发点 向四周扩散，每一步可以往4个方向走，将新点入列（没出界，没走过的非海洋的点）并且面积加一
走完4个方向 将这个点出列 然后从入列的几个点继续扩散 直到队列为空 即算出岛面积
深度就是递归 特别注意book[tx][ty]=0 那步不能要 因为递归完了一步之后不用回撤这步然后继续递归 因为回撤了会死循环了
---Floodfill 漫水填充法（也称种子填充法）：求一个图中独立子图的个数，这算法再计算机学中广泛应用
比如图像分割、物体识别、windows画图里的油漆桶、ps里的魔术棒查找颜色相近的点（有个阈值）
###2016-8-7 水管游戏 在N*M的地图上有树木 和管道，
管道只有L型和I型两种（直的、弯的）然后水从左上角0,0出发经过管道 判断能否从右下角出来（管道可以旋转对接）
分析下就是管道分6种状态（L 旋转4种朝向 I 旋转就1种）然后用深度优先搜索尝试下一步能否到达终点