算法设计思想

本章学习要求：掌握蛮力、分治、减治、变治和时空权衡等算法设计思想的特点。

蛮力法-选择排序、冒泡排序

选择排序：每次遍历未排序的整个列表，选择一个最小的与第一卦没有被交换的进行交换，下次从被交换的下一个元素开始遍历。

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {10, 8, 7, 5, 6, 1, 2, 3, 9, 4};
        // 调用选择排序方法
        selectionSort(arr);
    }
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 遍历数组
        for (int i = 0; i < n - 1; i++) {
            // 假设当前索引为最小值的索引
            int minIndex = i;
            // 从 i+1 开始遍历剩余元素，找到最小值的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 如果最小值的索引不是当前索引，交换它们的值
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
}

冒泡排序：从第一个元素开始遍历列表直到不确定位置的最后一个元素，如果相邻元素是逆序则交换位置，每次遍历后，有一个元素会被放到对应的位置上。

public static void bubbleSort(int[] array){
    if(array == null || array.length <= 1){
        return ;
    }
    int n = array.length;
    boolean swapped;
    for(int i = 0; i < n - 1; i++){
        swapped = false;
        for(int j = 0; j < n - 1 - i; j++){
            if(array[j] > array[j + 1]){
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                swapped = true;
            }
        }
        //如果内层循环没有进行交换，说明已经有序
        if(!swapped){
            break;
        }
    }
}

例题1：设计一个蛮力算法对给定的x计算多项式值。

public static void main(String[] args){
    //多项式系数
    int[] nums = {1, 2, 3, 4, 5};
    int x = 2;
    int res = 0;
    for(int i = 0; i < nums.length; i++){
        res += nums[i] * (int)Math.pow(x, i);
    }
    return res;
}

例题2：求一个数组中大小最接近的两个元素的差的算法。

public static void main(String[] args){
    int[] arr = {10, 8, 7, 5, 6, 1, 2, 3, 9, 4};
    Arrays.sort(arr);
    int minDiff = Integer.MAX_VALUE;
    for(int i = 0; i < arr.length - 1; i++){
        int diff = arr[i+1] - arr[i];
        if(diff < minDiff){
            minDiff = diff;
        }
    }
    System.out.println(minDiff);
}

分治法-归并排序、快速排序

将问题实例划分为同一问题的几个较小的实例，对这些较小的实例进行求解，最后合并这些较小问题实例的解得到原问题的解。

  • 问题规模缩小到一定程度就很容易解决
  • 问题能够划分为多个相互独立的子问题

归并排序：将一个需要排序的数组一分为两个子数组，分别对两个子数组进行排序，最后将两个子数组合并。

public class MergeSort {
    // 归并排序的主函数
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }
    // 递归进行归并排序
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            // 对左半部分进行排序
            mergeSort(arr, left, mid, temp);
            // 对右半部分进行排序
            mergeSort(arr, mid + 1, right, temp);
            // 合并两个有序的子数组
            merge(arr, left, mid, right, temp);
        }
    }
    // 合并两个有序的子数组
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 左子数组的起始索引
        int j = mid + 1; // 右子数组的起始索引
        int k = left; // 临时数组的起始索引
        // 比较左右子数组的元素，将较小的元素放入临时数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 将左子数组中剩余的元素复制到临时数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 将右子数组中剩余的元素复制到临时数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 将临时数组中的元素复制回原数组
        for (k = left; k <= right; k++) {
            arr[k] = temp[k];
        }
    }
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
        System.out.println("排序前的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        mergeSort(arr);
        System.out.println("\n排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

快速排序：通过选择一个基准元素（pivot），将数组分为两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于等于基准元素，然后分别对左右两部分递归地进行快速排序，最终得到一个有序的数组。

public class QuickSort {
    // 快速排序的主函数
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    // 递归进行快速排序
    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            // 分区操作，获取基准元素的最终位置
            int pivotIndex = partition(arr, left, right);
            // 对基准元素左边的子数组进行排序
            quickSort(arr, left, pivotIndex - 1);
            // 对基准元素右边的子数组进行排序
            quickSort(arr, pivotIndex + 1, right);
        }
    }
    // 分区操作
    private static 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++;
                // 交换 arr[i] 和 arr[j]
                swap(arr, i, j);
            }
        }
        // 将基准元素放到正确的位置
        swap(arr, i + 1, right);
        return i + 1;
    }
    // 交换数组中两个元素的位置
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2, 7, 1, 6};
        System.out.println("排序前的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        quickSort(arr);
        System.out.println("\n排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

例题1：有一个由 N 个实数构成的数组，如果一对元素 A[i] 和 A[j] 是倒序的，即 i < j 但是 A[i] > A[j] 则称它们是一个倒置，设计一个计算该数组中所有倒置数量的算法。要求算法复杂度为 O(nlogn)。

public class InversionCount {
    public static int countInversions(int[] arr) {
        int[] temp = new int[arr.length];
        return mergeSortAndCount(arr, temp, 0, arr.length - 1);
    }
    private static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
        int invCount = 0;
        if (left < right) {
            // 计算中间索引
            int mid = (left + right) / 2;
            // 递归统计左子数组的倒置数量
            invCount += mergeSortAndCount(arr, temp, left, mid);
            // 递归统计右子数组的倒置数量
            invCount += mergeSortAndCount(arr, temp, mid + 1, right);
            // 合并两个子数组并统计跨越两个子数组的倒置数量
            invCount += mergeAndCount(arr, temp, left, mid, right);
        }
        return invCount;
    }
    private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left; // 左子数组的起始索引
        int j = mid + 1; // 右子数组的起始索引
        int k = left; // 临时数组的起始索引
        int invCount = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                // 如果 arr[i] > arr[j]，则 arr[i...mid] 中的所有元素都与 arr[j] 构成倒置
                temp[k++] = arr[j++];
                invCount += (mid - i + 1);
            }
        }
        // 将左子数组中剩余的元素复制到临时数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 将右子数组中剩余的元素复制到临时数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 将临时数组中的元素复制回原数组
        for (i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
        return invCount;
    }
}

减治法-插入排序

利用一个问题给定实例的解和同样问题较小实例的解之间的某种关系，将一个大规模的问题逐步化简为一个小规模的问题。
减治法和分治法的区别和联系：

  • 分治：是多个小问题，小问题之间的联系
  • 减治：还是一个小问题，小问题与原问题之间的联系

插入排序：假设前 n - 1 个元素以已经排序好了，如何将最后一个元素插入到其他元素中去的问题。

public static void insertionSort(int[] arr) {
    int n = arr.length;
    // 从第二个元素开始，依次将每个元素插入到前面已排序的部分
    for (int i = 1; i < n; i++) {
        // 提取当前要插入的元素
        int key = arr[i];
        int j = i - 1;
        // 将比 key 大的元素往后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 将 key 插入到正确的位置
        arr[j + 1] = key;
    }
}

例题1：N 个士兵过又宽又深的河，没有桥，不用船就会牺牲；发现有 2 个小朋友在划船，但是这个船只能搭两个小朋友或 1 个士兵，如何过河？需要来回多少次？

每次只能容纳一名士兵，所以士兵一定是一个一个过河，同时需要有小男孩将船划回来，那么每一次士兵过河之前，两个小男孩先划船过去对岸，然后留下一个小男孩在对岸，另一个小男孩划船回来。接着一个士兵过河，另一个小男孩在士兵过河之后把船划回来。然后继续重复，两个小男孩划船过去对岸……所以摆渡 n 个士兵，需要执行这样的步骤 n 次，每次船在岸与岸之间横渡 4 次，共 4n 次。

例题2：有 2n 个玻璃杯挨个排成一排，前 n 个装满苏打水，其余n个杯子为空。请交换杯子位置，使得按照满-空-满-空-满…的顺序排放。要求交换次数最少。

n 为奇数的时候，空杯从第二个开始，每隔一个满杯与之交换；n 为偶数的时候，空杯从第一个开始，每隔一个满杯与之交换。

例题3：设计一个减一算法，生成一个 n 个元素集合的幂集（集合 S 的幂集是 S 的所有子集的集合，包括空集和 S 本身）。

减一算法是一种迭代算法，它通过移除集合中的一个元素来生成子集。减一算法的基本思想是通过二进制数的所有可能组合来表示集合的所有子集。对于一个具有 n 个元素的集合，其幂集的元素个数为 2^n，可以用从 0 到 2^n - 1 的二进制数来表示每个子集，其中二进制数的每一位对应集合中的一个元素，如果该位为 1，则表示该元素在子集中，否则不在子集中。

例题4：Shell排序，它是插入排序的一种更高效的改进版本，也称为缩小增量排序。它的基本思想是将原始数据分成多个子序列来进行插入排序，通过逐渐缩小子序列的间隔（增量），最终使整个序列基本有序，最后进行一次整体的插入排序。

public static void shellSort(int[] arr) {
    int n = arr.length;
    // 初始化增量为序列的一半长度
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列进行插入排序
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            // 对当前子序列进行插入排序
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

变治法-预排序

通过转换问题使得原问题更容易求解。
预排序：一种变治的思想，先对输入列表进行排序，再求解原问题。
例题1：有 n 个数字构成的一个数组和一个整数 s，如何最快确定数组中是否存在两个数的和恰好等于 s。

public class TwoSumWithSorting {
    public static boolean hasTwoSum(int[] nums, int s) {
        // 对数组进行排序
        Arrays.sort(nums);
        // 初始化左右指针
        int left = 0;
        int right = nums.length - 1;
        // 使用双指针法查找
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == s) {
                // 找到和为 s 的两个数
                return true;
            } else if (sum < s) {
                // 和小于 s，左指针右移
                left++;
            } else {
                // 和大于 s，右指针左移
                right--;
            }
        }
        // 未找到和为 s 的两个数
        return false;
    }
}

例题2：假设有两个数字的集合 A 和 B。现在要求两个集合的交集。请给出一个蛮力的方案，再用预排序的方法设计一个方案。

蛮力法：遍历 A 集合，用当前数字与 B 集合中所有数字比较，如果相同就加入交集，直到 A 遍历结束；预排序：分别排序，两个指针分别遍历，相等加入交集，都移动，哪个小移动哪个。

例题3：在实数域上有 n 个开区间，开区间由严格位于区间端点之间的所有点构成，求给定开区间集合中包含共同点的区间的最大数量。例如 (1,4) , (0,3) , (-1.5,2) , (3.6,5)，包含共同点的最大区间个数为 3 个。

class Interval {
    double start;
    double end;
    public Interval(double start, double end) {
        this.start = start;
        this.end = end;
    }
}
public class MaxOverlappingIntervalsUsingPQ {
    public static int maxOverlappingIntervals(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        // 按照区间的左端点进行排序
        Collections.sort(intervals, Comparator.comparingDouble(i -> i.start));
        // 使用优先队列（最小堆）来维护当前重叠区间的右端点
        PriorityQueue<Double> pq = new PriorityQueue<>();
        int maxOverlap = 0;
        for (Interval interval : intervals) {
            // 如果队列头部的右端点小于当前区间的左端点，说明该区间已经不与当前区间重叠，将其从队列中移除
            while (!pq.isEmpty() && pq.peek() <= interval.start) {
                pq.poll();
            }
            // 将当前区间的右端点加入队列
            pq.offer(interval.end);
            // 更新最大重叠区间数量
            maxOverlap = Math.max(maxOverlap, pq.size());
        }
        return maxOverlap;
    }
    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<>();
        intervals.add(new Interval(1, 4));
        intervals.add(new Interval(0, 3));
        intervals.add(new Interval(-1.5, 2));
        intervals.add(new Interval(3.6, 5));

        int result = maxOverlappingIntervals(intervals);
        System.out.println("包含共同点的最大区间个数为: " + result);
    }
}

例题4：在一个给定的单词集合中，如何快速查找所有变位词？例如 eat、ate、tea 属于同一个变位词集合。

public class AnagramFinder {
    public static List<List<String>> findAnagrams(List<String> words) {
        // 用于存储排序后的字符串和对应的变位词列表
        Map<String, List<String>> anagramMap = new HashMap<>();
        // 遍历单词集合
        for (String word : words) {
            // 将单词转换为字符数组
            char[] charArray = word.toCharArray();
            // 对字符数组进行排序
            Arrays.sort(charArray);
            // 将排序后的字符数组转换为字符串，作为键
            String sortedWord = new String(charArray);
            // 检查 Map 中是否已经存在该键
            if (!anagramMap.containsKey(sortedWord)) {
                // 如果不存在，创建一个新的列表
                anagramMap.put(sortedWord, new ArrayList<>());
            }
            // 将原单词添加到对应的列表中
            anagramMap.get(sortedWord).add(word);
        }
        // 将 Map 中的值转换为列表返回
        return new ArrayList<>(anagramMap.values());
    }
    public static void main(String[] args) {
        List<String> words = Arrays.asList("eat", "ate", "tea", "tan", "nat", "bat");
        List<List<String>> anagramGroups = findAnagrams(words);
        // 输出所有变位词集合
        for (List<String> group : anagramGroups) {
            System.out.println(group);
        }
    }
}

时空权衡-计数排序

空间换时间，对问题的部分或者全部的输入作预处理，然后对获得的额外信息进行存储，以加速后面问题的求解。
计数排序：多次扫描列表，利用额外空间记录比每一个元素小的元素的个数，最后把原列表的元素复制到新数组对应下标地方。
例题1：写一个算法计算两个稀疏矩阵的乘积。

class SparseMatrix {
    int rows;
    int cols;
    List<int[]> elements;
    public SparseMatrix(int rows, int cols, List<int[]> elements) {
        this.rows = rows;
        this.cols = cols;
        this.elements = elements;
    }
    public SparseMatrix multiply(SparseMatrix other) {
        if (this.cols != other.rows) {
            throw new IllegalArgumentException("矩阵维度不匹配，无法相乘");
        }
        List<int[]> resultElements = new ArrayList<>();        
        for (int[] row : this.elements) {// 对第一个矩阵的每一行
            for (int[] col : other.elements) {// 对第二个矩阵的每一列               
                if (row[1] == col[0]) {// 如果行和列的索引匹配，计算乘积
                    int dotProduct = row[2] * col[2];
                    if (dotProduct != 0) {
                        resultElements.add(new int[]{row[0], col[1], dotProduct});
                    }
                }
            }
        }
        return new SparseMatrix(this.rows, other.cols, resultElements);
    }
}

例题1：使用多种排序方法对 2^31 个 IPv4 地址进行排序；只有 1G 内存空间可以使用。

外部归并排序，依次将每个小文件加载到内存中，使用快速排序、堆排序等高效的内部排序算法对小文件内的地址进行排序；使用多路归并算法，同时从多个已排序的小文件中读取数据，每次选取最小的地址输出到一个新的文件中，直到所有小文件的数据都处理完毕。最终得到一个完整的、按顺序排列的 IPv4 地址文件。

蛮力法

本章学习要求：能够熟练使用蛮力法解决问题，作为优化的基线方法，例如找到数组中大小最接近的两个元素的差、找到凸包极点等问题。

前言

蛮力法即枚举法、穷举法，暴力法。它的关键是依次处理所有元素或者依次处理所有可能的情况。
体现蛮力法的两个典型场景：选择排序和冒泡排序

  • 选择排序：选择最大或最小与第一个没有排序好的交换
  • 冒泡排序：遍历列表，两两按照大小交换位置

蛮力法之顺序查找

在给定的列表中查找一个给定的值。
蛮力解法：给定的列表是搜索空间，需要在该空间内根据限制条件顺序查找。
示例1：求所有的三位数，它除以11所得的余数等于它的三位数字的平方和。

public class Main {
    public static void main(String[] args) {
        // 遍历所有的三位数
        for (int num = 100; num < 1000; num++) {
            // 计算该数除以 11 的余数
            int remainder = num % 11;
            // 分离出该数的百位、十位和个位数字
            int hundreds = num / 100;
            int tens = (num / 10) % 10;
            int units = num % 10;
            // 计算三位数字的平方和
            int squareSum = hundreds * hundreds + tens * tens + units * units;
            // 判断余数是否等于三位数字的平方和
            if (remainder == squareSum) {
                System.out.println(num);
            }
        }
    }
}

示例2：某公司有N层楼，为了测出哪层楼最高，可以使用一种仪器从天花板向地板自由落体测时间，仪器不会摔坏；如果有两个一模一样的仪器，请设计一个最佳效率类型的算法解决这个问题。
课件中的翻译有误，实际上是：一家公司想要确定其N层总部大楼中，小部件从多高楼层掉落而不会摔坏的最高楼层。该公司有两个完全相同的小部件用于试验。如果其中一个摔坏了，就无法修复，后续试验将只能用剩下的那个小部件完成。设计一种算法来解决这个问题，使其尽可能达到最佳效率类别。

二分法：从 N/2 层扔一次，如果摔坏了，就从 1 楼开始逐个扔直到 N/2 层，反之从 N/2 层开始逐个扔直到顶层。

蛮力法之模式匹配

从n个字符组成的串中寻找匹配模式（ m 个字符，m <= n）的子串。
蛮力解法：以文本中的每一个字符为开始，用模式串匹配，直到文本结束。
示例1：给定一个文本 CADFBAAXBYA，计算以 A 开始以 B 结束的字符串个数。

public class Main {
    public static void main(String[] args) {
        String text = "CADFBAAXBYA";
        int count = 0;
        // 遍历字符串中的每个字符
        for (int i = 0; i < text.length(); i++) {
            if (text.charAt(i) == 'A') {
                // 从当前 'A' 的位置往后找 'B'
                for (int j = i + 1; j < text.length(); j++) {
                    if (text.charAt(j) == 'B') {
                        count++;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

蛮力法之最近对问题

找出一个包含 n 个点的集合中距离最近的两个点。
蛮力解法：求出每两个点之间的距离，选出最小的那一个。注意不要重复计算两个点之间的距离，即 A 和 B 的距离与 B 和 A 的距离是等价的。
示例1：一条线上的 n 个点如何计算距离最小的两个点。

public class ClosestPointsIndices {
    public static int[] findClosestPointsIndices(int[] points) {
        int n = points.length;
        if (n < 2) {
            return new int[]{-1, -1}; // 如果数组元素少于2个，返回无效下标
        }
        int minDistance = Integer.MAX_VALUE;
        int index1 = -1;
        int index2 = -1;
        // 遍历所有可能的点对
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int distance = Math.abs(points[i] - points[j]);
                if (distance < minDistance) {
                    minDistance = distance;
                    index1 = i;
                    index2 = j;
                }
            }
        }
        return new int[]{index1, index2};
    }
}

蛮力法之凸包问题

为一个包含 n 个点的集合构造凸包的问题。

  • 凸包：一个点集合 S 的凸包是包含 S 的最小凸集合
  • 凸集合：对面平面上的一个点集合，如果以集合中任意两点 P 和 Q 为端点的线段都属于该集合，我们就称这个集合是凸的（例如直线、三角形）
  • 凸包定理：任意包含多于两个不共线点的集合 S 的凸包肯定是以 S 中某些点为顶点的凸多边形

示例1：设计一个线性算法找到 n>1 个点集合的两个极点（凸包的顶点）。

  • 极点的特性：如果两个点构成的线段是凸包的边界，则其他点都在这条线段所在直线的一边

示例2：线性规划问题，求出 3x + 5y 在约束条件 x + y <= 4 且 x + 3y <= 6 且 x >= 0，y >= 0下的最大值。

  • 约束条件构成可行区域即凸包，最优解一定出现在凸包的某个极点上
    public class LinearProgrammingBruteForce {
        public static void main(String[] args) {
            // 定义步长，步长越小结果越精确，但计算时间会增加
            double step = 0.01;
            // 初始化最大值为 0
            double maxValue = 0;
            // 由于 x + y <= 4 且 x + 3y <= 6，x 和 y 的最大值不会超过4
            for (double x = 0; x <= 4; x += step) {
                for (double y = 0; y <= 4; y += step) {
                    // 检查是否满足约束条件
                    if (x + y <= 4 && x + 3 * y <= 6 && x >= 0 && y >= 0) {
                        // 计算目标函数的值
                        double currentValue = 3 * x + 5 * y;
                        // 更新最大值
                        if (currentValue > maxValue) {
                            maxValue = currentValue;
                        }
                    }
                }
            }
            System.out.println("3x + 5y 的最大值是: " + maxValue);
        }
    }

蛮力法之穷举查找

用户在指数级增长的解空间中查找满足要求的解。
示例1：旅行商问题，即 TSP 问题。有一个旅行商从城市 1 出发，需要到城市 2……n 去推销，最后返回城市 1，任意两个城市的距离已知，求其最佳行走路线。
旅行商问题蛮力解法

  • 旅行商问题的扩展：瓶颈 TSP，即经过的最长距离最短
  • 旅行商问题的扩展：最小比率 TSP，即除了行程还会产生收益，优化的目标是总行程与总收益比最小
  • 旅行商问题的扩展：多人 TSP，即多个推销员同时出发，路线不同，使得所有城市至少被访问一次，优化的目标是所有人的总路程最小

示例2：背包问题，给定 n 个，重量为 w1……wn，价值为 v1……vn 的物品和一个承重为 W 的背包，求这些物品中一个最有价值的子集，并且装到背包中。
背包问题蛮力解法

  • 背包问题的扩展：完全背包，即每一件物品不计件数
  • 背包问题的扩展：多重背包，即每一件物品对应有一个确定的件数

示例3：分配问题，将 n 个任务分配给 n 个人执行，每个人只执行一个任务，每个任务只能给一个人执行。将第 j 个任务分配个第 i 个人执行的成本是 C[i,j]，如何找到总成本最小的分配方案。

  • 分配问题蛮力解法
    分配问题蛮力解法
  • 分配问题匈牙利算法（时间复杂度通常是 O(n^3)）
    分配问题匈牙利算法
    分配问题匈牙利算法例题

示例4：分配问题之二分图的最大匹配，在二分图中，顶点被分为两个不相交的集合，且图中的每条边都连接这两个集合中一个顶点，最大匹配指的是选取尽可能多的边，且这些边之间没有公共顶点。使用增广路径算法。
增广路径算法步骤

  • 二分图最大匹配的扩展：加权二分图的最大匹配，即图中的每一条边有一个权重，在满足完全匹配（最大匹配）的前提下，选择权重和最大的方式
    加权的增广路径算法步骤

蛮力法其他例题

假金币问题：有 N 个金币，其中一个是假的，重量小于真金币，其他真金币的重量都相同，只有一台天平可以使用，设计一个算法找到假金币，或者给定测试结果，判断假金币编号。
假金币问题测试结果

只有一个金币是假的，根据第二行结果可知编号为 2 和 5 的金币都为真金币，根据第三行结果可知编号为 1 和 4 的金币都为真金币，则假金币是编号为 3 的金币。

阶乘位数问题：计算 N! 有多少位。

分治法

本章学习要求：分治思想在具体实现的时候，可以使用递归的方法，也可以结合特殊的数据结构使用循环的方法，例如合并排序、快速排序等。能够采用分治思想解决的两个经典问题是最近对问题和凸包问题，请掌握具体的代码实现。

前言

分治法是最著名的通用算法设计技术，很多有效的算法是分治算法的特殊实现。
分治法的具体方案流程：

  • 将问题实例划分为同一个问题的几个较小实例，最好拥有相同规模
  • 对每一个较小规模的实例进行求解
  • 如果需要则以某种方式合并这些小问题的解得到原问题的解

分治法在排序中的应用：归并排序和快速排序。
例题1：N 个直径各不相同的螺母和 N 个直径各不相同的螺钉，但是螺钉和螺母是一一对应的。如果不可以使用螺母与螺母比较，也不能使用螺钉和螺钉比较，如何快速找到它们的对应关系？

从螺钉中选出一个，对螺母们进行划分成三部分：比这个螺钉小的、大的和相等的。随后取出第一步相等的螺母，对螺钉们进行相同的划分。对小的部分，和大的部分，进行递归操作。

例题2：Tromino 是一个由棋盘上的三个邻接方块组成的 L 型瓦片，我们的问题是，如何用 Tromino 覆盖一个缺少了一个方块的 2 ^ n * 2 ^ n 的棋盘，除了这个缺失的方块，要覆盖棋盘上所有其它方块，而且不能有重复。

通过对问题的分析，题目要求用分治法来解决该问题。该问题中缺失方块的位置是任意的，棋盘大小是 2 的 n 次方（n 为正整数）的矩阵，所以先来考虑最小规模即当 n = 1 时的情况。这种情况下无论缺失的方块在哪个位置，只需要将剩下的三个方块填充就好，相当于放置一个骨牌。当 n = 2 时，方块数为4 * 4。划分子问题前，我们先将棋盘分为四个象限，确定缺失方块的象限后，将其它三个象限距离中心位置最近的一个方块填充。此时再将其划分为四个方块数为2 * 2 的矩阵，将已经填充的方块看作缺失方块，则每个小规模矩阵都有一个缺失方块，即它们是规模相同的子问题，依次递归最后将整个棋盘填充完整。

分治法之折半查找

对于有序列表的卓越查找方案。通过对比查找键值与列表中间元素的大小，确定下一次查找的位置。
分治法折半查找递归方案：

public class BinarySearchRecursive {
    /**
     * 递归实现的二分查找函数
     * @param arr 要查找的有序数组
     * @param left 左边界索引
     * @param right 右边界索引
     * @param target 要查找的目标值
     * @return 如果找到目标值，返回其索引；否则返回 -1
     */
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // 未找到目标值
        }
        int mid = left + (right - left) / 2; // 计算中间索引
        if (arr[mid] == target) {
            return mid; // 找到目标值，返回其索引
        } else if (arr[mid] > target) {
            // 目标值在左半部分，递归查找左半部分
            return binarySearch(arr, left, mid - 1, target);
        } else {
            // 目标值在右半部分，递归查找右半部分
            return binarySearch(arr, mid + 1, right, target);
        }
    }
}

分治法折半查找非递归方案：

public class BinarySearch {
    // 非递归折半查找
    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 如果目标值等于中间元素，返回索引
            if (array[mid] == target) {
                return mid;
            }
            // 如果目标值小于中间元素，调整右边界
            if (array[mid] > target) {
                right = mid - 1;
            } 
            // 如果目标值大于中间元素，调整左边界
            else {
                left = mid + 1;
            }
        }
        // 如果没有找到目标值，返回 -1
        return -1;
    }
}

分治法之二叉树遍历

回顾完全二叉树、满二叉树等二叉树基本概念：

  • 完全二叉树：如果有 h 层，1 ~ h-1 层布满节点，h 层节点从左向右分布
  • 满二叉树：除了叶子节点其它节点都有左右子节点，且叶子节点都在最底层
  • 二叉查找树：排序好二叉树，如果左子树不空，则左子树值小于根节点值；如果右子树不空，则右子树值都大于根节点；左右子树分别是二叉查找树
  • 平衡二叉树：是一棵左右子树高度差绝对值不大于 1 的二叉查找树

二叉树与分治思想的关联在于，对二叉树的操作可以变为对左右子树的分别操作。但不是所有二叉树的操作都体现分治思想，例如二叉查找树的插入和删除等。
分治法之计算二叉树高度：左子树的最大高度或右子树的最大高度 + 1。

public class BinaryTreeHeight {
    // 分治法计算二叉树高度
    public int getHeight(TreeNode root) {
        // 基线条件：如果当前节点为空，返回高度 0
        if (root == null) {
            return 0;
        }
        // 递归计算左子树的高度
        int leftHeight = getHeight(root.left);
        // 递归计算右子树的高度
        int rightHeight = getHeight(root.right);
        // 返回当前树的高度：左右子树的最大高度 + 1（当前节点）
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

分治法之二叉树的遍历：前序遍历（根-左-右），中序遍历（左-根-右），后序遍历（左-右-根）。

public class BinaryTreeTraversal {
    // 前序遍历：根节点 -> 左子树 -> 右子树
    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        // 访问根节点
        System.out.print(root.val + " ");
        // 递归遍历左子树
        preOrderTraversal(root.left);
        // 递归遍历右子树
        preOrderTraversal(root.right);
    }
    // 中序遍历：左子树 -> 根节点 -> 右子树
    public static void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归遍历左子树
        inOrderTraversal(root.left);
        // 访问根节点
        System.out.print(root.val + " ");
        // 递归遍历右子树
        inOrderTraversal(root.right);
    }
    // 后序遍历：左子树 -> 右子树 -> 根节点
    public static void postOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归遍历左子树
        postOrderTraversal(root.left);
        // 递归遍历右子树
        postOrderTraversal(root.right);
        // 访问根节点
        System.out.print(root.val + " ");
    }
}

分治法之二叉树节点间最大距离：可能的情况是，左子树中节点间最大距离，或者右子树中节点最大距离，或者左子树中节点到右子树中节点的最大距离。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
private static class Distance {
    int maxDistance;
    int height;
    Distance(int maxDistance, int height) {
        this.maxDistance = maxDistance;
        this.height = height;
    }
}
public static int findMaxDistance(TreeNode root) {
    return findMaxDistanceUtils(root).maxDistance;
}
private static Distance findMaxDistanceUtils(TreeNode root) {
    if (root == null) {
        return new Distance(0, -1); // height is -1 for null node
    }
    Distance leftDistance = findMaxDistanceUtils(root.left);
    Distance rightDistance = findMaxDistanceUtils(root.right);
    // Distance through root
    int throughRoot = leftDistance.height + rightDistance.height + 2;
    // Distance in left or right subtree
    int withoutRoot = Math.max(leftDistance.maxDistance, rightDistance.maxDistance);
    // Max of the two distances
    int maxDistance = Math.max(throughRoot, withoutRoot);
    // Height of current node is max of left or right height + 1
    int height = Math.max(leftDistance.height, rightDistance.height) + 1;
    return new Distance(maxDistance, height);
}

例题1：有一个 n × m 格的巧克力，我们要把它掰成 n × m 个 1 × 1 的小块，我们只能沿着直线掰，而且不能几块同时掰，设计一个算法用最少的次数掰完巧克力，该次数是多少？如果可以几块同时掰，最少需要多少次？

每次都掰一块巧克力，当是一条 1 x m 的巧克力时，最少需要 m - 1 次，故对 n x m 的巧克力，我们可以先掰成 n 条 1 × m 的巧克力，则此时需要 n - 1 次，再对每个 1 x m 掰 m - 1 次，则此时总次数是 n × m - 1 次；当没有每次操作一块巧克力的限制时，我们还是对 1 x m 的巧克力考虑，此时需要 log m 次，而将 n × m 掰成 1 × m 需要 log n 次，故总次数是 log n + log m，此时掰的时候是将巧克力叠着一起掰。

分治法之大数乘法、斯特拉森矩阵乘法

密码技术中，需要对超过 100 位的十进制整数进行乘法运算，但这些整数无法用整型表示，衍生出大数乘法问题。
对于任意两个两位整数的例子：把结果看成是由百位、十位、个位数字组成。

  • 百位数字是两个两位数的十位数字相乘得到
  • 个位数字是两个两位数的个位数字相乘得到
  • 十位数字的算法稍复杂，是把两个两位数的十位与个位数字分别相加后相乘，再减去前面得到的百位数字与个位数字之和

大数乘法中的分治思想：对于位数较多的整数相乘，用分治思想，就是把大问题变成小问题。如果整数的位数 n 是偶数，就把每个整数拆成两部分，前半部分乘 10 的 n 除以 2 次方，再加上后半部分。然后像算两位数乘法那样，把乘积结果也拆成三部分，计算这三部分的方法和两位数乘法类似：

  • 第一部分类似两位数乘法里的百位数字算法
  • 第二部分类似十位数字算法
  • 第三部分类似个位数字算法

应用主定理计算复杂度：
分治法时间复杂度递归式主定理
在大数乘法算法中，a 为 3，b 为 2，d 为 1，所以根据主定理，该算法的时间复杂度为 O(n ^ 1.58)，优于传统乘法的 O(n ^ 2)。

  • 其中，a 代表递归子问题的数量
  • 其中，b 代表子问题的规模
  • 其中，d 代表非递归部分的时间复杂度

从大于 600 位的整数开始，分治算法的性能超越笔算算法的性能。
两个两阶矩阵的乘积计算需要 8 次乘法，Strassen 发现计算矩阵乘法可以只使用 7 次乘法。Strassen 矩阵乘法的核心原理是通过将大矩阵分解为较小的子矩阵，并利用特定的组合方式来减少乘法运算的次数。算法步骤简略描述如下：

  • 将输入的两个 n × n 矩阵 A 和 B 划分为四个 n / 2 × n / 2 的子矩阵
  • 按照 Strassen 的方法，计算 7 个中间矩阵
  • 根据 7 个中间矩阵，计算结果矩阵 C 的四个子矩阵
  • 将计算得到的四个子矩阵组合起来，得到最终的结果矩阵 C

应用主定理计算复杂度：
分治法Strassen矩阵乘法

分治法之最近对问题

分治思想在最近对问题中的应用：

  • 使用一个坐标维度将点分为两个大小接近的集合，需要先排序
  • 分别计算两个集合中的最近对
  • 然后合并
  • 对小集合中的点递归使用分治思想

分治法之凸包问题