分治思想

算法中有许多特殊的解法，不求一步到位的解出题目，而是通过把大问题简化成小的子问题来解决，分治和dp都是其优秀代表。
分治实现形式可以借用递归。另外dp的思想也与之类似，都是定义子问题 + 设定边界条件来完成算法。
注：本文并非题解，而是作为分治算法的专门讲解，主要讲思路而非题目

一、全局分治

全局分治的意思是，需要对全局进行分治才能得出最后的答案，需要维护全局的状态空间（不重也不漏）才能找到最终结果。 一般题目的暗示语句为：“找出所有符合条件的解”的选择类型的算法，或是类似于“将数组排序”的维护类的算法。
1、题目一：LeetCode 23 合并K个升序链表
合并两个升序数组是很好写的，但合并K个怎么解决？
分治思想便是将“两个升序链表的合并”作为最小子问题来解决K个链表

1）解决最小子问题

private ListNode mergeTwo(ListNode a, ListNode b) {
	ListNode head = new ListNode(0);
    ListNode cur = head;
    while (a != null || b != null) {
        if (b == null || (a != null && a.val <= b.val)) {
            cur.next = a;
            a = a.next;
        } else {
            cur.next = b;
            b = b.next;
        }
        cur = cur.next;
    }
    return head.next;
}

2）划分子问题
如果子问题只有一个链表，则直接返回
如果子问题有两个链表，则正中下怀
否则便以二分的方式去划分子问题，直到子问题满足上述情况

private ListNode partition(ListNode[] lists, int l, int r) {
    if (l > r) return null;
    if (l == r) return lists[l];
    if (l + 1 == r) return mergeTwo(lists[l], lists[r]);
    int mid = (l + r) >> 1;
    return mergeTwo(partition(lists, l, mid), partition(lists, mid + 1, r));
}

2、题目二：LeetCode 241 为运算表达式设计优先级
这里的分治便相当于给原式子加括号，哪一段应该先算？怎么去找子问题呢？
对于这个case：“2-1-1”，有两个答案：(2-1)-1 = 0 ，2-(1-1) = 2
不难看出，每一段子问题的分隔符是操作符'+'，'-'，'*'。操作符左侧和右侧都是子问题的字符串。
那么最小子问题便是“没有操作符的纯数字字符串”，所以利用递归便能完成
分别求得操作符左右两侧字符串的所有结果（allRes），再依据当下的操作符'+'，'-'，'*'进行加减乘
1）解决最小子问题（伪代码）

// 如果String s没有operator，也即最小子问题
if (the amount of operator in s is 0)
    return Integer.parseInt(s);

2）划分子问题
划分子问题时恰好可以一起解决最小子问题

private List<Integer> dealWithString(String expression, int l, int r) {
    List<Integer> allRes = new ArrayList<>(); // 对于一个式子可能产生多个答案
    for (int i = l; i <= r; i++) {
        char c = expression.charAt(i);
        if (!Character.isDigit(c)) {
            int res = 0;
            List<Integer> former = dealWithString(expression, l, i - 1);
            List<Integer> latter = dealWithString(expression, i + 1, r);
            for (int fst : former)
                for (int sec : latter) {
                    if (c == '+') allRes.add(fst + sec);
                    else if (c == '-') allRes.add(fst - sec);
                    else allRes.add(fst * sec);
                }
        }
    }
    // 如果这一段没有operator
    if (allRes.size() == 0)
        allRes.add(Integer.parseInt(expression.substring(l, r + 1)));
    return allRes;
}

3、题目三：LeetCode 105 从前序与中序遍历序列构造二叉树

// 把数组分段创建二叉树
// l1,r1为preorder对应的一段，l2,r2为inorder相应的一段
private TreeNode create(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {
    // 终止条件
    if (l1 > r1)
        return null;
    // 找到中序中root的位置
    int rootindex = l2;
    while (inorder[rootindex] != preorder[l1]) // 前序数组中，首位置l1是root
        rootindex++;
    // preorder = [root | left | right]，inorder = [left | root | right]
    // 由于我们知道了rootindex，可以借助inorder的l2,r2来推出left的长度和right的长度
    // left：inorder中从l2 ~ (rootindex - 1)，长度为 rootindex - l2
    	// 于是preorder中从(l1 + 1) ~ (l1 + rootindex - l2)
   	// right：inorder中从(rootindex + 1) ~ r2
   		// preorder中right在left的右侧，从(l1 + rootindex - l2 + 1) ~ r1
    TreeNode node = new TreeNode(preorder[l1]); // 我是谁？
    // 左儿子是谁？
    node.left = create(preorder, inorder, l1 + 1, l1 + rootindex - l2, l2, rootindex - 1);
    // 右儿子是谁？
    node.right = create(preorder, inorder, l1 + rootindex - l2 + 1, r1, rootindex + 1, r2);
    return node;
}

4、实战题目：
常规思路类：
LeetCode 14 最长公共前缀
 LeetCode 22 括号生成
 LeetCode 282 给表达式添加运算符
 LeetCode 493 翻转对
排序类：
LeetCode 912 排序数组
 LeetCode 148 排序链表
树类：
LeetCode 108 将有序数组转换为二叉搜索数
 LeetCode 106 从中序与后序遍历序列构造二叉树

二、局部分治

局部分治类似于全局分治的剪枝，也可以理解成定向的分治，从全局的状态空间中寻找到涵盖目标的子问题，舍弃掉非目标的子问题。
1、题目一：LeetCode 215 数组中的第K个最大元素
利用快排思想，可以很轻松的返回已排好序的数组，任意大小的元素都能找到，这是基于全局分治。
快排的也是基于分治思想，找到pivot并确定其在数组中的最终位置，递归的对其左侧和右侧排序。

局部分支——快排思维找第K大元素
但我们会发现，其实我们不需要将所有数都排一遍。可以根据k的大小，和pivot在数组中的位置推导出应该往哪边递归，而另一边是一定得不到答案的，所以直接舍弃。
如上图，若寻找第2大元素，只需向右分治递归而舍弃左侧，若寻找第6大元素，只需向左分治而舍弃右侧。
所以子问题便是不断地缩小搜素范围去找到第K大元素，最小子问题就是当长度为1时。

private int partition(int[] nums, int k, int l, int r) {
    if (l == r) return nums[l];
    int pivot = nums[(l + r) >> 1];
    int i = l, j = r;
    while (i < j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i == j) break;
        if (nums[i] == nums[j]) {
            i++;
            continue;
        }
        swap(nums, i, j);
    }
    // 若此时i停在pivot的正确位置
    if (i == nums.length - k) return nums[i];
    if (i < nums.length - k)
        return partition(nums, k, i + 1, r); // 向右
    else
        return partition(nums, k, l, i - 1); // 向左
}

private void swap(int[] nums, int l, int r) {
    int tmp = nums[l];
    nums[l] = nums[r];
    nums[r] = tmp;
}

2、题目二：LeetCode 50 Pow(x, n)
局部分治在这题上可以帮助去冗，若第一次遇见此类题可能不好想到分治。

// 伪代码
if (n is even number) // 偶数
	return pow(x, n / 2) * pow(x, n / 2);
else // 奇数
	return pow(x, n / 2) * pow(x, n / 2) * x;

会发现，通过将n区分奇偶性完成分治，并且将pow(x, n / 2)存储起来，可以减少一半的计算，也算是局部分治了。
则最小子问题就是当n为0时返回1.
有了这个想法，代码就十分好写了，注意一下定义域即可

public double myPow(double x, int n) {
    // 终止条件
    if (n == 0)
        return 1;
    if (n == Integer.MIN_VALUE) // 特殊处理非对称的定义域
        return 1 / (myPow(x, Integer.MAX_VALUE) * x);
    if (n < 0)
        return 1 / myPow(x, -n);
    // 分治
    double half = myPow(x, n / 2);
    if (n % 2 == 0)
        return half * half;
    else
        return half * half * x;
}