分治算法

一、分治算法的主要思想

• 将原问题递归的分解成若干性质相同、互相独立的子问题，直到问题满足边界条件停止递归。然后将子问题逐个击破（一般是同种方法），将已经解决的子问题合并，最后算法会层层合并得到子问题的解。

二、分治算法的步骤

• 分：递归地将问题分解为各个的子问题(性质相同的、相互独立的子问题)
• 治：将这些规模更小的子问题逐个击破
• 合：将已解决的子问题逐层合并，最终得出原问题的解
  

三、分治算法适用的情况

• 原问题的计算复杂度随着问题的规模的增加而增加
• 原问题能够被分解成更小的子问题
• 子问题的结构和性质与原问题一样，并且相互独立，子问题之间不包含公共的子子问题
• 原问题分解出的子问题的解可以合并为该问题的解

四、分治算法的应用

1.LeetCode第169题：多数元素

• 题目描述：给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 [n/2] 的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。
• 解题思路：
  1.直到所有的子问题都是长度为 1 的数组，停止切分
  2.递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回
  3.处理子问题得到子结果，并合并
• 解决代码：
  
• 其他解决方法：
  哈希表
  
  排序
  

2.LeetCode第53题：最大子序和

• 题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
• 解题思路：
  1.直到所有的子问题都是长度为 1 的数组，停止切分
  2.递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回
  3.处理子问题得到子结果，并合并
• 解题代码：
  

3.LeetCode第50题：Pow(x,n)

• 题目描述：实现 pow(x, n) ，即计算 x 的 n 次幂函数。
• 解题代码：
  

刚入门的小白还不太会所以目前能读懂标准解题代码并且自己能做出题目就算是进步辽，还请大家多多指点。

资料来源：Datawhale&LeetCode