记录实验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
```

代码随想录算法训练营第三十五天 | LeetCode860 柠檬水找零、LeetCode406 根据身高重建队列、LeetCode452 用最少数量的箭引爆气球

今日任务：

1. LeetCode1005 K次取反后最大化的数组和
2. LeetCode134 加油站
3. LeetCode135 分发糖果



资料来源：

1. [代码随想录 | LeetCode1005 K次取反后最大化的数组和](https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html)
2. [代码随想录 | LeetCode134 加油站](https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html)
3. [代码随想录 | LeetCode135 分发糖果](https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html)

### 1 LeetCode1005 K次取反后最大化的数组和

:::info{title="题目"}
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

 

示例 1：
```
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
```
示例 2：
```
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
```
示例 3：
```
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
```

提示：

- 1 <= nums.length <= $$10^4$$
- -100 <= nums[i] <= 100
- 1 <= k <= $$10^4$$
:::

一个贪心是，尽量选择绝对值大的负数进行变换，另一个贪心是，如果没得负数可换了，就选择绝对值尽量小的数字反复变换。

``` python
from typing import List

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: abs(x), reverse=True)  # 绝对值排序
        index = 0
        while index < len(nums) - 1 and k > 0:
            if nums[index] < 0:
                nums[index] = -nums[index]
                k -= 1
            index += 1
        if k > 0:
            for i in range(k):
                nums[-1] = - nums[-1]
        return sum(nums)
```

### 2 LeetCode134 加油站

:::info{title="题目"}
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

 

示例 1:
```
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
```
示例 2:
```
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
```

提示:

- gas.length == n
- cost.length == n
- 1 <= n <= $$10^5$$
- 0 <= gas[i], cost[i] <= $$10^4$$
:::

第一次做的时候想的是思路一，该思路整体如下：假设我从第一个加油站出发准备转一圈，一旦我的油箱出现负数，就说明我出发的这个起点不能用，需要一直向后寻找新的出发点，直到某一个加油站时我目前的油箱是正数了，再继续出发。如此往复直到出发的点和当前所在的加油站重合。此时如果我的油箱>=0，那么说明此时的出发点是可以走完全程的；如果此时我的油箱是负数，那么说明无论怎么跑都无法完成一圈。

``` python
# 我的代码
from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        oil_balance = [0] * len(gas)  # 这个可以优化掉的
        for i in range(len(gas)):
            oil_balance[i] = gas[i] - cost[i]
        # 正数意味着可以到达 有多余的油 负数意味着不可以到达
        start_index = 0
        end_index = 0
        balance = oil_balance[end_index]  # 当前油箱
        while (end_index - start_index) != len(gas) - 1:
            if balance < 0:  # 向前起点
                start_index -= 1
                balance += oil_balance[start_index]
            else:  # 向后继续走
                end_index += 1
                balance += oil_balance[end_index]
        if balance >= 0:
            if start_index == 0:
                return 0
            else:
                return len(gas) + start_index
        else:
            return -1
```

第二种解法说实话，感觉和第一种解法有点相似。第一种解法相当于是向前找起点，第二种解法就是向后找起点。同样是对数组进行循环，同样是计算油箱，不同的是解法二在油箱为负数时认为从第一个加油站到当前加油站都不可能是起点，从当前加油站的下一个加油站为起点开始重新计算油箱。同时，解法二还在循环中计算总的路程和油的多少。循环结束时，如果油数量小于路程，就说明无论从哪里开始都不能走完一圈，返回-1；如果油数量大于路程，就返回当前计算的油箱所对应的那个起点。

### 3 LeetCode135 分发糖果

:::info{title="题目"}
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

 

示例 1：
```
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
```
示例 2：
```
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
```

提示：

- n == ratings.length
- 1 <= n <= 2 * $$10^4$$
- 0 <= ratings[i] <= 2 * $$10^4$$
:::

这题体现了贪心的特点：不好想，但是一旦想出来就相当好做。整体的思路就是从前向后和从后向前两次遍历，分别检查当前孩子比左边孩子大和当前孩子比右边孩子大两种情况。它之所以成立，是因为第一次检查时，不仅保留了糖果数量，也保留了当前孩子和左边孩子的大小关系。等到第二遍遍历检查当前孩子和右边孩子的大小关系时，由于是取max，所以再怎么修改当前孩子的糖果数也不会小于之前的糖果数，当前孩子和左边孩子的大小关系也就得到了保留。

``` python
from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        candy_list = [1] * len(ratings)
        for i in range(1, len(ratings)):  # 从前向后 检查当前孩子比左边孩子大的情况
            if ratings[i] > ratings[i - 1]:
                candy_list[i] = candy_list[i - 1] + 1
        for i in range(len(ratings) - 2, -1, -1):  # 从后向前 检查当前孩子比右边孩子大的情况
            if ratings[i] > ratings[i + 1]:
                candy_list[i] = max(candy_list[i], candy_list[i + 1] + 1)
        return sum(candy_list)
```

代码随想录算法训练营第三十四天 | LeetCode1005 K次取反后最大化的数组和、LeetCode134 加油站、LeetCode135 分发糖果

今日任务：

1. LeetCode122 买卖股票的最佳时机 Ⅱ
2. LeetCode55 跳跃游戏
3. LeetCode45 跳跃游戏 Ⅱ



资料来源：

1. [代码随想录 | LeetCode122 买卖股票的最佳时机 Ⅱ](https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html)
2. [代码随想录 | LeetCode55 跳跃游戏](https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html)
3. [代码随想录 | LeetCode45 跳跃游戏 Ⅱ](https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html)

### 1 LeetCode122 买卖股票的最佳时机 Ⅱ

:::info{title="题目"}
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

 

示例 1：
```
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
``` 
示例 2：
```
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
```  
示例 3：
```
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
```

提示：

- 1 <= prices.length <= 3 * 104
- 0 <= prices[i] <= 104
:::

这题要用贪心，我一开始以为贪的是每次买卖的收益最大化，为此要找到每个单调区间的最大值和最小值。看了题解之后才豁然开朗。假设我每天都赚钱（先别管赚的是正是负），每天要赚的就是今天的价格减去昨天的价格。那我贪心一点，只赚正数就好了。

看来贪心确实很奇怪，只要思路想对了就好说，一直想不对就一直想不出来。

``` python
from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1:
            return 0
        result = 0
        for i in range(1, len(prices)):
            if prices[i] - prices[i-1] > 0:
                result += prices[i] - prices[i-1]
        return result
```        

### 2 LeetCode55 跳跃游戏

~~又是一个很巧妙的解法，贪心真的很难想。~~

:::info{title="题目"}
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

 

示例 1：
```
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
```
示例 2：
```
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
```

提示：

- 1 <= nums.length <= 104
- 0 <= nums[i] <= 105
:::

这次贪心贪的是，每次取最大的步数，并且认为在这个步数范围内都是可达的。只要所有的节点的可达范围加在一起能够到达终点，就认为从起点开始能够到达最后一个下标，别管它是怎么到的，反正能到。

``` python
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        max_index_reachable = 0
        for i in range(len(nums)):
            if i + nums[i] > max_index_reachable:
                max_index_reachable = i + nums[i]
            if i >= max_index_reachable:
                return False
            if max_index_reachable >= len(nums) - 1:
                return True
```     

### 3 LeetCode45 跳跃游戏 Ⅱ

:::info{title="题目"}
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i] 
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

 

示例 1:
```
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
```     
示例 2:
```
输入: nums = [2,3,0,1,4]
输出: 2
```

提示:

- 1 <= nums.length <= 104
- 0 <= nums[i] <= 1000
- 题目保证可以到达 nums[n-1]
:::

这是在上一题的基础上修改来的。每一步都争取覆盖最远的地方，这样总体看下来就可以在步数最少的情况下到达终点。

``` python
from typing import List

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        now_index_reachable = 0  # 当前可以到达的最大范围
        next_index_reachable = 0  # 下一步可以到达的最大范围
        step = 0
        for i in range(len(nums)):
            next_index_reachable = max(next_index_reachable, nums[i] + i)  # 每次循环尝试更新下一步可以到达的最大范围
            if i == now_index_reachable:  # 循环到达当前可以到达的最大范围 必须步数+1
                step += 1
                now_index_reachable = next_index_reachable  # 当前可以到达的最大范围更新为下一步的
                if next_index_reachable >= len(nums) - 1:  # 到达终点
                    break
        return step
```