今日任务：

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
```

代码随想录算法训练营第三十六天 | LeetCode435 无重叠区间、LeetCode763 划分字母区间、LeetCode56 合并区间

今日任务：

1. LeetCode860 柠檬水找零
2. LeetCode406 根据身高重建队列
3. LeetCode452 用最少数量的箭引爆气球



资料来源：

1. [代码随想录 | LeetCode860 柠檬水找零](https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html)
2. [代码随想录 | LeetCode406 根据身高重建队列](https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html)
3. [代码随想录 | LeetCode452 用最少数量的箭引爆气球](https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html)

### 1 LeetCode860 柠檬水找零

:::info{title="题目"}
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

 

示例 1：
```
输入：bills = [5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
```
示例 2：
```
输入：bills = [5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
```

提示：

- 1 <= bills.length <= $$10^5$$
- bills[i] 不是 5 就是 10 或是 20 
:::

遇见了以前写过的题可还行，这题就是优先去消耗10块，再消耗5块就行。

``` python
from typing import List

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five_bill_num = 0
        ten_bill_num = 0
        for bill in bills:
            if bill == 5:
                five_bill_num += 1
            elif bill == 10:
                five_bill_num -= 1
                ten_bill_num += 1
            else:
                if ten_bill_num > 0:
                    ten_bill_num -= 1
                    five_bill_num -= 1
                else:
                    five_bill_num -= 3
            if five_bill_num < 0 or ten_bill_num < 0:
                return False
        return True
```        

### 2 LeetCode406 根据身高重建队列

:::info{title="题目"}
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

 

示例 1：
```
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
```
示例 2：
```
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
```

提示：

- 1 <= people.length <= 2000
- 0 <= hi <= $$10^6$$
- 0 <= ki < people.length
- 题目数据确保队列可以被重建
:::

这题一开始看的时候完全没弄明白和贪心有什么关系，想了半天之后想到的思路就是先对$$k_i$$为0的人先按$$h_i$$进行升序排序，然后再对剩下$$k_i$$不是0的挨个插入到$$h_i$$后面的位置去。

下面这些代码的思路是先按$$h_i$$进行降序排序，如果$$h_i$$相同则按$$k_i$$升序排序。之后对排序后的数组进行循环，以$$k_i$$为索引直接插入新数组result即可。这样能够保证每次插入元素时，result里全部都是$$h_i$$大于等于要处理的元素的$$h_i$$，再按照$$k_i$$为下标插入就可以完美符合条件。

``` python
from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key=lambda x: (-x[0], x[1]))  # 先按x[0]进行降序排序，如果x[0]相同则按x[1]升序排序
        
        result = []
        for i in people:
            result.insert(i[1], i)

        return result
```

### 3 LeetCode452 用最少数量的箭引爆气球

:::info{title="题目"}
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

 
示例 1：
```
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。
```
示例 2：
```
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。
```
示例 3：
```
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。
```

提示:

- 1 <= points.length <= $$10^5$$
- points[i].length == 2
- $$-2^{31}$$ <= xstart < xend <= $$2^{31} - 1$$
:::

这是重叠区间问题，贪心贪在尽可能多的让同一支箭引爆尽可能重叠的气球（区间）。先对所有气球按区间开始位置排序，再循环并且记录区间结束位置（即气球的$$x_{end}$$），如果下一个区间的结束位置小于记录位置，那么说明这个气球和记录位置对应的气球完全重叠，为了引爆这个更小的气球（更小的区间），将记录位置改为这个更小的区间的结束位置；如果下一个区间的开始位置大于记录位置，那么说明下一个气球和记录位置对应的气球完全不重合，那就可以引爆之前的气球，并且将记录位置更新为下一个区间（气球）的结束位置。

``` python
from typing import List

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[0])
        result = 0
        arrow_x = points[0][1]
        for i in points:
            if i[1] < arrow_x:
                arrow_x = i[1]
            if i[0] > arrow_x:
                result += 1
                arrow_x = i[1]
        return result + 1
```