面试算法大全-分治算法总结

╰半夏微凉° 2022-10-06 13:57 226阅读 0赞

## 12、分治 ##

### 12.1 分治算法总结 ###

分治法在每一层递归上都有三个步骤：  
  （1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。  
  （2）求解：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。  
  （3）合并：将各个子问题的解合并为原问题的解。

//伪代码
    Divide-and-Conquer(P)
        if |P| ≤ n0
            then return(ADHOC(P))
        将P分解为较小的子问题 P1 ,P2 ,...,Pk
            for i←1 to k
                do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
            T ← MERGE(y1,y2,...,yk) △ 合并子问题
        return(T)

其中，|P| 表示问题 P 的规模，n0 为一阈值，表示当问题 P 的规模不超过 n0 时，问题已容易直接解出，不必再继续分解。ADHOC§ 是该分治法中的基本子算法，用于直接解小规模的问题 P。因此，当 P 的规模不超过n0 时直接用算法 ADHOC§ 求解。算法 MERGE(y1,y2,…,yk) 是该分治法中的合并子算法，用于将 P 的子问题 P1 ,P2 ,…,Pk 的相应的解 y1 , y2 ,…, yk 合并为 P 的解。

![img][]

### 12.2 经典题目源码总结 ###

#### 二分查找 ####

public int recursionBinarySearch(int[]arr,int key,int low,int high){
        
        if(key<arr[low]||key>arr[high]||low>high){
        
            return-1;
        }
        int middle=(low+high)/2;            //初始中间位置
        if(arr[middle]>key){
        
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr,key,low,middle-1);
        }else if(arr[middle]<key){
        
            //比关键字小则关键字在右区域
            return recursionBinarySearch(arr,key,middle+1,high);
        }else{
        
            return middle;
        }
    }

#### 全排列问题 ####

public class Test {
        
        public static void main(String[] args) {
        
            int[] arr = {
         1, 2, 3, 4 };
            fullSort(arr, 0, arr.length - 1);
        }
        public static void fullSort(int[] arr, int start, int end) {
        
            // 递归终止条件
            if (start == end) {
        
                for (int i : arr) {
        
                    System.out.print(i);
                }
                System.out.println();
                return;
            }
            for (int i = start; i <= end; i++) {
        
                swap(arr, i, start);
                fullSort(arr, start + 1, end);
                swap(arr, i, start);
            }
        }
    
        private static void swap(int[] arr, int i, int j) {
        
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

#### 归并排序 ####

算法 MergeSort(A, p, r)
    输入：数组A[p...r]
    输出：有序数组A
    if(p < r)
        then q <- (p+r)/2//折半划分
            MergeSort(A, p ,q)//子问题1
            MergeSort(A, p ,q)//子问题2
            Merge(A, p ,q, r)//合并求解

public class MergeSort {
        
        //两路归并算法，两个排好序的子序列合并为一个子序列
        public void merge(int []a,int left,int mid,int right){
        
            int []tmp=new int[a.length];//辅助数组
            int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针
            while(p1<=mid && p2<=right){
        
                if(a[p1]<=a[p2])
                    tmp[k++]=a[p1++];
                else
                    tmp[k++]=a[p2++];
            }
            while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
            while(p2<=right) tmp[k++]=a[p2++];//同上
            //复制回原素组
            for (int i = left; i <=right; i++) 
                a[i]=tmp[i];
        }
    
        public void mergeSort(int [] a,int start,int end){
        
            if(start<end){
        //当子序列中只有一个元素时结束递归
                int mid=(start+end)/2;//划分子序列
                mergeSort(a, start, mid);//对左侧子序列进行递归排序
                mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
                merge(a, start, mid, end);//合并
            }
        }
    }

#### 快速排序 ####

import java.util.Arrays;
    import java.util.Random;
    
    /**
     * 快速排序，使得整数数组 arr 有序
     */
    public class QuickSortSwap {
        
        public static int[] quickSort(int[] arr) {
        
            if (arr == null || arr.length < 2) {
        
                return arr;
            }
            quickSort(arr, 0, arr.length - 1);
            return arr;
        }
        /**
         * 快速排序，使得整数数组 arr 的 [L, R] 部分有序
         */
        public static void quickSort(int[] arr, int L, int R) {
        
            if (L < R) {
        
                // 把数组中随机的一个元素与最后一个元素交换，这样以最后一个元素作为基准值实际上就是以数组中随机的一个元素作为基准值
                swap(arr, new Random().nextInt(R - L + 1) + L, R);
                int[] p = partition(arr, L, R);
                quickSort(arr, L, p[0] - 1);
                quickSort(arr, p[1] + 1, R);
            }
        }
        /**
         * 分区的过程，整数数组 arr 的[L, R]部分上，使得：
         * 大于 arr[R] 的元素位于[L, R]部分的右边，但这部分数据不一定有序
         * 小于 arr[R] 的元素位于[L, R]部分的左边，但这部分数据不一定有序
         * 等于 arr[R] 的元素位于[L, R]部分的中间
         * 返回等于部分的第一个元素的下标和最后一个下标组成的整数数组
         */
        public static int[] partition(int[] arr, int L, int R) {
        
            int basic = arr[R];
            int less = L - 1;
            int more = R + 1;
            while (L < more) {
        
                if (arr[L] < basic) {
        
                    swap(arr, ++less, L++);
                } else if (arr[L] > basic) {
        
                    swap(arr, --more, L);
                } else {
        
                    L++;
                }
            }
            return new int[]{
        less + 1, more - 1};
        }
        /**
         * 交换数组 arr 中下标为 i 和下标为 j 位置的元素
         */
        public 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 = {
        1,9,3,12,7,8,3,4,65,22};
            int[] sort = QuickSortSwap.quickSort(arr);
            System.out.println(Arrays.toString(sort));
        }
    }

#### 汉诺塔问题 ####

public class Hanoitower {
        
    	public static void main(String[] args) {
        
    		hanoiTower(10, 'A', 'B', 'C');
    	}
    	//汉诺塔的移动的方法
    	//使用分治算法
    	public static void hanoiTower(int num, char a, char b, char c) {
        
    		//如果只有一个盘
    		if(num == 1) {
        
    			System.out.println("第1个盘从 " + a + "->" + c);
    		} else {
        
    			//如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
    			//1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
    			hanoiTower(num - 1, a, c, b);
    			//2. 把最下边的盘 A->C
    			System.out.println("第" + num + "个盘从 " + a + "->" + c);
    			//3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔  
    			hanoiTower(num - 1, b, a, c);
    		}
    	}
    }

#### 合并两个链表 ####

class Solution {
        
    	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
    		//递归的结束条件，如果l1和l2中有一个为空就返回
    		if(l1==null || l2==null) {
        
    			return (l1==null)? l2:l1;
    		}
    		//如果l1的值<=l2的值，就继续递归，比较l1.next的值和l2的值
    		//l1.next和l2比较完后，会产生一个更小的节点x，将x加到当前l1的后面
    		if (l1.val<=l2.val) {
        
    			l1.next = mergeTwoLists(l1.next,l2);
    			return l1;
    		//如果l1的值>l2的值，就继续递归，比较l1的值和l2.next的值
    		} else {
        
    			l2.next = mergeTwoLists(l1,l2.next);
    			return l2;
    		}
    	}
    }

[img]: /images/20221005/23023448e727426aae9d7a31f3ce9392.png