前言
这次分享的内容是,经典算法思想-分治,你可以把它称之为一种思想,也可以叫它分治算法,为了更好的区分,接下来我们以'分治法'来称呼它。
如果你还不了解什么是分治法,或者知道一些,但是对于它具体是如何实现回溯,那么这篇文章可能适合你阅读。
我对分治算法的理解:
那么围绕以下几个点来展开介绍分治算法👇
分治法基本思想
一句话,对分治法概括它的话👇
将原问题划分成n个规模较小而结构与原问题相似的子问题,递归去解决这些子问题,然后依次再合并其结果,最后得到原问题的解。
那么具体的来说,我们似乎可以分成三个步骤👇
其实思想还是不变的,将一个难以直接解决的大问题,分割成一些小规模的相同问题,以便各个击破,分而治之。
分治法适用情况
利用分治法求解一个问题,在于我们能否掌握分治法的几个特征:
那我们来说一说这几个特征吧~
第一条特征:一个问题的计算复杂性一般是随问题的规模增加而增加的,所以绝大多数问题都满足。
第二条特征:应用分治法的前提是得满足它,你可以理解成它某种程度上反映了递归思想的应用。
第三条特征:这个应该就是分治法的关键了吧,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑用贪心法或动态规划法。
第四条特征:涉及到分治法的效率,如果各子问题是不独立的则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。
了解分治法的特征,我们来看看有哪些经典的问题是利用这个思想来解决问题的👇
分治法求解经典问题
什么情况下,可以用该思路来求解呢,以下来自网上搜集的内容👇
(1)二分搜索
(2)大整数乘法
(3)Strassen矩阵乘法
(4)棋盘覆盖
(5)合并排序
(6)快速排序
(7)线性时间选择
(8)最接近点对问题
(9)循环赛日程表
(10)汉诺塔
我想提起的是合并(归并)排序,它完成照应分治法的思想,分解大问题,解决各个规模小问题,最后合并,那我们来看看合并(归并)排序代码👇
归并排序
对于归并排序的思路,是如何实现的,之前的排序一章以及提及过,采用的是分治思路,可以看看是如何实现的,这里就不具体展开了。
2个例子
接下来,我们通过三个题目作为例子,来看看怎么利用分治的思想来解决问题👇
最大子序和⭐
链接:最大子序和
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
首先,我们看看能不能以O(n)复杂度解决这个问题,其实仔细想一想的话,我们可以通过一个简单
更多得是,我们这题尝试一下用分治法来解决这题。对于一个数组的最大子序和,它对答案的贡献,只能是以下几种情况👇
那么我们是不是可以递归处理呢,对于出现在左边和出现在右边的答案,我们可以把它们当作是一种情况,然后递归去处理,当然了递归的出口,很显然,当递归的数组的长度为1时,我们需要递归结束。
对于出现在中间答案的情况,我们可以通过计算来算出答案,所以思路理清楚, 接下来,我们看如何写👇
分治法连续最大和
当然了,这题用动态规划思路更好求解,也更加得好理解👇
动态规划求连续和
代码点这里☑️
搜索二维矩阵 II⭐⭐
链接:搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例:
现有矩阵 matrix 如下:
给定 target = 5,返回 true。
给定 target = 20,返回 false。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/search-a-2d-matrix-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这题的题目很清晰👉矩阵的每行从左到右是升序, 每列从上到下也是升序,在矩阵中查找某个数。
当然了,我们有一个简单的思路👇
时间复杂度:O(n+m)
根据以上的伪代码,我们基本上就能解出这个题目👇
二位矩阵求值
这样子的解法,简单且容易理解,其实这并不是真正意义上的二分,只是根据数据的特殊性,使用特定的搜索方式完成对矩阵的查找。
既然一维数组查某个值时,我们可以将复杂度降为log级别的时间复杂度,那么在二维的情况下,我们是不是也可以这么考虑呢?
这个思路,可以借鉴一下👇
说得更加简单一些,二分查找的思想是沿着对角线,行查找一下,列查找一下。
可以借鉴一下代码,就会明白如何利用矩阵的对角线去分治。
二位矩阵求值
代码点这里☑️
理清楚分治法思路,对它的特征有了一定的了解,明白何如利用它解决实际的问题,那或许这就是这篇文章的意义所在吧~
题目汇总
题目不多,但是对于基本的入门分治法,应该还是不错的选择👇
多年以后,面对台下五彩斑斓的Jetbrain和Vscode用户,这位曾经的资深的vim追随者...
在Asp.net Core之前所有的Action返回值都是ActionResult,Json(),File()等方法返...
一个常见的场景,获取:标签背景图片链接: 如字符串:var bgImg = "url (\" htt...
1 概述 在接下来的时间里,将会入手ASP.NET MVC这一专题,尽量用最快的时间,最...
在新的MySQL 8.0.23中,引入了新的有趣功能:不可见列。 这是第一篇关于这个新功...
详解Spring Controller autowired Request变量 spring的DI大家比较熟悉了,对于...
需要注意的是,调用的封装的数据库,和jQuery的保存地址 一、注册 (1)写文本框...
最近在学习jQuery时接触到了show()、hide()、toggle()函数,于是利用这几个函数...
大家好我是爱景甜的网工我是一个思科出身专注于华为的网工 好了话不多说进入正题...
git clone支持https和git(即ssh)两种方式下载源码: 当使用git方式下载时,如...