算法学习——分治
分治算法的经典算法,如归并排序、快速排序、最大子段和问题等,以及一些力扣练习题。
分治
经典算法
数字旋转方阵
1 |
|
归并排序
1 |
|
快速排序
1 |
|
最大子段和问题
1 |
|
棋盘覆盖问题
1 |
|
最近对问题
1 |
|
凸包问题(待解决)
1 |
|
练习
力扣.53. 最大子数组和
定义一个操作get(a,l,r)
表示查询a序列[l,r]区间内的最大子段和,则最终答案就是get(nums,0,nums.length-1)
。
对于区间[l,r]
,取\(m=\lfloor\frac{l+r}{2}\rfloor\),对区间[l,m]
和[m+1,l]
分治求解,当递归逐层深入到区间长度为1时,递归开始回升。
对于区间[l,r]
维护四个量:
lSum
表示[l,r]
内以l为左端点的最大子段和。rSum
表示[l,r]
内以l为右端点的最大子段和。mSum
表示[l,r]
内的最大子段和。iSum
表示[l,r]
的区间和。
对于长度为1的区间[i,i]
,上述四个量均与nums[i]
相等。
对于长度大于1的区间:
iSum
最好维护,区间[l,r]
的iSum
就等于左子区间的iSum
加右子区间的iSum
。lSum
存在两种可能,要么等于左子区间的lSum
,要么等于左子区间的iSum
+右子区间的lSum
,二者取大。rSum
同理,要么等于右子区间的rSum
,要么等于右子区间的iSum
+左子区间的rSum
,二者取大。mSum
同样有两种情况,一是[l,r]
的mSum
对应的区间不跨越m,则[l,r]
的mSum
可能是左子区间和右子区间的mSum
中的一个,二是[l,r]
的mSum
对应的区间跨越m,则可能是左子区间的rSum
+右子区间的lSum
,三者取大。
1 |
|
力扣.108. 将有序数组转换为二叉搜索树
由于数组是按升序排列的,故可将问题划分为子问题,即
- 取数组中间元素作为根节点。
- 中间元素左侧的所有元素均为左子树中的元素。
- 中间元素右侧的所有元素均为右子树中的元素。
以上述方式递归处理左侧和右侧的数组,设置递归边界:
- 当
end < begin
时,说明该侧数组为空,直接返回null。 - 当
end == begin
时,说明该侧数组只有一个元素,直接返回以该元素为根节点的子树
1 |
|
力扣.169. 多数元素
如果数 a
是数组 nums
的众数,如果我们将
nums
分成两部分,那么 a
必定是至少一部分的众数。
证明:
- 假设
a
既不是左半部分的众数,也不是右半部分的众数。 - 那么
a
出现的次数少于L / 2 + R / 2
次,其中L
和R
分别是左半部分和右半部分的长度。 - 由于
L / 2 + R / 2 <= (L + R) / 2
,说明a
也不是数组nums
的众数,因此出现了矛盾。 - 故
a
必定是至少一部分的众数。
拆分子问题,将数组分为左右两部分:
- 左侧众数若与右侧众数相同,则众数为该数。
- 左侧众数若与右侧众数不同,则需要分别统计这两个数在左右两部分中的总共出现的次数,次数大者为众数。
递归边界:当区间长度为1时,该数即为众数,直接返回。
1 |
|
力扣.190. 颠倒二进制位
若要翻转一个二进制串,可以将其均分成左右两部分,对每部分递归执行翻转操作,然后将左半部分拼在右半部分的后面,即完成了翻转。
由于左右两部分的计算方式是相似的,利用位掩码和位移运算,我们可以自底向上地完成这一分治流程。
1 |
|