分治算法

分治算法基础

分治算法的思想

1. 分解：将问题分解成若干个规模较小的子问题
2. 解决：递归地解决各个子问题
3. 合并：将子问题的解合并成原问题的解

分治算法模板

public Result divideAndConquer(Problem problem) {
    // 递归终止条件
    if (problem.size() <= threshold) {
        return solveDirect(problem);
    }

    // 分解
    List<Problem> subProblems = divide(problem);

    // 递归解决子问题
    List<Result> subResults = new ArrayList<>();
    for (Problem subProblem : subProblems) {
        subResults.add(divideAndConquer(subProblem));
    }

    // 合并结果
    return merge(subResults);
}

经典题目

归并排序

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 分解
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    System.arraycopy(temp, 0, arr, left, temp.length);
}

快速排序

public void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        // 分解
        int pivot = partition(arr, left, right);

        // 递归解决
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, right);
    return i + 1;
}

最大子数组和（LeetCode 53）

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

private int divideAndConquer(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }

    int mid = left + (right - left) / 2;

    // 分解
    int leftMax = divideAndConquer(nums, left, mid);
    int rightMax = divideAndConquer(nums, mid + 1, right);

    // 跨越中点的最大子数组
    int crossMax = crossSum(nums, left, right, mid);

    // 合并
    return Math.max(Math.max(leftMax, rightMax), crossMax);
}

private int crossSum(int[] nums, int left, int right, int mid) {
    int leftSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }

    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }

    return leftSum + rightSum;
}

为运算表达式设计优先级（LeetCode 241）

public List<Integer> diffWaysToCompute(String expression) {
    List<Integer> result = new ArrayList<>();

    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);

        if (c == '+' || c == '-' || c == '*') {
            // 分解
            List<Integer> left = diffWaysToCompute(expression.substring(0, i));
            List<Integer> right = diffWaysToCompute(expression.substring(i + 1));

            // 合并
            for (int l : left) {
                for (int r : right) {
                    if (c == '+') {
                        result.add(l + r);
                    } else if (c == '-') {
                        result.add(l - r);
                    } else {
                        result.add(l * r);
                    }
                }
            }
        }
    }

    // 递归终止条件
    if (result.isEmpty()) {
        result.add(Integer.parseInt(expression));
    }

    return result;
}

不同的二叉搜索树II（LeetCode 95）

public List<TreeNode> generateTrees(int n) {
    if (n == 0) return new ArrayList<>();
    return generate(1, n);
}

private List<TreeNode> generate(int start, int end) {
    List<TreeNode> result = new ArrayList<>();

    if (start > end) {
        result.add(null);
        return result;
    }

    for (int i = start; i <= end; i++) {
        // 分解
        List<TreeNode> leftTrees = generate(start, i - 1);
        List<TreeNode> rightTrees = generate(i + 1, end);

        // 合并
        for (TreeNode left : leftTrees) {
            for (TreeNode right : rightTrees) {
                TreeNode root = new TreeNode(i);
                root.left = left;
                root.right = right;
                result.add(root);
            }
        }
    }

    return result;
}

练习题

1. 数组中的逆序对（剑指Offer 51）
2. 计算右侧小于当前元素的个数（LeetCode 315）
3. 搜索二维矩阵II（LeetCode 240）
4. 多数元素（LeetCode 169）
5. Pow(x, n)（LeetCode 50）