您现在的位置是: 首页  >  计算机基础  >  数据结构与算法
  • 深度优先搜索解决矩阵搜索问题

    深度优先搜索解决矩阵搜索问题

    最近在刷LeetCode的时候发现一类和二维矩阵(二维数组)搜索有关的题目,一般使用深度优先或广度优先搜索就可以很好的解决这类题目,这里特意总结一下。1、剑指Offer12.矩阵中的路径这是一个典型的矩阵搜索问题,可使用深度优先搜索(DFS)+剪枝解决。首选,在矩阵中任意选择一个格子作为路径的起点。假设举证中某个格子的字符为ch,并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是ch,那么这个格子不可能处在路径上的第i个位置。如果路径上第i个字符正好是ch,那么到相邻的格子寻找路径上的第i+1个字符。出矩阵边界上的格子以外,其他格子都有上、下、左、右4个方向可以选择,重复这个过程,知道路径上所有字符都在矩阵中找到相应的位置。并且为了便于控制一个格子只会被访问一遍,我们可以使用一个和矩阵一样大小的boolean矩阵来标识路径是否已经进入了某个格子。相信上面代码一看就会,值得说明的一点使用了isVisited来判断是否再次访问,用来标记已经访问过的点。2、岛屿问题岛屿问题是一类经典的网格搜索类问题。关于岛屿的题目有:200.NumberofIslands岛屿数量695.MaxAreaofIsland岛屿最大面积463.岛屿的周长694.不同岛屿的个数711.不同岛屿的个数II要求解这道题,我们首先来看如何在网格上做DFS如何在网格上做DFS网格问题是这样一类搜索问题:有m\timesnm×n个小方格,组成一个网格,每个小方格与其上下左右四个方格认为是相邻的,要在这样的网格上进行某种搜索。这种题目乍一看可能有点麻烦,实际上非常简单,尤其是用DFS的方法。题目没有限制的话,我们尽量用DFS来写代码。下面我们一步步地构造出方格类DFS的代码。首先,每个方格与其上下左右的四个方格相邻,则DFS每次要分出四个岔:但是,对于网格边缘的方格,上下左右并不都有邻居。一种做法是在递归调用之前判断方格的位置,例如位于左边缘,则不访问其左邻居。但这样一个一个判断写起来比较麻烦,我们可以用“先污染后治理”的方法,先做递归调用,再在每个DFS函数的开头判断坐标是否合法,不合法的直接返回。同样地,我们还需要判断该方格是否有岛屿(值是否为1),否则也需要返回。之后为了能够让递归停止下来,我们需要在遍历的时候把已经遍历过的网格做一下标记,可以单独开辟一个和矩阵同样大小的二维boolean矩阵来记录,或者也可以直接修改遍历过的网格的值使其在下一次判断时条件不成立。通常考虑到内存友好,我们直接在原数组上标记就好了。标记遍历过的方格并不需要使用额外的空间,只需要改变方格中存储的值就可以。在这道题中,值为0表示非岛屿(不可遍历),值为1表示岛屿(可遍历),我们用2表示已遍历过的岛屿。这样我们就可以得到网格DFS遍历的框架代码:岛屿有关的二维数组搜索问题,基本都可以在此框架上修改得到结果。我们来看下面几道经典的题。2.1LeetCode200.岛屿数量示例:对于这个二维矩阵进行遍历,如果来到一个是1的位置,开始一个“感染”过程,就是从当前位置出发,把连成一片的1全部变成2。“感染”过程结束之后,继续遍历二维矩阵,直到结束。有多少次“感染”过程,就有多少个岛。实现“感染”过程。假设从i行j列位置出发,向上下左右四个位置依次去“感染”。写成递归函数即可。2.2LeetCode695.岛屿的最大面积示例:基本思路和上面相同,只是需要在遍历每个岛屿的时候,使用一个计数器将这个岛屿的陆地数目记录下来返回,然后比较每个岛屿的大小,返回最大的岛屿的面积即可。代码实现上只需做略微改动即可。2.3LeetCode463.岛屿的周长示例:求岛屿的周长其实有很多种方法,如果用DFS遍历来求的话,有一种很简单的思路:岛屿的周长就是岛屿方格和非岛屿方格相邻的边的数量。注意,这里的非岛屿方格,既包括水域方格,也包括网格的边界。我们可以画一张图,看得更清晰:将这个“相邻关系”对应到DFS遍历中,就是:每当在DFS遍历中,从一个岛屿方格走向一个非岛屿方格,就将周长加1。完整代码如下:那么每一次进行“深度优先遍历”或者“广度优先遍历”的条件就是:1、这个格子是陆地1,如果是水域0就无从谈论“岛屿”;2、这个格子不能是之前发现“岛屿”的过程中执行了“深度优先遍历”或者“广度优先遍历”操作,而被标记的格子(这句话说得太拗口了,大家意会即可,意会不了不是您的问题,是我表达的问题,直接看代码会清楚很多)。3、剑指Offer13.机器人的运动范围示例:输入:m=2,n=3,k=1输出:3这个题目和前面对题目类似,也可以看做是一个m×n的矩阵。同样,在这个矩阵中,除了边界上的格子,其他位置的格子都有4个相邻的格子。机器人从(0,0)开始。当他准备移动到(i,j)的时候,首先判断他能否进入,如果他可以进入,则在判断它能否进入4个相邻的格子。同时这道题还有一个隐藏的优化:我们在搜索的过程中搜索方向可以缩减为向右和向下,而不必再向上和向左进行搜索。如下图,我们展示了19*19的地图随着限制条件k的放大,可行方格的变化趋势,每个格子里的值为行坐标和列坐标的数位之和,绿色方格代表非障碍方格,即其值小于等于当前的限制条件k。我们可以发现随着限制条件k的增大,(0,0)所在的绿色方格区域内新加入的非障碍方格都可以由上方或左方的格子移动一步得到。而其他不连通的黄色方格区域会随着k的增大而连通,且连通的时候也是由上方或左方的格子移动一步得到,因此我们可以将我们的搜索方向缩减为向右或向下。可以套用岛屿问题中的模板,完整代码如下:参考【1】liweiwei1419.DFS+BFS+并查集(Python代码、Java代码).力扣(LeetCode)【2】nettee.图解:在DFS遍历过程中求周长(Java).力扣(LeetCode)

    LoveIT 2020-10-24
    数据结构与算法
  • 十大经典排序算法(动图演示)

    十大经典排序算法(动图演示)

    0、算法概述0.1算法分类十种常见排序算法可以分为两大类:比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。0.2相关概念稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。0.3算法复杂度分析1、冒泡排序(BubbleSort)冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。1.1算法描述比较相邻的元素。如果第一个比第二个大,就交换它们两个;对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;针对所有的元素重复以上的步骤,除了最后一个;重复步骤1~3,直到排序完成。1.2动图演示1.3代码实现优化当我们的数字序列基本有的时候往往只需要扫描几次就可以排序好了,当数字序列有序了之后在重复扫描那就是在做无用功,因此我们需要优化一下代码的实现。2、选择排序(SelectionSort)选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。2.1算法描述n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:初始状态:无序区为R[1..n],有序区为空;第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;n-1趟结束,数组有序化了。2.2动图演示2.3代码实现2.4算法分析表现最稳定的排序算法之一,因为无论什么数据进去都是O(n^2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。3、插入排序(InsertionSort)插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。3.1算法描述一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:从第一个元素开始,该元素可以认为已经被排序;取出下一个元素,在已经排序的元素序列中从后向前扫描;如果该元素(已排序)大于新元素,将该元素移到下一位置;重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;将新元素插入到该位置后;重复步骤2~5。3.2动图演示3.2代码实现优化上面的算法在寻找合适的插入位置的时候使用的是顺序查找,非常的耗费时间,既然前面的数字序列是已经排序好的,那么我们可以思考可以用二分查找优化寻找合适插入位置的逻辑。3.4算法分析插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。插入排序在小数据量或数据基本有序的情况下非常高效,但是数据量一大就基本不那么好使了,基于此Shell排序应运而生。4、希尔排序(ShellSort)1959年Shell发明,第一个突破O(n^2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。4.1算法描述先将整个待排序的记录序列分割成为若干子序列(分割成小数据量)分别进行直接插入排序,具体算法描述:选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;按增量序列个数k,对序列进行k趟排序;每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序。仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。4.2动图演示4.3代码实现4.4算法分析希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版)》的合著者RobertSedgewick提出的。 5、归并排序(MergeSort)归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。5.1算法描述把长度为n的输入序列分成两个长度为n/2的子序列;对这两个子序列分别采用归并排序;将两个排序好的子序列合并成一个最终的排序序列。5.2动图演示5.3代码实现5.4算法分析归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。6、快速排序(QuickSort)快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。6.1算法描述快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:从数列中挑出一个元素,称为“基准”(pivot);重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。6.2动图演示6.3代码实现7、堆排序(HeapSort)堆排序(Heapsort)是利用堆这种数据结构而设计的一种排序算法,堆排序是一种**选择排序,**它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:大顶堆:arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]小顶堆:arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]一般升序排序使用大顶堆,降序排序使用小顶堆。ok,了解了这些定义。接下来,我们来看看堆排序的基本思想及基本步骤:7.1算法描述以升序排序为例,算法思路如下:将待排序的序列构造成一个大顶堆,根据大顶堆的性质,当前堆的根节点(堆顶)就是序列中最大的元素将堆顶元素和最后一个元素交换,然后将剩下的节点重新构造成一个大顶堆;重复步骤2,如此反复,从第一次构建大顶堆开始,每一次构建,我们都能获得一个序列的最大值,然后把它放到大顶堆的尾部。最后,就得到一个有序的序列了。7.2动图演示7.3代码实现7.4算法分析堆排序是一种选择排序,整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n),在交换并重建堆的过程中,需交换n-1次,而重建堆的过程中,根据完全二叉树的性质,[log2(n-1),log2(n-2)...1]逐步递减,近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。8、计数排序(CountingSort)计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。8.1算法描述找出待排序的数组中最大和最小的元素;统计数组中每个值为i的元素出现的次数,存入数组C的第i项;对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。8.2动图演示8.3代码实现优化8.4算法分析计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时,时间复杂度是O(n+k),空间复杂度也是O(n+k),其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。9、桶排序(BucketSort)桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序(Bucketsort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。9.1算法描述设置一个定量的数组当作空桶;遍历输入数据,并且把数据一个一个放到对应的桶里去;对每个不是空的桶进行排序;从不是空的桶里把排好序的数据拼接起来。9.2图片演示9.3代码实现9.4算法分析平均时间复杂度:O(n+k)最佳时间复杂度:O(n+k)最差时间复杂度:O(n^2)空间复杂度:O(n*k)稳定性:稳定10、基数排序(RadixSort)基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。10.1算法描述取得数组中的最大数,并取得位数;arr为原始数组,从最低位开始取每个位组成radix数组;对radix进行计数排序(利用计数排序适用于小范围数的特点);10.2动图演示10.3代码实现10.4算法分析基数排序基于分别排序,分别收集,所以是稳定的。但基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要O(n)的时间复杂度,而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2n),当然d要远远小于n,因此基本上还是线性级别的。基数排序的空间复杂度为O(n+k),其中k为桶的数量。一般来说n>>k,因此额外空间需要大概n个左右。参考资料【1】十大经典排序算法(动图演示)【2】图解排序算法(三)之堆排序

    LoveIT 2020-08-01
    数据结构与算法