所有代码详见：https://github.com/jingminglake/Leetcode
总体思路
分治法和很多其他题型有交集。
具体题目
4. Median of Two Sorted Arrays
题意：找出两个已排序数组中的总的中位数。中位数在总元素为奇数的时候取中间值，偶数时候取中间两个值的平均值。
解：先想办法求两个已排序数组（假设大小分别为m和n）中的第k小的数的问题。那么此题答案就是总元素为奇数时候的第(m+n)/2 + 1小的数，偶数时候就是第(m+n)/2和第(m+n)/2 + 1小的数的平均值。
求两个已排序数组（假设分别为M和N）中的第k小的数的问题：对于一个排序数组，取出其中的第k小的元素花费时间仅为O（1）。现在假设我们分别取出两个数组中自身第k/2大的元素，那么分别为M[k/2]和N[k/2]，而且我们知道M[k/2]比M中的k/2个元素大，N[k/2]比n中的k/2个元素大。
假设M[k/2] > N[k/2]，那么我们知道M[k/2]比(k/2)+(k/2)，即k个元素大。也就是说，M中比M[k/2]大的元素，也就是M[k/2]后面的元素，都不可能作为答案了。同理，我们知道N[k/2]比总元素个数中的k个元素小，所以答案必定不在N[k/2]之前的元素中。所以答案必介于N[k/2]后面部分和M[k/2]前面部分。 M[k/2] < N[k/2]的情况依次类推。
M[k/2] == N[k/2]，同理分析，发现必介于N[k/2]到M[k/2]，那么就是N[k/2]。
举一个现实中的例子，有两个班级参加了同一门考试，假设我们分别知道了两个班成绩由高到低的排序数组，那么我们快速的求第k名是哪个分数。
假设分数为第一个班[100, 98, 97, 96, 95….]，第二个班分数有些不均匀[100, 99, 70, 60….]，现在假设求第6名是哪个分数。
我们首先看每个班级的第3名。97比70大，那么我们知道，第2个班中70分以下的分数不可能成为第6名，因为最少有6个人比70分高。同理，第一个班中大于等于97分的也不可能是第6名，因为97分必定是最高的5个分数中的一个。理解：第一个班只有2个人比97分数高，如果想要97分为第6名，那么我们得从第二个班找出比97高的3个人，而这个数根本找不到。 现在问题缩减为，第1个班[96, 95….]，第2个班[100, 99, 70]中找出第3名的问题。因为原问题中的前6名中已经有3名被排除。
会遇到的问题：如果是找第7名，那么如何做？此时如果每个班都取第3名，那么只能去除第一个班的前2名，而不能去掉第2班的60分以下的部分。
所以实际编码中，一次只去掉一个数组的前面部分。还有一点，第3名相当于数组下标2。另外，例如找第7名，子问题不是求第3名，而有可能是求第4名。
50. Pow(x, n)
题意：求n次方。
解：此题在于把问题分解小，先自己乘以自己，也就是算自己平方的，次方的一半的问题。 另外注意，次方是负数的时候，变正数可能会越界，所以要使用long型。
140. Word Break II
题意：给出串S，和单词字典，现在求所有可以切分的情况。
解：此题大致解题思路是递归求解：对于一个串s，发现一个可以切分的单词的时候，后面的部分作为相同子问题进行求解，关键的问题是第一个单词怎么找，答案就是：对字典里的每个单词看下是不是可以是当前串的开头。
整个过程中使用记忆化，所以也是一道动态规划题。求解所有可能解的问题的时候，思路就是先看能不能递归，再加记忆化搜索。
214. Shortest Palindrome
题意：在串S之前加最少的字符，使得串S变成回文串。
解：此题第一个发现就是将完整的S加在S之前就可以达到回文串，但是第一个S的结尾和第二个S的开头部分会出现冗余，而且冗余的部分应该是消除第一个S中的后缀部分，而保留第二个的S的前缀部分。现在问题变为：串S的前缀和后缀相等的情况下，最大能达到多长。
首先有一个O(n^2)的解法，贪心的依次看n,n-1,n-2长度情况下的S的前缀和翻转后的S的后缀是否相等，如果相等，那么答案就出来了，这样最坏情况下，要看n次，每次比较是否相等花费n的时间。
还有一个方法是KMP，不写了。 然后答案中还有一个巧妙的解法：递归。首先要知道，S之前的加串的话，一定加的是S的后缀的翻转，也就是说：问题可以转化为把S分为两段，然后后面一部分，也就是后缀，翻转之后放到整个S的前面，然后剩余的前一半部分作为子问题进行相同的操作。现在的问题是怎么切分成两段：可以使用双指针，一开始分别指向头尾，如果相等，两指针往中间走，否则只走右指针，找到第一个不等的字符对，那么左指针就是切分点，左指针之后的后缀部分是一定需要翻转到前面的不重复部分，也是最长的不存在相同前缀的后缀，不可能存在被之后的子问题干扰形成回文串的情况。
395. Longest Substring with At Least K Repeating Characters
题意：求最长子串，子串中每个字符的出现次数至少是k。
解：分治法：先统计每个字符的出现次数，如果某个字符总数不足k个，那么任何substring都不可能包含该字符，就可以把问题分解成两半。时间复杂度O(nlogn)。还可以跳过开头和结尾,开头结尾如果字符都不足K个，其实都可以跳过。初始情况就是：存在一段区间，里面出现的字符都比k个多，不能被分割。
一种双指针解法：假设对最终答案的独特字符做出数量限制，那么最终答案一定在包含1个到包含26个独特字符之间。
然后对每种独特字符，可以使用同向双指针进行O(n)求解出最长串。
还有一种双指针解法：首先固定left，把right从左到右扫一遍，记录下最后一个合法的位置last，那么下一次扫描时，left直接跳到上一步最后合法位置last的下一个位置就可以了。
这么跳过的原理就是最后一个合法位置last的下一个字符肯定是之前从来没有出现的字符，这样，增加left的时候，left小于last的情况下，left开头的字符不存在跨过last字符组成更长子串的可能，因为left移动时候，减少了一个字符，且与last指向的字符无关，根本消除不了没有last字符带来的负面效果。
而且此方法还可以使用一个技巧来时刻判断当前窗口是不是合法的：那就是使用mask，参考http://www.cnblogs.com/grandyang/p/5852352.html
222. Count Complete Tree Nodes
题意：求完全二叉树结点总数。要求时间复杂度低于O(n)。
解：此题技巧在于分治，利用完全二叉树的性质，发现完全二叉树的左子树如果比右子树高1，那么右子树是一颗满二叉树，左子树是一颗完全二叉树，这样问题减半，因为右边满二叉树直接使用公式计算出结点总数。如果左右子树高度相同，那么说明左子树是一颗满二叉树，右子树是一颗完全二叉树。
注意：完全二叉树高度是可以logn时间求出来的。一般二叉树需要n时间求出来。
247. Strobogrammatic Number II
题意：给出数字的位数n，求满足该位数的Strobogrammatic数（旋转180度相等）
解：此题边界情况非常多，例如，数字不能以0开头，如果是奇数的时候，奇数的中心元素 可以选0， 1， 8。此外的其他数字，只能从0，1，6，8，9中选。
此题可以递归来解，要求解位数n，先求解位数n-1，…递归到n = 2， n = 1, n = 0的情况。
n = 0的时候，就是{}。
n = 1的时候，就是{0， 1， 8}。
n = 2的时候，就是{11, 69, 88, 96}。
n = 3的时候，中间就是n = 1子问题，分为四种情况，（1）以1开头，1结尾，（2）6开头，9结尾； （3）8开头，8结尾；（4）9开头，6结尾。
n = 4的时候，中间是n = 2的子问题，但是注意的是n = 2的子问题并没有考虑0开头结尾的情况。
此时，就需要在 n = 2的结果上加入以0开头，0结尾的情况。
n = 5的时候，中间是n = 3的子问题，但是注意的是n = 3的子问题并没有考虑0开头结尾的情况。
此时，就需要在n = 3的结果上加入以0开头，0结尾的情况。
也就是说，如果处理的不是最后一层n的时候，需要考虑以0开头，0结尾的情况加入结果返回给上一层。
