分而治之算法
分而治之是算法设计中的一种方法,算法的一种设计思想。它将一个问题分成多个和原问题相似的小问题,递归解决小问题,再将结果合并一解决原来的问题。
使用场景一: 归并排序
分:把数组从中间一分为二。
解:递归地对两个子数组进行归并排序。
合:合并有序子数组。
使用场景二: 快速排序
分:选基准,按基准把数组分成两个子数组。
解:递归地对两个子数组进行快速排序。
合:对两个子数组进行合并。
举例算法题一:猜数字大小
猜数字游戏的规则如下:
每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):
-1:我选出的数字比你猜的数字小 pick < num 1:我选出的数字比你猜的数字大 pick > num
0:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num
返回我选出的数字。
示例 1:
输入:n = 10, pick = 6
输出:6
示例 2:
输入:n = 1, pick = 1
输出:1
示例 3:
输入:n = 2, pick = 1
输出:1
示例 4:
输入:n = 2, pick = 2
输出:2
提示:
1 <= n <= 2^31 – 1
1 <= pick <= n
解题思路
分:计算中间元素,分割数组。
解:递归地在较大或者较小数组进行二分搜索。
合:不需要此步,因为在子数组中搜到就返回了。
解题答案
var guessNumber = function(n){
const rec = (low,high) =>{
if(low > high){ return }
const mid = Math.floor((low+high) / 2);
const res = guess(mid);
if(res === 0){
return mid;
}else if(res === 1){
return rec(mid + 1,high);
}else{
return rec(1, mid - 1);
}
}
return rec(1,n);
}
解题分析
时间复杂度 O(logn),空间复杂度 O(logn)
举例算法题二:翻转二叉树
翻转一棵二叉树。
示例:
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
解题思路:
- 先反转左右子树,再将子树换个位置。
- 符合“分、解、和”特性。
- 考虑用分而治之来做。
解题步骤:
分:获取左右子树。
解:递归地翻转左右子树。
合:将翻转后的左右子树换个位置放到根节点上。
解题答案:
var invertTree = function(root){
if(!root){ return null; }
return {
val: root.val,
left: invertTree(root.right),
right: invertTree(root.left)
}
}
解题分析:
时间复杂度O(n),空间复杂度 O(n)。
举例算法题三:相同的树
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3] 输出:true
示例 2:
输入:p = [1,2], q = [1,null,2] 输出:false
示例 3:
输入:p = [1,2,1], q = [1,1,2] 输出:false
提示:
- 两棵树上的节点数目都在范围
[0, 100]
内 -104 <= Node.val <= 104
解题思路:
- 两棵树:根节点的值相同,左子树相同,右子树相同
- 符合“分、解、和”特性。
- 考虑用分而治之来做。
解题步骤:
分:获取两个树的左子树和右子树。
解:递归地判断两个数的左子树是否相同,右子树是否相同。
合:将上述结果合并,如果根节点的值也相同,树就相同。
解题答案:
var inSameTree = function(p,q){
if(!p && !q){ return true} //如果两个都为空
if( p && q && p.val === q.val &&
inSameTree(p.left,q.left )&&
inSameTree(p.right,q.right)
){
return true;
}
return false;
}
举例算法题四:对称二叉树
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3]
是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3]
则不是镜像对称的:
1
/ \
2 2
\ \
3 3
解题思路:
- 转化为:左右子树是否镜像。
- 分解为:树1的左子树和树2的右子树是否镜像,树1的右子树和树2的左子树是否镜像。
- 符合“分、解、和”特性,考虑用分而治之来做。
解题步骤:
分:获取两个树的左子树和右子树。
解:递归地判断树1的左子树和树2的右子树是否镜像,树1的右子树和树2的左子树是否镜像。
合:如果上述都成立,且根节点值也相同,两个树就镜像。
解题答案:
var isSymmetric = function(root){
if(!root) return true;
const isMirror = (l, r) => {
if(!l && !r) return true;
if(l && r && l.val === r.val &&
isMirror(l.left, r.right)&&
isMirror(l.right, r.left)
){
return true;
}
return false;
}
return isMirror(root.left, root.right);
}
解题分析:
时间复杂度O(n),空间复杂度 O(LogN)和O(n)。