知识点

知识点
1. 分治算法详解
  1. 分治算法是什么：
    
    分治算法是是一种算法思想，通过将原问题分解成小规模的子问题，然后根据子问题的结果构造出原问题的答案。
    
    这有点类似动态规划，所以说运用分治算法也需要满足一些条件：你的原问题结果应该可以通过合并子问题结果来计算
2. 阶乘相关的算法题目
  1. 阶乘后的零
    
    阶乘的时间复杂度最高，因此不可能直接计算然后得出。
    
    首先，两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，因为 10 = 2 x 5。
    
    也就是说，问题转化为：n!最多可以分解出多少个因子 2 和 5？
    
    同时，因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多得多，所以n!最多可以分解出多少个因子 2 和 5只和因子 5相关。
    
    所以问题又可以转化为：n!最多可以分解出多少个因子 5，难点在于像 25，50，125 这样的数，可以提供不止一个因子 5，怎么才能不漏掉。
    
    例如125!有多少个因子5：首先，125 / 5 = 25，这一步就是计算有多少个像 5，15，20，25 这些 5 的倍数，它们一定可以提供一个因子 5；我们再计算出125!中有 125 / 25 = 5 个 25 的倍数，它们每人可以额外再提供一个因子 5；我们还得再计算出125!中有 125 / 125 = 1 个 125 的倍数，它还可以额外再提供一个因子 5；最后，没有更高的倍数了。125!最多可以分解出 20 + 5 + 1 = 26 个因子 5，也就是说阶乘结果的末尾有 26 个 0
3. 接雨水问题
  
  首先，暴力解法：
  
  对于这种问题，我们不要想整体，而应该去想局部，具体来说，仅仅对于位置i，能装下多少水，位置i能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，我们分别称这两个柱子高度为l_max和r_max；位置 i 最大的水柱高度就是min(l_max, r_max)，因此位置i能够装的水为:
```
 // height[0..i]代表i左边的所有柱子，height[i..j]代表i右边的所有zhuz
 val[i] = min(max(height[0..i]), max(height[i..j])) - height[i];
```
  根据上述思路，写出暴力解法：
```
 public int trap(int[] height) {

 int res = 0;

 // 遍历所有柱子
 for (int i = 0; i < height.length; i++) {
     int lmax = 0, rmax = 0;
     // 寻找左右最高的柱子
     for (int m = i; m >= 0; m--) {
         lmax = Math.max(lmax, height[m]);
     }
     for (int n = i; n < height.length; n++) {
         rmax = Math.max(rmax, height[n]);
     }
     // 将i位置能够装的水加入结果中
     res = res + (Math.min(lmax, rmax) - height[i]);
 }

 // 返回结果
 return res;

}
```
  暴力解法，时间复杂度为O(N^2)，空间复杂度为O(1)
  
  暴力解法的优化：
  
  暴力解法中，每个位置i都要计算r_max和l_max。如果我们提前计算出每个i的l_max和r_max，就不用每次都计算了。
  
  开辟两个长度为i的数组lmax和rmax，记录在i位置的左边最高的柱子高度和右边最高的柱子高度，然后套用暴力解法的思路即可：
```
 public int trap(int[] height) {

 if (height.length == 0) return 0;

 int res = 0;

 // 定义两个数组
 int[] lmaxArr = new int[height.length];
 int[] rmaxArr = new int[height.length];
 // 填充值
 lmaxArr[0] = height[0];
 for (int i = 1; i < height.length; i++) {
     lmaxArr[i] = Math.max(height[i], lmaxArr[i - 1]);
 }
 rmaxArr[height.length - 1] = height[height.length - 1];
 for (int i = height.length - 2; i >= 0; i--) {
     rmaxArr[i] = Math.max(height[i], rmaxArr[i + 1]);
 }

 // 遍历所有柱子
 for (int i = 0; i < height.length; i++) {
     int lmax = lmaxArr[i], rmax = rmaxArr[i];
     // 将i位置能够装的水加入结果中
     res = res + (Math.min(lmax, rmax) - height[i]);
 }

 // 返回结果
 return res;

}
```
  优化后的暴力解法，时间复杂度为O(N)，空间复杂度O(N)
  
  双指针解法：
  
  该解法思路和上述的一样，也是拆解到每个i然后计算，但在实现手法上非常巧妙，我们不需要用备忘录提前计算了，而是用双指针边走边算，节省下空间复杂度

LeetCode算法题

LeetCode算法题
1. 241.【为运算表达式设计优先级】
  
  解题思路：
  
  首先，题目的意思：给你输入一个算式，你可以给它随意加括号，请你穷举出所有可能的加括号方式，并计算出对应的结果
  
  本题的关键是：1、不要首先考虑整个字符串，而是把目光聚焦局部，只看一个运算符；2、明确递归函数的定义
  
  第一步，首先考虑如何穷举出所有加括号的形式。穷举出所有加括号的形式思考起来很难，因为括号之间可以嵌套，但是嵌套可以通过递归来解决，因此我们只需要思考，如果不让括号嵌套（即只加一层括号），有几种加括号的方式。对于某个算式，只加一层括号的所有方式，其实就是按照运算符进行分割，给每个运算符的左右两部分算式加括号。根据递归的思路，括号嵌套的所有情况也可以列出来了。
  
  第二步，上述第一步过程就是分治算法中拆解问题的部分，接下来就是治的过程。第二个关键点，明确函数的定义，函数定义应该就是计算加括号形式产生的不同结果。
  
  注意，该函数的base case。递归函数必须有个 base case 用来结束递归，其实这段代码就是我们分治算法的 base case，代表着你「分」到什么时候可以开始「治」，我们是按照运算符进行「分」的，一直这么分下去，当算式中不存在运算符的时候就可以结束了。算式没有运算符，则直接返回该数字即可。
  
  至此，利用分治算法的思想，就可以解决该问题了：
```
 public List<Integer> diffWaysToCompute(String expression) {
 // 结果的集合
 List<Integer> res = new LinkedList<>();

 // 遍历算式，按照运算符切割算式
 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 a: left) {
             for (int b: right) {
                 if (c == '+') {
                     res.add(a + b);
                 } else if (c == '-') {
                     res.add(a - b);
                 } else if (c == '*') {
                     res.add(a * b);
                 }
             }
         }
     }
 }

 // base case。如果算式是个数字，则res为空，直接将该数字返回
 if (res.size() == 0) {
     res.add(Integer.parseInt(expression));
 }

 // 返回结果
 return res;
}
```
2. 172.【阶乘后的零】
  
  解题思路：
  
  如上述的知识点所述，最终代码为：
```
public int trailingZeroes(int n) {

 // 记录有多少个0
 int res = 0;

 long divisor = 5;
 while (divisor <= n) {
     res += n / divisor;
     divisor *= 5;
 }
 return res;

}
```
3. 42.【接雨水】
  
  解题思路：
  
  使用双指针解法或优化后的暴力解法来做。
4. 102.【二叉树的层序遍历】
  
  解题思路：
  
  简单的BFS即可解决
5. 103.【二叉树的锯齿形层序遍历】
  
  解题思路：
  
  使用BFS进行二叉树遍历，使用双端队列维护当前层节点值输出的顺序（从后面插入就是从左往右遍历，从前面插入就是从右往左遍历）

2021/06/17 今日算法

知识点

LeetCode算法题