算法分析期末复习

第一章 算法概述

• 基本理论知识
• 课后作业做过的类型
• 1. 渐进阶排序，类似课后作业：1-3
  2. 输入规模，类似课后作业： 1-4， 1-5

第二章 递归与分治

• 基本概念，基本思想

  • 递归：直接或间接的调用自身的算法。
  • 分治：分治法 的子问题间是相互独立的，子问题不包含公共的子问题。

• 排序(归并，快速)

• 二分搜索

• 解决实际问题：

• 1. 10个硬币，其中有一个假币，比真币轻，要求用分治法找假币
  2. 求最大值最小值，次大值次小值

归并排序

package review;
public class MergeSort {
    public  void sort(int []a){
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int []temp = new int[a.length];
        mergeSort(a,0, a.length-1, temp);
    }

    public void mergeSort(int[] a, int left, int right, int[] temp){
        if(left < right){
            int mid = left+(right-left)/2;
            mergeSort(a, left, mid, temp); //左边归并排序，使得左子序列有序
            mergeSort(a, mid+1, right, temp); //右边归并排序，使得右子序列有序
            merge(a, left, mid, right, temp); // 并
        }
    }
    /**
     * 归并排序
     * @param a 待排序的数组
     * @param left 排序的左边界
     * @param mid 数组的中间
     * @param right 排序的右边界
     * @param temp 一个长度等于原数组长度的临时数组
     */
    public void merge(int[] a, int left, int mid, int right, int[] temp){
        int i = left, j = mid + 1;
        int t = 0;
        while(i <= mid && j <= right){ // 开始排序，
            if(a[i] <= a[j]){ // 相等也要填，这次会把一个相等的数移到temp，另一个等下次。
                temp[t++] = a[i++];
            }else{
                temp[t++] = a[j++];
            }
        }
        while(i > mid){
            temp[t++] = a[j++];
        }
        while(j > left){
            temp[t++] = a[i++];
        }
        t = 0;
        while(left < right){
            a[left++] = temp[t++];
        }
    }
}

快速排序

package review;

public class QuickSort {
    public static void main(String[] args) {
        int[] a = {6, 10, 32, 8, 19, 20, 2, 14};
        quickSort(a, 0, a.length-1);
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }
    public static void quickSort(int[] a, int left, int right){
       if(left < right){
           int i = left;
           int j = right;
           int x = a[i];
           while(i < j){
                while(i < j && a[j] > x){
                    j--;
                }
                if(i < j){
                    a[i++] = a[j];
                }
                while(i < j && a[i] < x){
                    i++;
                }
                if(i < j){
                    a[j--] = a[i];
                }
           }
           a[i] = x;
           quickSort(a,left, i-1);
           quickSort(a, i+1, right);
       }
    }
}

二分搜索

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return -1;
    }
}

棋盘覆盖(分治法)

找假币

package review;

public class FindFakeCoin {
    public static void main(String[] args) {
        int[] arr = {2,2,2,2,2,1};
        System.out.println(findFakeCoin(arr, 0, arr.length-1));
    }
    public static int findFakeCoin(int[] a, int l, int r){
        int sum1 = 0;
        int sum2 = 0;
        if((r-l+1)% 2 == 0){ // 偶数
            if(l == r-1){
                if(a[l] < a[r]){
                    return l;
                }else{
                    return r;
                }
            }else{ //数组多于两个数
                int mid = l + (r-l+1)/2; // 找中间位置
                for(int i = l; i < mid; i++){
                    sum1 += a[i]; // 中间靠左数组集合总和
                    sum2 += a[i+mid]; // 中间靠右数组集合总和
                }
                if(sum1 < sum2){
                    return findFakeCoin(a, l, mid-1);
                }else{
                    return findFakeCoin(a, mid, r);
                }
            }

        }else{ //奇数
            int mid = l+(r-l)/2;
            for(int i = l; i < mid; i++){
                sum1 += a[i];
                sum2 += a[r-(i-l)];
            }
            if(sum1 < sum2){
                return findFakeCoin(a, l, mid-1);
            }else if(sum1 > sum2){
                return findFakeCoin(a, mid+1, r);
            }else{
                return mid;
            }
        }
    }
}

求最值和次值

package review;

import java.util.Arrays;

public class MaxiMum {
    public static void main(String[] args) {
        int arr[] = { -2, -9, 0, 5, 2 };
        int[] res =  findMinMax(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(res));

    }
    public static int[] findMinMax(int[] a, int l, int r){
        int min = 0, max = 0;
        if(l == r){ // 只剩一个格子
            min = a[l];
            max = a[l];
        }else if(l == r - 1){ // 还有两个格子
            max = a[l] > a[r]?a[l]:a[r];
            min = a[l] < a[r]?a[l]:a[r];
        }else{  // 不止两个格子，分割，结果用数组储存。
            int mid = l + (r-l)/2;
            int[] preHalf = findMinMax(a, l, mid);
            int[] postHalf = findMinMax(a,mid+1, r);
            max = postHalf[0] > preHalf[0]?postHalf[0]:preHalf[0];
            min = postHalf[1] < preHalf[1]?postHalf[1]:preHalf[1];
        }
        return new int[] {max, min};
    }

}

第三章 动态规划

1. 基本概念，基本思想

2. 矩阵连乘问题

3. 最长公共子序列

4. 01背包

5. 解决实际问题 ：

   1. 设m是一个n位十进制整数。如果将m划分为x段，则可得到x个整数。这x个整数的乘积称为m的一个x乘积。试设计一个算法，对于给定的m和x,求出m的最大x乘积。要求给出动态规划算法解决该问题的基本思路，并给出该问题的递归公式。

   2. 数字三角形问题（算法实现题3-4）

   3. 石子合并问题

矩阵连乘

public static int matrixChain(int arrayNum, int[]m, int l, int r){
        int t = 0;
        // dp[i][j]表示第i到j个矩阵的最少计算次数
        int[][] dp = new int[arrayNum+1][arrayNum+1];
        // 第i到i个的计算次数为 0
        for(int i = 1; i <= arrayNum; i++){
            dp[i][i] = 0;
        }
        for(int i = 1; i <= arrayNum; i++){
            for(int j = i+1; j <= arrayNum; j++){ 
                dp[i][j] = dp[i+1][j] + m[i-1]*m[i]*m[j];
                for(int a = 1; a < arrayNum; a++){
                    t = dp[i][a] + dp[a+1][j] + m[i-1]*m[a]*m[j];
                    if(dp[i][j] > t){
                        dp[i][j] = t;
                    }
                }
            }
        }
        return dp[l][r];
    }

最长公共子序列

public int Lcs(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= s2.length(); j++) {
            dp[0][j] = 0;
        }
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }

01背包

public static void bag01(int bagCapacity, int[] itemWeight, int[] itemValue){
        int[][] dp = new int[itemValue.length+1][bagCapacity+1];
        for(int i = 0; i <= itemValue.length; i++){
            dp[i][0] = 0;
        }
        for(int j = 0; j <= bagCapacity; j++){
            dp[0][j] = 0;
        }
        for(int i = 1; i <= itemValue.length; i++){
            for(int j = 0; j <= bagCapacity; j++) {
                if(j >= itemWeight[i]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-itemWeight[i]] + itemValue[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
           }
        }
    }

1.

设m是一个n位十进制整数。如果将m划分为x段，则可得到x个整数。这x个整数的乘积称为m的一个x乘积。试设计一个算法，对于给定的m和x,求出m的最大x乘积。要求给出动态规划算法解决该问题的基本思路，并给出该问题的递归公式。

dp[i][j] = max{dp[i][j], dp[m][j-1]*num[m+1][i] }
dp[i][j] 表示这个数前i位切j刀的最大乘积为：前m位切j-1刀的最大乘积乘上num[m+1][i];

第四章 贪心算法

1. 基本概念，基本思想。

2. 活动安排问题

3. 背包问题

4. 最优装载问题

5. 单源最短路径

6. 根据算法思想解决实际问题：

   1. 有n个正整数，将他们连成一排，组成一个最大的多位整数。例如：n = 3时，3个整数13，312，343连成的最大整数为：34331213。又如：n = 4时，4个整数7，13，4，246连接成的最大整数为7424613
   2. 新房需要装修，但是总预算只有20万元，为了更好得满足装修需求，小明按照所需物品的重要程度进行了分类，用1~5表示，第5类最重要，他希望在不超过预算的前提下，求max（Σ每种物品的价格*重要程度）
   3. 设计一个贪心算法，使得对于给定的n位正整数，在删除其中任意k<=n位数字后，剩余的数字按原来的次序排列组成的新的正整数最小。

做题的时候想清楚什么是局部最优，如何用局部最优推全局最优。

活动安排问题

各个活动的起始时间存在数组 s 中，结束时间存储在数组 f 中。

f [ i ] 按照非递减的顺序排序。所以先排结束时间早的，这样可以为后面的活动留下更多的时间。

import java.util.Arrays;

public class GreedySelect {
    public static void main(String[] args) {
        int[] s = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
        int[] f = {4, 5, 6, 7, 8, 9, 10, 11, 12 ,13 ,14};
        System.out.println(Arrays.toString(greedySelect(s,f)));
    }
    public static boolean[] greedySelect(int[] s, int[] f){
        boolean[] a = new boolean[s.length];
        a[0] = true;
        int t = 0;
        for(int i = 1; i < s.length; i++){ // 后面活动的开始时间要大于前面活动的结束时间。
            if(s[i]>=f[t]){
                t = i;
                a[i]  = true;
            }
            else{
                a[i] = false;
            }
        }
        return a;
    }
}

背包问题

有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

最优装载问题

轮船装的货物重量受限，物品重量给出，求怎样装能装的物品数量最多。

package review;

import java.util.Arrays;

public class LoadProblem {
    public static void main(String[] args) {
        int shipWeight = 100;
        int[] itemWeight = {2, 6, 34, 76, 45, 20};
        loadProblem(shipWeight,itemWeight);
    }
    public static void loadProblem(int shipWeight, int[] itemWeight){
        Arrays.sort(itemWeight); // 将物品按重量从轻到重排序
        boolean[] isLoad = new boolean[itemWeight.length];
        for(int i = 0; i < itemWeight.length; i++){
            if(shipWeight < itemWeight[i]){ // 剩余容量装不下itemWeight[i]了
                break;
            }
            shipWeight -= itemWeight[i]; 
            isLoad[i] = true;
        }
        System.out.println(Arrays.toString(isLoad));
    }
}

单源最短路径

import java.util.Arrays;
import java.util.Scanner;
import java.util.Collections;

public class Dijkstra {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int vectorNum = sc.nextInt();
        int[][] reflect = new int[vectorNum + 1][vectorNum + 1];
        for(int i = 1; i <= vectorNum; i++){
            for(int j = 1; j <= vectorNum; j++){
                reflect[i][j] = sc.nextInt();
            }
        }
        int root = sc.nextInt();
}

/**
 *
 * @param path 记录i到j的路径
 * @param root 源点1
 */
private static void dijkstra(int[][] path, int root){
    boolean identify[]  = new boolean[path.length]; // 判断节点是否找到了最短路径
    int[] rootToVectorPath = new int[path.length]; // 存各点到源点的当前最短路径长度
    int[] prev = new int[path.length]; // 记录前驱节点
    prev[root] = 0; // 源点的前驱节点为 0
    // 初始化 存各点最短路径的数组，
    for(int j = 1; j <= path.length; j++){ // 遍历1~n
        rootToVectorPath[j] = path[root][j]; // 能直达源点的节点的最短路径为她们到源点的路径
        identify[j] = false;
        if(rootToVectorPath[j] != Integer.MAX_VALUE){  // 如果有节点到源点可以直达
            prev[j] = root; // 那么她们的前驱节点就是root
        }else{
            prev[j] = 0; // 不能直达，则前驱节点为0
        }
    }
    identify[root] = true;

    int fulfillVector = 0;
    // refresh circle
    for(int i = 1; i <= path.length; i++) {
        int temp = Integer.MAX_VALUE;
        // 找还没有找到最短路径的点中路径最短的
        for (int j = 1; j <= path.length; j++) {
            if (!identify[j] && rootToVectorPath[j] < temp) {
                fulfillVector = j;
                temp = rootToVectorPath[j];
            }
        }
        identify[fulfillVector] = true;
        // 调整rootToVectorPath
        for (int j = 1; j <= path.length; j++) {
            if(!identify[j] && path[fulfillVector][j] != Integer.MAX_VALUE){
                if(rootToVectorPath[fulfillVector] + path[fulfillVector][j] < rootToVectorPath[j]){
                    rootToVectorPath[j] = rootToVectorPath[fulfillVector] + path[fulfillVector][j];
                    prev[j] = fulfillVector;
                }
            }
        }
    }
}

第五章 回溯法

1. 基本概念，基本思想
2. 01背包
3. 最优装载
4. N后问题
5. 会求左右剪枝问题
6. 利用所学知识解决实际问题

/**
*t为当前拓展节点在解空间树的深度。
*n用来控制递归深度，当t>n时，算法已经搜索到叶子节点。
*/
void backtracking(t) {
    if (终止条件) { // 记录或输出得到的可行解x
        存放结果;
        return;
    }
    for(int i = f(n, t); i <= g(n, t); i++) {
        if(Constraint(t) && Bound(t)){
			处理节点;
            BackTrack(t+1);
         	回溯，撤销处理结果
        }
    }
}

01背包

 public static void backtrack(int t){
        if(t >= itemNum){
            bestValue = Math.max(curValue, bestValue) ;

        }else{
            for(int i = 0; i < 2; i++){
                if(i == 0){
                    backtrack(t+1);
                }else{
                    if(bagCapacity >= curWeight+itemWeight[t]){
                        curWeight += itemWeight[t];
                        curValue += itemValue[t];
                        backtrack(t+1);
                        curWeight -= itemWeight[t];
                        curValue -= itemValue[t];
                    }
                }
            }
        }
    }

最优装载

https://www.cnblogs.com/icodes8238/p/12893640.html
n为集装箱数量 
c为第一艘船的最大容量 
cw为当前已装入第一艘船的重量 
r为剩余未装入第一艘船的重量 
bestw为目前为止最好的装载方案其对应的重量 
w[i]集装箱i的重量 
x[i]集装箱i是否装入第一艘船 

void backtrack(int i){
    if(i > n){ //reach the leaves
        if(cw > bestw) bestw = cw;
        return ;
    }
    r -= w[i]; // 剩余的箱子不包含第i个箱子
    if(cw + w[i] <= c){//constraint function for searching left
        x[i] = 1;
        cw += w[i];
        backtrack(i+1);
        cw -= w[i];
    }
    if(cw + r > bestw){ //bounding function for searching right
        x[i] = 0;
        backtrack(i+1);
    }
    r += w[i]; //剩余的箱子包含第i个箱子
}
    /*-------- 
    关键在于理解下面这个限界函数，目的是剪去得不到最优解的子树。
    这个时候我们正在处理树的第i层，即正在决定第i个集装箱是否装入
    如果说上面的约束函数是对左子树（装入i）的情况剪枝，那么该函数就是对右子树剪枝。 
    
    对该函数的理解：如果我把集装箱i抛弃掉，这个时候
    如果已经装入的重量+未装入的重量比目前的最优解bestw还要差，
    那么说明这种情况不可能得到最优解 
    也就是说如果把不装入集装箱i，肯定的不到最优解，后面的情况不用考虑了
    
    而如果当前载重量cw + 剩余集装箱的重量r>当前最优载重量 best，
    那么我们就要去尝试不装入它，因为有可能得到最优解 
    */

N后问题

/**
     * 递归实现回溯，从第row行开始找放Q的位置
     * @param n 棋盘大小
     * @param row 当前所在行
     * @param chessboard
     */
    public void backTracing(int n, int row, char[][] chessboard){
        if(row >= n){
            res.add(Array2List(chessboard));
            return;
        }

        for(int col = 0; col < n; col++){ // 遍历row层的各种情况col
            if(isValid(chessboard, row, col, n)){ // (row, col)可以放Q
                chessboard[row][col] = 'Q'; // 放Q
                backTracing(n, row + 1, chessboard); // 继续递归
                chessboard[row][col] = '.'; // 回溯，撤回处理结果
            }
        }
    }

第六章 分支限界法（考理论）

1. 基本概念，基本思想
2. 与其他方法的比较
3. 01背包问题
4. 最优装载问题
5. 分析实际问题