算法课程期末复习总结

曾经终败给现在 2022-11-29 11:50 154阅读 0赞

#### 八大排序算法复杂度比较 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center]

#### 求解递归式的复杂度 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center 3]

#### Max Sum(最大子段和) ####

int len = arr.length;
    int[] dp = new int[len + 1];
    dp[0] = 0;
    for(int i = 1; i <= len; i ++) { 
      dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
    }
    int res = Integer.MIN_VALUE;
    for(int i = 1; i < dp.length; i ++) { 
      res = Math.max(res, dp[i]);
    }
    return res;

`dp[i] = max(dp[i-1] + nums[i], nums[i]) (1<=j<=n)`

dp\[i\]表示nums数组从第1个到第i个数区间内的最大子段和

#### **base case**: `dp[0] = 0` ####

结果： 遍历dp数组，找出最大值，即为最大子段和

#### LCS(最长公共子序列) ####

int rows = str1.length();
    int cols = str2.length();
    int[][] dp = new int[rows+1][cols+1];
    for(int i = 1; i <= rows; i ++) { 
      for(int j = 1; j <= cols; j ++) { 
        if(str1.charAt(i-1) == str2.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[rows][cols];

dp[i][j]表示str1[1..i]，str2[1..j]的两段字符串的最长公共子序列
    if  str1[i] == str2[j]
      	dp[i][j] = dp[i-1][j-1] + 1;
    else
      	dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

**base case**: `dp[..][0] = 0, dp[0][..] = 0;`

结果： `dp[str1.len][str2.len]`

#### LPS(最长回文子序列) ####

> 我们说这个问题对 dp 数组的定义是：在⼦串 s\[i…j\] 中，最⻓回⽂⼦序列的⻓度为 dp\[i\]\[j\] 。
> 
> 具体来说，如果我们想求 dp\[i\]\[j\] ，假设你知道了⼦问题 dp\[i+1\]\[j-1\]的结果（ s\[i+1…j-1\] 中最⻓回⽂⼦序列的⻓度），你是否能想办法算出dp\[i\]\[j\] 的值（ s\[i…j\] 中，最⻓回⽂⼦序列的⻓度）呢？
> 
> 可以！这取决于 s\[i\] 和 s\[j\] 的字符：如果它俩相等，那么它俩加上 s\[i+1…j-1\] 中的最⻓回⽂⼦序列就是s\[i…j\] 的最⻓回⽂⼦序列：如果它俩不相等，说明它俩不可能同时出现在 s\[i…j\] 的最⻓回⽂⼦序列中，那么把它俩分别加⼊ s\[i+1…j-1\] 中，看看哪个⼦串产⽣的回⽂⼦序列更⻓即可：

int rows = s.length();
    int cols = s.length();
    int[][] dp = new int[rows][cols];
    for(int i = 0; i < rows; i++) { 
      for(int j = 0; j < cols; j++) { 
        if(i == j) { 
          dp[i][j] = 1;
        }
      }
    }
    for(int i = rows-1; i >=0; i --) { 
      for(int j = i+1;j < cols; j ++) { 
        if(s.charAt(i) == s.charAt(j)) { 
          dp[i][j] = dp[i+1][j-1] + 2;
        }else { 
          dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
        }
      }
    }
    return dp[0][cols-1];

#### 0-1 Knapsack Problem(0-1背包问题) ####

dp[i][w] = max(dp[i-1][w] + (dp[i-1][w-w[i]] + val[i]) )
    dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w ，这种情况下可以装的最⼤价值是 dp[i][w]

**base case** : `dp[0][..] = dp[..][0] = 0`

结果 ： `dp[N][W]`

public static int maxValue(int[] v, int[] w, int weight) { 
      int rows = v.length;
      int cols = weight;
      int[][] dp = new int[rows+1][cols+1];
      //dp[i][w] 的定义如下：对于前 i 个物品，当前背包的容量为 w ，这种情况下可以装的最⼤价值是 dp[i][w] 
      for(int i = 1; i <= rows; i ++) { 
        for(int j = 1; j <= cols; j ++) { 
          if(j - w[i-1] < 0) { 
            dp[i][j] = dp[i-1][j];
          }else { 
            dp[i][j] = Math.max(dp[i-1][j - w[i-1]] + v[i-1] , dp[i-1][j]);
          }
        }
      }
      return dp[rows][cols];
    }

#### 区间调度问题 ####

> 你今天有好⼏个活动，每个活动都可以⽤区间 \[start, end\] 表⽰开始和结束的时间，请问你今天最多能参加⼏个活动呢？显然你⼀个⼈不能同时参加两个活动，所以说这个问题就是求这些时间区间的最⼤不相交⼦集。

按完成时间从早到晚将活动排序

1.  选取排序后的第一个活动a1（即最早结束的活动）
2.  在a1结束时间之前，删除所有已经始时间的活动（即和a1有重叠）
3.  递归地解决剩余活动的问题

public int intervalSchedule(int[][] intvs) { 
    	if (intvs.length == 0) return 0;
    	// 按 end 升序排序
    	Arrays.sort(intvs, new Comparator<int[]>() { 
    		public int compare(int[] a, int[] b) { 
    			return a[1] - b[1];
    		}
    	});
    	// ⾄少有⼀个区间不相交
    	int count = 1;
    	// 排序后，第⼀个区间就是 x
    	int x_end = intvs[0][1];
    	for (int[] interval : intvs) { 
    		int start = interval[0];
    		if (start >= x_end) { 
    			// 找到下⼀个选择的区间了
    			count++;
    			x_end = interval[1];
    		}
    	}
    	return count;
    }

#### 部分背包问题 ####

总是优先选择单位重量下价值最大的物品

1.  将每个背包按单位重量的价值从大到小排序
2.  每次剩余的性价比最大的加入到背包中
3.  或者剩余容量不够将整个背包加入的话，则用当前背包的部分去填满剩余空间

Arrays.sort(packages, new Comparator<Package>() { 
      @Override
      public int compare(Package o1, Package o2) { 
        return o2.value/o2.weight - o1.value/o1.weight;
      }
    });
    for(int i = 0; i < len; i ++) { 
      if(remind >= w[i]) { 
        res += v[i];
        remind -= w[i];
      }else { 
        res += remind * v[i] / w[i];
        break;
      }
    }
    return res;

#### 期末总结 ####

1.  小题考察了**渐进上界、渐进下界、紧致界**的求解。还考察了几种**常用算法的复杂度**以及几种算法的**概念**和**典型应用**场景。
2.  大题分为两部分，第一部分是用**master方法**求解三个递归式的复杂度（公式记错了，尴尬）
    
    第二部分是算法分析与设计题，题目都是比较典型的题目。
    
    分治：**快排**的过程
    
    动规: **最大子段和 最长回文子序列 0-1背包问题**
    
    贪心： **部分背包 迪杰斯特拉**

考完分享复习笔记，过过过！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/9a72c24504d84393ac9960c05e9c015d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/2692774150d347619a5bfa95f3ea2f86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/a38b3c9d959c4897b430b11be8849756.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDc1OTE0_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/f165a28c51f6494e8761fbfff968d467.png