算法学习——分治

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

分治

经典算法

数字旋转方阵

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;
}

归并排序

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];
        }
    }
}

快速排序

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);
    }
}

最大子段和问题

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;
}

棋盘覆盖问题

/**
 * @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;
}

最近对问题

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));
}

凸包问题（待解决）

练习

力扣.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，三者取大。

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时，说明该侧数组只有一个元素，直接返回以该元素为根节点的子树

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 次，其中L和R分别是左半部分和右半部分的长度。
• 由于L / 2 + R / 2 <= (L + R) / 2，说明a也不是数组nums的众数，因此出现了矛盾。
• 故a必定是至少一部分的众数。

拆分子问题，将数组分为左右两部分：

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

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

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. 颠倒二进制位

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

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

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;// 最终将左右两半部分互换
}