Leetcode按题目类型总结(十四)

分治法

Posted by Jingming on January 3, 2018

所有代码详见: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结尾的情况加入结果返回给上一层。