算法学习——分治

分治算法的经典算法,如归并排序、快速排序、最大子段和问题等,以及一些力扣练习题。

分治

经典算法

数字旋转方阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static int[][] Full(int[][] data, int number, int begin, int size) {// 从number开始填写size阶方阵,左上角下标为(begin,begin)
int i, j, k;
if (size == 0)// 递归边界,若size为0则无需填写
return data;
if (size == 1) {// 递归边界,若size为1
data[begin][begin] = number;// 则只需填写number
return data;
}
i = begin;
j = begin;
for (k = 0; k < size - 1; k++) {
data[i][j] = number;
number++;
i++;// 往下移动
}
for (k = 0; k < size - 1; k++) {
data[i][j] = number;
number++;
j++;// 往右移动
}
for (k = 0; k < size - 1; k++) {
data[i][j] = number;
number++;
i--;// 往上移动
}
for (k = 0; k < size - 1; k++) {
data[i][j] = number;
number++;
j--;// 往左移动
}
Full(data, number, begin + 1, size - 2);// 递归填写除最外面一圈的部分

return data;
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void Merge(int[] r, int[] res, int start, int mid, int end) {
int i = start, j = mid + 1, k = start;
while (i <= mid && j <= end) {
if (r[i] <= r[j]) {
res[k++] = r[i++];
} else {
res[k++] = r[j++];
}
}
while (i <= mid) {
res[k++] = r[i++];
}
while (j <= end) {
res[k++] = r[j++];
}
}

public static void Sort(int[] r, int start, int end) {
int mid;
int[] temp = new int[r.length];
if (start == end) return;
else {
mid = (start + end) / 2;
Sort(r, start, mid);
Sort(r, mid + 1, end);
Merge(r, temp, start, mid, end);
for (int i = start; i <= end; i++) {
r[i] = temp[i];
}
}
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public static int Partition(int[] r, int low, int high) {
int i = low, j = high;
while (i < j) {
while (i < j && r[i] <= r[j]) {
j--;
}
if (i < j) {
int temp = r[i];
r[i] = r[j];
r[j] = temp;
}
while (i < j && r[i] <= r[j]) {
i++;
}
if (i < j) {
int temp = r[i];
r[i] = r[j];
r[j] = temp;
j--;
}
}
return i;
}

public static void Sort(int[] r, int low, int high) {
int pivot;
if (low < high) {
pivot = Partition(r, low, high);
Sort(r, low, pivot - 1);
Sort(r, pivot + 1, high);
}
}

最大子段和问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int MaxSum(int[] a, int left, int right) {
int sum = 0, midSum = 0, leftSum = 0, rightSum = 0;
int center, s1, s2, lefts, rights;
if (left == right)// 若序列长度为1,则直接求解
sum = a[left];
else {
center = (left + right) / 2;// 从中间划分
leftSum = MaxSum(a, left, center);// 情况①,最大和在左半部分,递归求解
rightSum = MaxSum(a, center + 1, right);// 情况②,最大和在右半部分,递归求解
s1 = 0;
lefts = 0;// 以下为情况③,组成最大和的元素跨越中轴线
for (int i = center; i >= left; i--) {// 先求解s1
lefts += a[i];// 指针向左运动并累加
if (lefts > s1)// 遇到负数会导致lefts变小,故不会赋值给s1
s1 = lefts;
}
s2 = 0;
rights = 0;
for (int j = center + 1; j <= right; j++) {// 再求解s2
rights += a[j];// 指针向右运动并累加
if (rights > s2)// 遇到负数会导致rights变小,故不会赋值给s2
s2 = rights;
}
midSum = s1 + s2;// 计算情况③的最大子段和
sum = Math.max(Math.max(midSum, leftSum), rightSum);// 三者取最大
}

return sum;
}

棋盘覆盖问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* @param board 棋盘
* @param tr 棋盘左上角的行标
* @param tc 棋盘左上角的列标
* @param dr 特殊方块的行标
* @param dc 特殊方块的列标
* @param size 棋盘的阶数
* @return 骨牌放置的结果
*/
public static int[][] ChessBoard(int[][] board, int tr, int tc, int dr, int dc, int size) {
int s, t1;// t1表示本次覆盖使用的L型骨牌编号
if (size == 1)
return board;
t1 = ++t;
s = size / 2;// 划分
// 处理左上角子棋盘
if (dr < tr + s && dc < tc + s) {// 若特殊方格在左上角的子棋盘中
board = ChessBoard(board, tr, tc, dr, dc, s);// 递归处理
} else {// 否则用t1号骨牌覆盖右下角,再递归处理子棋盘
board[tr + s - 1][tc + s - 1] = t1;
board = ChessBoard(board, tr, tc, tr + s - 1, tc + s - 1, s);
}
// 处理右上角子棋盘
if (dr < tr + s && dc >= tc + s) {// 若特殊方格在右上角的子棋盘中
board = ChessBoard(board, tr, tc + s, dr, dc, s);// 递归处理
} else {// 否则用t1号骨牌覆盖左下角,再递归处理子棋盘
board[tr + s - 1][tc + s] = t1;
board = ChessBoard(board, tr, tc + s, tr + s - 1, tc + s, s);
}
// 处理左下角子棋盘
if (dr >= tr + s && dc < tc + s) {// 若特殊方格在左下角的子棋盘中
board = ChessBoard(board, tr + s, tc, dr, dc, s);// 递归处理
} else {// 否则用t1号骨牌覆盖右上角,再递归处理子棋盘
board[tr + s][tc + s - 1] = t1;
board = ChessBoard(board, tr + s, tc, tr + s, tc + s - 1, s);
}
// 处理右下角子棋盘
if (dr >= tr + s && dc >= tc + s) {// 若特殊方格在右下角的子棋盘中
board = ChessBoard(board, tr + s, tc + s, dr, dc, s);// 递归处理
} else {// 否则用t1号骨牌覆盖左上角,再递归处理子棋盘
board[tr + s][tc + s] = t1;
board = ChessBoard(board, tr + s, tc + s, tr + s, tc + s, s);
}
return board;
}

最近对问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public static double Closest(Point[] S, int low, int high) {
double d1, d2, d3, d;
int mid, i, j, index;
Point[] P = new Point[S.length]; //存放点集P1和P2
if (high - low == 1) //只有两个点
return Distance(S[low], S[high]);
if (high - low == 2) { //只有三个点
d1 = Distance(S[low], S[low + 1]);
d2 = Distance(S[low + 1], S[high]);
d3 = Distance(S[low], S[high]);
if ((d1 < d2) && (d1 < d3))
return d1;
else if (d2 < d3)
return d2;
else
return d3;
}

mid = (low + high) / 2; //计算中间点
d1 = Closest(S, low, mid); //递归求解子问题①
d2 = Closest(S, mid + 1, high); //递归求解子问题②
d = Math.min(d1, d2); //一下求解子问题③
index = 0;
for (i = mid; (i >= low) && (S[mid].getX() - S[i].getX() < d); i--) { //建立点集P1
P[index++] = S[i];
}
for (i = mid + 1; (i <= high) && (S[i].getX() - S[mid].getX() < d); i++) { //建立点集P2
P[index++] = S[i];
}
PointQuickSort.Sort(P, 0, index - 1);//将集合P1和P2按y坐标升序排列
for (i = 0; i < index; i++) {
for (j = i + 1; j < index; j++) {
if (P[j].getY() - P[i].getY() >= d)
break;
else {
d3 = Distance(P[i], P[j]);
if (d3 < d) d = d3;
}
}
}
return d;
}

public static double Distance(Point a, Point b) {
return Math.sqrt(Math.pow(a.getX() - b.getX(), 2) + Math.pow(a.getY() - b.getY(), 2));
}

凸包问题(待解决)

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public class Status {
public int lSum, rSum, mSum, iSum;

public Status(int lSum, int rSum, int mSum, int iSum) {
this.lSum = lSum;
this.rSum = rSum;
this.mSum = mSum;
this.iSum = iSum;
}
}

public int maxSubArray(int[] nums) {
return getInfo(nums, 0, nums.length - 1).mSum;
}

public Status getInfo(int[] a, int l, int r) {
if (l == r) {
return new Status(a[l], a[l], a[l], a[l]);
}
int m = (l + r) >> 1;
Status lSub = getInfo(a, l, m);
Status rSub = getInfo(a, m + 1, r);
return pushUp(lSub, rSub);
}

public Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = Math.max(l.lSum, l.iSum + r.lSum);
int rSum = Math.max(r.rSum, r.iSum + l.rSum);
int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
return new Status(lSum, rSum, mSum, iSum);
}
}

力扣.108. 将有序数组转换为二叉搜索树

由于数组是按升序排列的,故可将问题划分为子问题,即

  • 取数组中间元素作为根节点。
  • 中间元素左侧的所有元素均为左子树中的元素。
  • 中间元素右侧的所有元素均为右子树中的元素。

以上述方式递归处理左侧和右侧的数组,设置递归边界:

  • end < begin时,说明该侧数组为空,直接返回null。
  • end == begin时,说明该侧数组只有一个元素,直接返回以该元素为根节点的子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public TreeNode sortedArrayToBST(int[] nums) {
if (nums.length == 0)
return null;
return Solution(nums, 0, nums.length - 1);
}

public TreeNode Solution(int[] nums, int begin, int end) {
if (end < begin)
return null;
if (end == begin)
return new TreeNode(nums[begin]);
int mid = (begin + end) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = Solution(nums, begin, mid - 1);
root.right = Solution(nums, mid + 1, end);

return root;
}

力扣.169. 多数元素

如果数 a 是数组 nums 的众数,如果我们将 nums 分成两部分,那么 a 必定是至少一部分的众数。

证明:

  • 假设a既不是左半部分的众数,也不是右半部分的众数。
  • 那么a出现的次数少于 L / 2 + R / 2 次,其中LR分别是左半部分和右半部分的长度。
  • 由于L / 2 + R / 2 <= (L + R) / 2,说明a也不是数组nums的众数,因此出现了矛盾。
  • a必定是至少一部分的众数。

拆分子问题,将数组分为左右两部分:

  • 左侧众数若与右侧众数相同,则众数为该数。
  • 左侧众数若与右侧众数不同,则需要分别统计这两个数在左右两部分中的总共出现的次数,次数大者为众数。

递归边界:当区间长度为1时,该数即为众数,直接返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int majorityElement(int[] nums) {
return Solution(nums, 0, nums.length - 1);
}


public int Solution(int[] nums, int low, int high) {
if (low == high) return nums[low];
int mid = (low + high) / 2;
int left = Solution(nums, low, mid);
int right = Solution(nums, mid + 1, high);
if (left == right) return left;

int leftC = Count(nums, left, low, high);
int rightC = Count(nums, right, low, high);
return leftC > rightC ? left : right;
}


public int Count(int[] nums, int num, int low, int high) {
int count = 0;
for (int i = low; i <= high; i++)
if (nums[i] == num) count++;
return count;
}

力扣.190. 颠倒二进制位

若要翻转一个二进制串,可以将其均分成左右两部分,对每部分递归执行翻转操作,然后将左半部分拼在右半部分的后面,即完成了翻转。

由于左右两部分的计算方式是相似的,利用位掩码和位移运算,我们可以自底向上地完成这一分治流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
private static final int M1 = 0x55555555; // 01010101010101010101010101010101
private static final int M2 = 0x33333333; // 00110011001100110011001100110011
private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111

public static int reverseBits(int n) {
n = n >>> 1 & M1 | (n & M1) << 1;// 奇偶位互换
n = n >>> 2 & M2 | (n & M2) << 2;// 每两位互换
n = n >>> 4 & M4 | (n & M4) << 4;// 每四位互换
n = n >>> 8 & M8 | (n & M8) << 8;// 每八位互换

return n >>> 16 | n << 16;// 最终将左右两半部分互换
}
作者

亦初

发布于

2022-03-13

更新于

2024-06-19

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...