分治策略的常见应用有二分法(分治应用于边界划分)、归并排序和快速排序，实现和详解见排序归纳总结（插入排序、归并排序、堆排序、快速排序、桶排序）

  在此简单总结一下分治的思想，一个问题可以拆分成众多的相同结构的子问题的求解，且子问题和原问题是相同性质的，且分出的子问题之间互不影响也即相互独立。同时，某个子问题中的解就是原问题的解。

接下来进入正题，以 395. 至少有K个重复字符的最长子串 为例，再理一下分治的思路。还有一道题，要求 O ( n l o g n ) O(nlogn) O(nlogn)时间复杂度， O ( 1 ) O(1) O(1)空间复杂度重排链表为有序链表：148. 排序链表，其实就是数归并排序的链表实现，这里就展开了。

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k。返回这一子串的长度。

  对于该问题，通过观察不难发现字符串中出现频次少于所要求频次k的字符，一定不会出现在所求的最长子串当中，则利用这一性质可以对整个字符串进行分割，分割为左右两个子串，再分别求解左右子串的最长子串，在所有符合题设的最长子串当中找出长度最长的子串并返回其长度即可完成题目要求。由此可以确立能够使用分治方法进行解题。

具体思路为：   先将整个字符串遍历一编，统计每个字符出现的频次从头开始遍历字符串，若是发现当前字符所出现频次小于要求的频次，则说明再所求的最长子串当中不会包含这个字符，则可将整个字符串分解为求解当前所遍历的字符为分割点的左子串和右子串的最长子串中的最大值。举例：

  注意代码实现中，通常分治和递归是伴生的，因为将大问题拆分为同等子问题，得到子问题的答案并更新大问题答案就意味着递归调用的产生。牵扯到递归，有三大要素，分别是返回条件、本层递归中的行为和返回值。

  对于返回条件和返回值：①如果k不大于2，则可直接返回s的长度；②若是s为空，或s长度小于k直接返回0；③若是整个字符串中的字符出现频次都大于等于k，则直接返回字符串的长度；④否则返回分割后的左右子串的最长子串长度中较大值；

  对于本层中的递归动作，就是找出分割点/区间，进行递归调用。