《算法与数据结构》带你领略分治算法之美为了更好的区分，我们称之为“分而治之”。如果你不知道什么是分而治之，或者知道一些，但它是如何实现回溯的，那么这篇文章可能适合你阅读。我对分治算法的理解：它的基本思想是将一个大小为N的问题分解成K个更小的子问题，这些子问题相互独立，与原问题具有相同的性质。求子问题的解可以得到原问题的解，可以理解为通过子目标完成程序的算法。二分法往往是一种分而治之的思维。然后重点介绍下分治算法👇基本思想的应用以及解决了哪些经典问题。形成n个规模较小、结构与原问题相似的子问题，递归求解这些子问题，然后将结果一一合并，最终得到原问题的解。所以具体来说，我们似乎可以将其分为三个步骤👇分解：把要解决的问题分解成若干个规模较小的相似问题。解决方法：当子问题分解得足够小时，用更简单的方法来解决。合并：根据原问题的要求，将子问题的解逐层合并，形成原问题的解。其实思路还是一样的。将一个难以解决的大问题直接分解成一些小规模的相同问题，从而逐一突破，分而治之。分治法的适用性用分治法解决一个问题，关键在于我们能否把握分治法的几个特点：一个问题可以在一定程度上缩小，变成更小的问题来解决。分解成几个小问题后，规模较小，属于同类问题。在这种情况下，问题应该是最优子结构。将问题分解的子问题的解组合成问题的解。分解后的子问题相互独立，即子问题之间没有共同的子问题。下面说说这几个特点吧~第一个特点：一个问题的计算复杂度一般会随着问题的规模增大而增加，所以大部分问题都是满足的。第二个特点：应用分治法的前提是要满足它。你可以理解为它在一定程度上反映了递归思想的应用。第三个特点：这应该是分治法的关键。这个问题能不能用，完全取决于这个问题是否具备第三个特征。如果它具有第一个和第二个特征，则它不具有第三个特征。特征，可以考虑使用贪心法或者动态规划法。第四个特点：涉及到分治法的效率。如果子问题不是独立的，分而治之的方法会做很多不必要的工作，重复解决共同的子问题。这时候虽然可以使用分治法，但是一般还是使用动态规划的方法比较好。为了理解分而治之法的特点，我们先来看一些使用这种思路解决问题的经典问题👇目录👇(1)二分查找(2)大整数乘法(3)施特拉森矩阵乘法(4)棋盘覆盖(5)归并排序(6)快速排序(7)线性时间选择(8)最近点关于问题(9)循环schedule(10)汉诺塔，我想提的是归并（merge）排序，完成分而治之的思想，分解大问题，解决各种规模的小问题，最后归并，那么我们将看看合并（merge）排序代码👇归并排序对于归并排序的思想，是如何实现的呢？上一章排序有讲到，它采用了分而治之的思想。你可以看到它是如何实现的。这里不详述。2个例子接下来我们以三个题目为例，看看如何使用分而治之的思想来解决问题👇thelargestsubsequenceand?link:最大子序列，给定一个整数数组nums，找到一个具有最大和的Contiguous子数组（子数组至少包含一个元素），返回它的最大和。示例：输入：[-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版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。首先，让我们看看是否可以用O(n)的复杂度来解决这个问题。其实仔细想想，我们可以通过更简单更简单的问题来解决这个问题。对于一个数组的最大子序列和，它对答案的贡献只能在以下几种情况下👇出现在左半边，出现在右半边，出现在中间，穿过中间。那么我们可以递归处理吗？对于出现在左边和右边的答案，我们可以把它们看成一种情况，然后递归处理。当然，递归退出，显然，当递归数组长度为1时，我们需要递归结束。对于中间出现答案的情况，我们可以通过计算算出答案，这样思路就清晰了。接下来，让我们看看如何编写👇连续最大和分治法。当然这道题可以用动态规划的思想更好的解决，更好的理解👇//dp[i]表示nums中以nums[i]结尾的最大子序列和这里的连续性和码点动态规划??搜索二维矩阵二??链接：搜索二维度矩阵二写一个高效的算法来搜索对于mxn矩阵矩阵中的目标值目标。该矩阵具有以下性质：每行的元素从左到右按升序排列。每列的元素从上到下按升序排列。例：现有矩阵矩阵如下：[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]给定target=5，返回true。给定target=20，返回false。来源：LeetCode链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii版权归Leetcode.com所有。商业转载请联系官方授权，非商业转载请注明出处。这个问题的标题很明确👉矩阵的每一行都是从左到右升序排列的，每一列也是从上到下升序排列的。在矩阵中找到某个数字。当然，我们有一个简单的想法👇维护两个指针(row,col)，当我们找到目标元素时，我们把它放回true；当指向的元素的值小于target时，我们使用col++向上移动一行。如果当前值大于当前目标，我们行--，向左移动一列。当我们知道col>matrix的行，或者row<0时，直接返回false，表示不存在。时间复杂度：O(n+m)时间复杂度分析的关键是要注意在每次迭代中（我们不返回true），行或列恰好递减/递增一次。由于行只能减少m次，列只能增加n次，因此在导致while循环终止之前，循环不能运行超过n+m次。因为所有其他工作都是不变的，所以总体时间复杂度与矩阵维数之和呈线性关系。根据上面的伪代码，我们基本可以解决这个问题👇二进制矩阵评估的解决方案简单易懂。其实这并不是真正意义上的二分法，只是根据数据的特殊性，使用特定的搜索方法完成矩阵的查找。既然我们在一维数组中检查某个值时可以将复杂度降低到对数级别的时间复杂度，那么我们是否也可以考虑在二维情况下呢？这个思路可以借鉴👇我们可以遍历矩阵对角线，对这些行和列进行二进制搜索，然后将它们切片。在对角线上迭代，二分查找行和列，直到对角线上的迭代元素都用完（这时候可以把true或者false放回去）简单来说，二分查找的思想就是沿着Diagonal，查找行，查找列。你可以从代码中学习，你会明白如何使用矩阵的对角线来分而治之。二值矩阵求值代码点此??了解分而治之的思想，对其特点有一定的了解，了解如何用它来解决实际问题，那么也许这就是这篇文章的意义吧~题目总结题目不多，但对于基础入门分而治之应该是个不错的选择👇拆分数组的最大子序列和连续数列
