今日任务：

1. LeetCode62 不同路径
2. LeetCode63 不同路径 Ⅱ



资料来源：

1. [代码随想录 | LeetCode62 不同路径](https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html)
2. [代码随想录 | LeetCode63 不同路径 Ⅱ](https://programmercarl.com/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.html)

### 1 LeetCode62 不同路径

:::info{title="题目"}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

 

示例 1：

![image.png](https://www.misaka19327.cc/static/img/e4564ba9068dbdc6ae566243f89e7fc6.image.png)
```
输入：m = 3, n = 7
输出：28
```
示例 2：
```
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
```
示例 3：
```
输入：m = 7, n = 3
输出：28
```
示例 4：
```
输入：m = 3, n = 3
输出：6
```

提示：

- 1 <= m, n <= 100
- 题目数据保证答案小于等于 $$2 * 10 ^ 9$$
:::

很经典的两层数组的动态规划，还是按照动态规划五部曲走：

1. dp数组的含义和下标含义：从起点到达当前位置的可能的路径数量
2. 确定递推公式：`dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1]`
3. dp数组初始化：第一横行和第一竖行全部初始化为1，意味着从起点到达这些点的可能路径只有1条。由于n，m可能为1，所以`dp_array[0][0]`也得初始化为1
4. 确定遍历顺序：先行后列还是先列后行没有影响
5. 举例推导：以用例1为例，它的dp数组应该是：
    
    | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
    | --- | --- | --- | --- | --- | --- | --- |
    | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
    | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
    
    可见没有问题
    
:::tip{title="提示"}
另外，这题还有一个数论的解法。首先，对于给定的m，n，从起点走到终点一定会走$$m + n - 2$$步，而且其中一定有$$m - 1$$步是向下走的，别管什么时候向下走。那也就是说，这题可以转化为一个数学问题：在$$m + n - 2$$个数中，挑出$$m - 1$$个数，可以有多少种挑法？结果就是$$C^{m - 1}_{m + n - 2}$$。
:::


``` python
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 初始化
        dp_array = [[0] * n] * m
        for i in range(n):
            dp_array[0][i] = 1
        for i in range(m):
            dp_array[i][0] = 1

        # 开始dp
        for i in range(1, m):
            for j in range(1, n):
                dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1]

        return dp_array[-1][-1]
```

``` java
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp_array = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp_array[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp_array[0][i] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp_array[i][j] = dp_array[i - 1][j] + dp_array[i][j - 1];
            }
        }
        return dp_array[m - 1][n - 1];
    }
}
```

``` go
func uniquePaths(m int, n int) int {
    dpArray := make([][]int, m)
    for i := range dpArray {
        dpArray[i] = make([]int, n)
        dpArray[i][0] = 1
    }
    for i := range dpArray[0] {
        dpArray[0][i] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dpArray[i][j] = dpArray[i - 1][j] + dpArray[i][j - 1]
        }
    }
    return dpArray[m - 1][n - 1]
}
```

### 2 LeetCode63 不同路径 Ⅱ

:::info{title="题目"}
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

![image.png](https://www.misaka19327.cc/static/img/92f6af59950f735b340f54e9b4052c82.image.png)
```
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
```
示例 2：
```
输入：obstacleGrid = [[0,1],[0,0]]
输出：1
```

提示：

- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
:::

~~不是，这题给的用例也太坑，完全看不出来这二维数组是按行存的还是按列存的气死个人。~~

这题的思路和上面的62是完全一致的，但是有的地方不一样。一方面是遍历dp数组的过程中，如果遇到障碍，说明这块是永远不可抵达的，所以要将其置为0；另一方面是初始化dp数组的过程中，如果遇到障碍，那么从这个障碍之后的所有位置都要置0，因为初始化的那一行/列本来就只有一条路，有个障碍在那里直接就把这一条路堵死了。

``` python
from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        if obstacleGrid[0][0] == 1:
            return 0
        # 这题的obstacleGrid是按列存的 obstacleGrid[i]代表的是一列的数据 注意
        # 初始化
        for i in range(1, len(obstacleGrid)):  # 因为是一旦遇到障碍 后面赋值为0 所以不能从头开始循环 否则下一个初始化会有问题
            if obstacleGrid[i][0] == 0:
                obstacleGrid[i][0] = 1
            else:
                # 一旦遇到障碍 后面全部赋值为0
                obstacleGrid[i][0] = 0
                if i < len(obstacleGrid) - 1:
                    obstacleGrid[i + 1][0] = 1
        for i in range(len(obstacleGrid[0])):
            if obstacleGrid[0][i] == 0:
                obstacleGrid[0][i] = 1
            else:
                obstacleGrid[0][i] = 0
                if i < len(obstacleGrid[0]) - 1:
                    obstacleGrid[0][i + 1] = 1

        for i in range(1, len(obstacleGrid)):
            for j in range(1, len(obstacleGrid[0])):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]

        return obstacleGrid[-1][-1]
```

``` java
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0;
        for (int i = 1; i < obstacleGrid.length; i++) {
            if (obstacleGrid[i][0] == 0) {
                obstacleGrid[i][0] = 1;
            } else {
                obstacleGrid[i][0] = 0;
                if (i < obstacleGrid.length - 1) {
                    obstacleGrid[i + 1][0] = 1;
                }
            }
        }
        for (int i = 0; i < obstacleGrid[0].length; i++) {
            if (obstacleGrid[0][i] == 0) {
                obstacleGrid[0][i] = 1;
            } else {
                obstacleGrid[0][i] = 0;
                if (i < obstacleGrid[0].length - 1) {
                    obstacleGrid[0][i + 1] = 1;
                }
            }
        }

        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }
        return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}
```

``` go
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	if obstacleGrid[0][0] == 1 {
		return 0
	}
	for i := 1; i < len(obstacleGrid); i++ {
		if obstacleGrid[i][0] == 1 {
			obstacleGrid[i][0] = 0
			if i < len(obstacleGrid) - 1 {
				obstacleGrid[i+1][0] = 1
			}
		} else {
			obstacleGrid[i][0] = 1
		}
	}
	for i := 0; i < len(obstacleGrid[0]); i++ {
		if obstacleGrid[0][i] == 1 {
			obstacleGrid[0][i] = 0
			if i < len(obstacleGrid[0]) - 1 {
				obstacleGrid[0][i + 1] = 1
			}
		} else {
			obstacleGrid[0][i] = 1
		}
	}
	for i := 1; i < len(obstacleGrid); i++ {
		for j := 1; j < len(obstacleGrid[0]); j++ {
			if obstacleGrid[i][j] == 1 {
				obstacleGrid[i][j] = 0
			} else {
				obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
			}
		}
	}
	return obstacleGrid[len(obstacleGrid) - 1][len(obstacleGrid[0]) - 1]
}
```

代码随想录算法训练营第三十九天 | LeetCode62 不同路径、LeetCode63 不同路径 Ⅱ

今日任务：

1. 动态规划理论基础
2. LeetCode509 斐波那契数
3. LeetCode70 爬楼梯
4. LeetCode746 使用最少花费爬楼梯



资料来源：

1. [代码随想录 | 动态规划理论基础](https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)
2. [代码随想录 | LeetCode509 斐波那契数](https://programmercarl.com/0509.%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0.html)
3. [代码随想录 | LeetCode70 爬楼梯](https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF.html)
4. [代码随想录 | LeetCode746 使用最少花费爬楼梯](https://programmercarl.com/0746.%E4%BD%BF%E7%94%A8%E6%9C%80%E5%B0%8F%E8%8A%B1%E8%B4%B9%E7%88%AC%E6%A5%BC%E6%A2%AF.html)

### 1 动态规划理论基础

先贴个图在这：

![image.png](https://www.misaka19327.cc/static/img/cf61ebaae6d72145d1f32ed06835df6a.image.png)

动态规划算法，是用于解决由许多重叠子问题组成的问题的算法。动态规划中，每个状态都是由上一个状态推导而来，这一点区别于贪心算法。比如说背包问题，动态规划每次都需要根据上一个状态来确定下一次拿什么物品，而贪心算法就不用，贪心直接可着最有价值的拿就是了。

动态规划五部曲：

1. 确定dp数组和下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

### 2 LeetCode509 斐波那契数

:::info{title="题目"}
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

 

示例 1：
```
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
```
示例 2：
```
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
```
示例 3：
```
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
```

提示：

- 0 <= n <= 30
:::

一道简单的动态规划。按照五部曲走就是：

1. 确定dp数组及下标含义：存储斐波那契数，每个下标对应该下标的斐波那契数
2. 确定递推公式：`array[i] = array[i - 1] + array[i - 2]`
3. dp数组如何初始化：第1个和第2个元素初始化为0和1
4. 确定遍历顺序：从前向后
5. 举例推导dp数组：0，1，2，3，5，8，13，21，34，55，没有问题。

``` python
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        dp_array = [0] * (n + 1)
        dp_array[1] = 1
        for i in range(2, n + 1):
            dp_array[i] = dp_array[i - 1] + dp_array[i - 2]
        return dp_array[-1]
```        

### 2 LeetCode70 爬楼梯

:::info{title="题目"}
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

 

示例 1：
```
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
```
示例 2：
```
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
```

提示：

- 1 <= n <= 45
:::

同斐波那契数。另外这道题还有个plus版本，就是如果一次能爬的台阶有1或2或3或4或...或m个，那么有多少种爬楼的方法。这个只需要在递推那块反向遍历一下，取前m个台阶位置的走法的和即可。

``` python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        dp_array = [0] * n
        dp_array[0] = 1
        dp_array[1] = 2
        for i in range(2, n):
            dp_array[i] = dp_array[i - 1] + dp_array[i - 2]
        return dp_array[-1]
```        

### 3 LeetCode746 使用最少花费爬楼梯

:::info{title="题目"}
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

 

示例 1：
```
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
```
示例 2：
```
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。
```

提示：

- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
:::

爬楼梯的plus版本。还是按五部曲走：

1. dp数组和下标的含义：到达第i个台阶时所花费的最少费用
2. 确定递推公式：`array[i] = min(cost[i - 1] + array[i - 1], cost[i - 2] + array[i - 2])`
3. dp数组初始化：题目给定的是从下标为0的台阶和下标为1的台阶出发都可以，那么array[0]和array[1]花费都为0，初始化为0
4. 遍历顺序：从前往后
5. 举例推导dp数组：示例1，0，0，15，没有问题

``` python
from typing import List

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp_array = [0] * (len(cost) + 1)
        for i in range(2, len(dp_array)):
            dp_array[i] = min(dp_array[i - 1] + cost[i - 1], dp_array[i - 2] + cost[i - 2])
        return dp_array[-1]
```

代码随想录算法训练营第三十八天 | LeetCode509 斐波那契数、LeetCode70 爬楼梯、LeetCode746 使用最少花费爬楼梯

今日任务：

1. LeetCode738 单调递增的数字
2. LeetCode968 监控二叉树
3. 贪心算法总结



资料来源：

1. [代码随想录 | LeetCode738 单调递增的数字](https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html)
2. [代码随想录 | LeetCode968 监控二叉树](https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html)
3. [代码随想录 | 贪心算法总结](https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html)

### 1 LeetCode738 单调递增的数字

:::info{title="题目"}
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

 

示例 1:
```
输入: n = 10
输出: 9
```
示例 2:
```
输入: n = 1234
输出: 1234
```
示例 3:
```
输入: n = 332
输出: 299
```

提示:

- 0 <= n <= $$10 ^ 9$$
:::

这题一开始看的时候的想法就是，这跟贪心有关系吗，不知道怎么贪。在看示例3的时候有了感觉，从后往前检查，如果有遇到**不是单调的两个数字，比它小的最大的数字一定是较大的数位-1，较小的数位为9的**。比如说332，从后往前检查的第一个就是2和3，如果要找比它小的而且是单调的，那么一定是2变成9，3变成2，这样整体就变成了329，再继续检查这个新的2和3，2 -> 9，3 -> 2，就得到了299。

另外，一旦有一个数位被置为9，那么比它小的所有数位都需要再置为9，以保证之前检查过的数位的单调性。比如说100，第一次检查0和0，是单调的；第二次检查1和0的时候就不是单调的了，这时需要将1 -> 0，0 -> 9，那么此时这个数字整体就是90，但是它不是单调数字，之前检查过的0失去了单调性，需要重新置为9。

``` python
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        n = str(n)
        n = list(n)
        n.reverse()
        n = list(map(int, n))
        
        pointer_9 = 0  # 列表已经反转 终点即是起点
        for i in range(len(n) - 1):
            if n[i] < n[i + 1]:
                pointer_9 = i
                n[i] = 9
                n[i + 1] -= 1

        for i in range(pointer_9):  # 按反转顺序来 置9
            n[i] = 9
            
        n.reverse()
        n = list(map(str, n))
        return int("".join(n))
```

### 2 LeetCode968 监控二叉树

:::info{title="题目"}
给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

 

示例 1：
```
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
```
示例 2：
```
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
```
提示：

- 给定树的节点数的范围是 [1, 1000]。
- 每个节点的值都是 0。
:::

这题的贪心很容易想到，那就是所有的叶子节点不能有摄像头，从叶子节点的父节点一级开始，竖方向上每隔两个节点设置一个摄像头，直到根节点。

首先，从上往下肯定是后序遍历没跑了；其次，因为给定的二叉树并没有限制对二叉树的读写，所以可以在遍历中使用。一个节点，它的状态可以是未覆盖、已被覆盖或者已设置摄像头三种情况。如果要实现思路，首先遍历中遇见叶子节点肯定是直接跳了；其次，如果左节点和右节点都是已覆盖区域，也可以直接跳过，由该节点的父节点来设置摄像头，这样就达成了“**竖方向上每隔两个节点设置一个摄像头**”；之后，如果左节点/右节点有未覆盖区域，那么为了保证所有区域都被覆盖，该节点必须设置一个摄像头；最后，如果左节点/右节点有摄像头，则设置该节点为已覆盖。注意后两个判断顺序不能变，防的就是一个节点的子节点一个有摄像头，一个是未覆盖，这时候必须给该节点上一个摄像头。

最后，因为检查都是对该节点的子节点进行检查，所以根节点并没有被检查过，所以最后必须给根节点单独检查是否是未覆盖，如果是就给根节点多加一个摄像头。（也可以给根节点多加一个虚拟的父节点，从虚拟父节点开始后序遍历来解决）

``` python
from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        if root.left is None and root.right is None:
            return 1
        monitor_number = 0
        stack = deque()
        stack.append(root)
        while len(stack) > 0:
            node = stack.pop()
            if node is None:
                node = stack.pop()
                # 规定0是未覆盖 1是有覆盖 2是有摄像头
                if node.left is None and node.right is None:
                    continue  # 叶子节点 不作处理
                if (node.left is not None and node.left.val == 1) and (node.right is not None and node.right.val == 1):
                    continue  # 左节点和右节点都是覆盖区域 不作处理
                if (node.left is not None and node.left.val == 0) or (node.right is not None and node.right.val == 0):
                    monitor_number += 1
                    node.val = 2
                    continue  # 左节点/右节点有未覆盖区域
                # 先检查子节点是否有未覆盖区域 再检查子节点有无摄像头 保证优先对未覆盖区域进行覆盖
                if (node.left is not None and node.left.val == 2) or (node.right is not None and node.right.val == 2):
                    node.val = 1
                    continue  # 左节点/右节点有摄像头 修改状态为有覆盖
            else:
                stack.append(node)
                stack.append(None)
                if node.right is not None:
                    stack.append(node.right)
                if node.left is not None:
                    stack.append(node.left)
        if root.val == 0:  # 因为遍历时都是对遍历节点的子节点进行检查 所以根节点并没有检查过是否被覆盖 在这里进行检查
            monitor_number += 1
        return monitor_number
```

### 3 贪心算法总结

贪心没有框架，没有显著的题目特征，就区间问题还算是比较典型的贪心题目，只能多做了，嫖个图在这。

![image.png](https://www.misaka19327.cc/static/img/e7611d3d6bf293254afac66a60dd808a.image.png)

代码随想录算法训练营第三十七天 | LeetCode738 单调递增的数字、LeetCode968 监控二叉树

记录实验2过程及代码。



注意Tomcat10 -> `jakarta.servlet-api`，Tomcat9以下 -> `javax.servlet-api`。

### 1 创建 Servlet 项目

``` java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;

@WebServlet(value = "/FirstServlet")
public class FirstServlet extends HttpServlet { // 继承HttpServlet
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {  // 重写doGet
        super.doGet(req, resp);
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException { // 重写doPost
        super.doPost(req, resp);
    }
}
```

### 2 处理并展示请求信息

``` java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletContext;
import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;
import java.io.PrintWriter;

@WebServlet(value = "/SecondServlet")
public class SecondServlet extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        String parameter1 = req.getParameter("parameter1");  // 获取请求参数
        String header = req.getHeader("parameter2");  // 获取http头信息
        ServletContext context = getServletContext();
        context.log(parameter1); // 输出到log里
        context.log(header);
        PrintWriter out = resp.getWriter();
        out.println(parameter1); // 输出到响应体里
        out.println(header);
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        super.doPost(req, resp);
    }
}
```

实际效果：

> ApiFox需要先设置好前置URL：
> 
> ![](https://www.misaka19327.cc/static/img/57b50dd9bea8b8fe372f9b2c4d96260a.image.png)

![image.png](https://www.misaka19327.cc/static/img/3ac0b782444ad5e88ff0c3af47c21ab3.image.png)

![image.png](https://www.misaka19327.cc/static/img/4d48fa81ad03d28291a22cd0c4454732.image.png)

![image.png](https://www.misaka19327.cc/static/img/3f744469c9b6509fb8f62490db04642f.image.png)

（要达到上图这个效果，需要先在运行配置里的log部分显示所有的log，然后在右侧筛选处选择all）

### 3 请求转发实践

``` java
// ThirdServlet_1.java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;

@WebServlet(value = "/ThirdServlet_1")
public class ThirdServlet_1 extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        req.getRequestDispatcher("/ThirdServlet_2").forward(req, resp); // 转发
        log("Request Forwarded");
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        super.doPost(req, resp);
    }
}

// ThirdServlet_2.java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;

@WebServlet(value = "/ThirdServlet_2")
public class ThirdServlet_2 extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        log(req.getParameter("parameter")); // 收到请求 输出log
        log("Request Received");
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        super.doPost(req, resp);
    }
}
```

效果：

![image.png](https://www.misaka19327.cc/static/img/b4eddb94c85c1a5f61544cd709c553e1.image.png)

![image.png](https://www.misaka19327.cc/static/img/b86cf83fe8d7233bf66731e4aa9ff998.image.png)

### 4 重定向实践

``` java
// FourthServlet_1.java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;

@WebServlet(value = "/FourthServlet_1")
public class FourthServlet_1 extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        resp.setStatus(302); // 设置状态码
        resp.setHeader("Location", "/WebStructure/FourthServlet_2"); // 重定向
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        super.doPost(req, resp);
    }
}

// FourthServlet_2.java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;

@WebServlet(value = "/FourthServlet_2")
public class FourthServlet_2 extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        log("Request Received"); // 收到请求 打印log
        super.doGet(req, resp);
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        super.doPost(req, resp);
    }
}
```

效果：

![image.png](https://www.misaka19327.cc/static/img/7cb3b8d50ca2b3280d32226a5467d090.image.png)


![image.png](https://www.misaka19327.cc/static/img/edfb7db82dc75a64e75c9b41428de5d1.image.png)

### 5 包含实践

``` java
// FifthServlet_1.java
package org.example.webstructure.experiment2;

import com.google.gson.Gson;
import jakarta.servlet.RequestDispatcher;
import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;
import java.io.PrintWriter;

@WebServlet(value = "/FifthServlet_1")
public class FifthServlet_1 extends HttpServlet {

    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        RequestDispatcher requestDispatcher = req.getRequestDispatcher("/FifthServlet_2"); // 设定目标资源路径
        requestDispatcher.include(req, resp); // 包含
        PrintWriter printWriter = resp.getWriter();
        printWriter.write("Wrote from FifthServlet_1\n"); // 写入
    }

    @Override
    protected void doPut(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        super.doPut(req, resp);
    }
}

// FifthServlet_2.java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;
import java.io.PrintWriter;

@WebServlet(value = "/FifthServlet_2")
public class FifthServlet_2 extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        PrintWriter printWriter = resp.getWriter();
        printWriter.write("Wrote from FifthServlet_2\n"); // 写入
    }
}
```

效果：

![image.png](https://www.misaka19327.cc/static/img/2fa59a0882b66d8dc71f40204e9d4106.image.png)

### 6 Cookie实践

``` java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.Cookie;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;

import java.io.IOException;
import java.time.LocalDateTime;

@WebServlet(value = "/SixthServlet")
public class SixthServlet extends HttpServlet {

    LocalDateTime time = null;

    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        resp.addCookie(new Cookie("parameter1", "value1"));
        if (this.time == null) {
            this.time = LocalDateTime.now();
        } else {
            resp.addCookie(new Cookie("lastLoginTime", this.time.toString()));
            this.time = LocalDateTime.now();
        }
    }
}
```

效果：

第一次请求：

![image.png](https://www.misaka19327.cc/static/img/d83151a15470e21927daf8218e3b3a9e.image.png)

第二次请求：

![image.png](https://www.misaka19327.cc/static/img/c42630508b170e10b0dc9b2fa922f4c9.image.png)

### 7 Session 实践

``` java
// SeventhServlet_1.java
package org.example.webstructure.experiment2;

import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;
import jakarta.servlet.http.HttpSession;

import java.io.IOException;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

@WebServlet(value = "/SeventhServlet_1")
public class SeventhServlet_1 extends HttpServlet {

    Map<String, String> userInfo = new HashMap<String, String>(); // 假装这是数据库

    @Override
    public void init() throws ServletException {
        this.userInfo.put("user1", "123456"); // 数据库里有用户user1 密码是123456
    }

    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        super.doGet(req, resp);
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        String name = req.getParameter("userName"); // 获取参数
        String password = req.getParameter("userPassword");
        PrintWriter out = resp.getWriter();
        if (Objects.equals(this.userInfo.get(name), password)) { // 登录验证
            HttpSession httpSession = req.getSession();
            httpSession.setAttribute("user", new UserEntity(name, password)); // 用户信息存储到 HttpSession 对象中
            out.write("Login Success!\n");
        } else {
            out.write("UserName or UserPassword is Incorrect!\n");
        }
    }
}

// SeventhServlet_2.java
package org.example.webstructure.experiment2;

import com.google.gson.Gson;
import jakarta.servlet.ServletException;
import jakarta.servlet.annotation.WebServlet;
import jakarta.servlet.http.HttpServlet;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;
import jakarta.servlet.http.HttpSession;

import java.io.IOException;
import java.io.PrintWriter;

@WebServlet(value = "/SeventhServlet_2")
public class SeventhServlet_2 extends HttpServlet {

    Gson gson = new Gson(); // 生成Json字符串用的

    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        UserEntity user = (UserEntity) req.getSession().getAttribute("user"); // 先尝试获取用户信息
        if (user == null) { // 这就说明还没登录
            resp.getWriter().write("User is not Logged In!");
            return;
        }
        int operation = Integer.parseInt(req.getParameter("operation")); // 获取操作
        PrintWriter out = resp.getWriter();
        switch (operation) {
            case 1: {
                user.addGood(req.getParameter("goodName")); // 增
                break;
            }
            case 2: {
                user.deleteGood(req.getParameter("goodName")); // 删
                break;
            }
            case 3: {
                user.setGoodNumber(req.getParameter("goodName"),  Integer.parseInt(req.getParameter("goodNumber"))); // 改
                break;
            }
            default: {
                out.write("Operation not recognized");
                return;
            }
        }
        out.write(gson.toJson(user.shoppingCart)); // 查
    }
}

// UserEntity.java
package org.example.webstructure.experiment2;

import java.util.ArrayList;
import java.util.Objects;

// 用户数据类
public class UserEntity {
    String userName;
    String password;
    ArrayList<Good> shoppingCart = new ArrayList<>(); // 购物车信息

    public UserEntity(String userName, String password) {
        this.userName = userName;
        this.password = password;
    }

    // 增加商品
    public void addGood(String goodName) {
        for (Good good : this.shoppingCart) {
            if (Objects.equals(good.name, goodName)) {
                good.number += 1;
                return;
            }
        }
        this.shoppingCart.add(new Good(goodName, 1));
    }

    // 删除商品
    public boolean deleteGood(String goodName) {
        for (Good good : this.shoppingCart) {
            if (Objects.equals(good.name, goodName)) {
                this.shoppingCart.remove(good);
                return true;
            }
        }
        return false;
    }

    // 修改商品数量
    public void setGoodNumber(String goodName, int goodNumber) {
        for (Good good : this.shoppingCart) {
            if (Objects.equals(good.name, goodName)) {
                good.number = goodNumber;
                return;
            }
        }
        this.shoppingCart.add(new Good(goodName, goodNumber));
    }

    // 查询商品数量
    public int getGoodNumber(String goodName) {
        for (Good good : this.shoppingCart) {
            if (Objects.equals(good.name, goodName)) {
                return good.number;
            }
        }
        return -1;
    }
}

// 商品数据类
class Good {
    String name;
    int number;

    public Good(String name, int number) {
        this.name = name;
        this.number = number;
    }
}
```

效果：

登录失败：

![image.png](https://www.misaka19327.cc/static/img/c941f6eb378e8cb1479a2520155f4bb2.image.png)

登录成功：

![image.png](https://www.misaka19327.cc/static/img/c133bf7b6d4d1f0aac7e78be6fc82417.image.png)

![image.png](https://www.misaka19327.cc/static/img/14e3ae71a6267c2f7aae6e2ffdc7f0da.image.png)

登录后对购物车进行操作：

增加商品（goodNumber参数不必要）：

![image.png](https://www.misaka19327.cc/static/img/90e2239d14545b0a27ac9ea8151b5bdc.image.png)

删除商品（goodNumber参数不必要）：

![image.png](https://www.misaka19327.cc/static/img/69aeca2dbf35b66c516c254a0365a262.image.png)

修改商品数量：

![image.png](https://www.misaka19327.cc/static/img/5f442ec4de99b7ba4a34e3a73a265680.image.png)

没登录时直接对购物车进行操作：

![image.png](https://www.misaka19327.cc/static/img/538789661845a8e719629f0e42b53222.image.png)

Web体系结构与程序设计 实验2

今日任务：

1. LeetCode435 无重叠区间
2. LeetCode763 划分字母区间
3. LeetCode56 合并区间



资料来源：

1. [代码随想录 | LeetCode435 无重叠区间](https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html)
2. [代码随想录 | LeetCode763 划分字母区间](https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html)
3. [代码随想录 | LeetCode56 合并区间](https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html)

### 1 LeetCode435 无重叠区间

:::info{title="题目"}
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:
```
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
```
示例 2:
```
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
```
示例 3:
```
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
```

提示:

- 1 <= intervals.length <= $$10^5$$
- intervals[i].length == 2
- -5 * $$10^4$$ <= starti < endi <= 5 * $$10^4$$
:::

要找的是需要被移除的重叠区间的最小数量，那我反向去找没有重叠区间的最大数量，再用所有区间的数量减去求出的没有重叠区间的最大数量，就能得到答案。

求没有重叠区间的数量，首先需要对给定的输入区间进行排序。排序标准可以是区间开始位置，也可以是区间结束位置，两种思路大体相同，下面的代码的排序依据是区间结束位置，排序后从第一个区间开始找起，记录区间结束位置，然后对之后的区间的开始位置进行挨个比较：如果之后的区间的开始位置小于记录的结束位置，说明这个区间和记录的结束位置对应的区间重叠，继续看下一个区间；如果之后的区间的开始位置大于记录的结束位置，说明这个区间和结束位置对应的区间不重叠，没有重叠区间的数量+1，将记录的结束位置更新为这个区间的结束位置，继续找和这个区间不重叠的下一个区间，直到循环结束。如果按照区间开始位置进行排序，比较思路也不变。

另外，这道题可以用上一道射气球题的思路来做，那道题在实际上找的是最少的不重叠区间。

``` python
from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        non_overlap_num = 0
        pointer = intervals[0][1]
        length = 0
        for i in intervals:
            length += 1
            if i[0] < pointer:  # 记录的区间结束位置和每个区间的开始位置比较
                continue
            else:
                non_overlap_num += 1
                pointer = i[1]
        return length - (non_overlap_num + 1)  # 因为循环结束后最后一个区间没加上 这里再加上
```

### 2 LeetCode763 划分字母区间

:::info{title="题目"}
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：
```
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 
```
示例 2：
```
输入：s = "eccbbbbdec"
输出：[10]
```

提示：

- 1 <= s.length <= 500
- s 仅由小写英文字母组成
:::

首先先统计每个字母对应的区间起始和结束位置（这个统计过程其实也就自动排序了），然后还是记录区间的结束位置，挨个和之后区间的结束位置对比，如果区间的结束位置小于记录位置，就说明记录位置对应的区间能够完全将当前区间包括住；如果区间的结束位置大于记录位置，看区间的起始位置是否大于记录位置：如果是，则说明当前区间和记录位置对应的区间是不重叠的，在这里划分；如果不是，则说明重叠，修改记录的结束位置到当前区间的结束位置，继续循环对比。

``` python
from typing import List

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        map = dict()
        for i in range(len(s)):  # 统计字母区间
            if s[i] not in map.keys():
                map[s[i]] = [i, i]
            else:
                map[s[i]][1] = i
        result = []
        processed_length = 0
        pointer = list(map.values())[0][1]
        for i in map.values():
            if i[1] < pointer:
                continue
            else:
                if i[0] > pointer:  # 划分
                    result.append(pointer - processed_length + 1)
                    processed_length = pointer + 1
                    pointer = i[1]
                else:
                    pointer = i[1]
        result.append(pointer - processed_length + 1)
        return result
```        

另外这个题还有一种思路，划分字符串其实只需要找到每个字符的最远的边界，划分的点就是那个能够包括之前所有字符的边界的最远的边界点。所以可以进行两次循环：第一次就是确定每个字符的最远边界，第二次循环中，如果循环的索引和当前索引的字符的最远边界相同，就是要划分的位置。

![image.png](https://www.misaka19327.cc/static/img/ea012f01df544d795d5a3dc6323fee10.image.png)

### 3 LeetCode56 合并区间

:::info{title="题目"}
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

 

示例 1：
```
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
```
示例 2：
```
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
```

提示：

- 1 <= intervals.length <= $$10^4$$
- intervals[i].length == 2
- 0 <= starti <= endi <= $$10^4$$
:::

还是找重叠的区间，只是这次需要同时记录起始位置和结束位置。

``` python
from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        start = intervals[0][0]
        end = intervals[0][1]
        result = []
        for i in intervals:
            if i[0] <= end:  # 重叠
                end = max(end, i[1])
            else:  # 不重叠
                result.append([start, end])
                start = i[0]
                end = i[1]
        result.append([start, end])
        return result
```