记录实验1过程及代码。



### 1 HTML 静态页面布局设计

``` html
<!DOCTYPE html>
<html class="light" lang="zh">
    <head>
        <meta charSet="utf-8"/>
    </head>

    <link href="style.css" rel="stylesheet" />

    <body>
        <header>
            <a href="" class="header_href">首页</a>
            <a href="" class="header_href">文章列表</a>
            <a href="" class="header_href">关于我</a>
        </header>

        <main>
            <div id="article_list" class="article_list" style="width: 30%;float: left;border: 1px solid black;">
                <ui>
                    <li class="ariticle_list_single">文章1</li>
                    <li class="ariticle_list_single">文章2</li>
                    <li class="ariticle_list_single">文章3</li>
                    <li class="ariticle_list_single">文章4</li>
                    <li class="ariticle_list_single">文章5</li>
                    <li class="ariticle_list_single">文章6</li>
                    <li class="ariticle_list_single">文章7</li>
                    <li class="ariticle_list_single">文章8</li>
                </ui>
            </div>
            <div id="article" class="article" style="width: 70%;float: right;border: 1px solid black;">
                <ui>
                    <article></article>
                </ui>
            </div>
        </main>
    </body>
```

### 2 CSS 样式表设计

``` css
header {
    background-color: bisque;
}

a.header_href {
    color: cadetblue;
}

a.header_href:hover {
    color: red;
}

a.header_href:active {
    color: aqua;
}

div.article_list {
    list-style: circle;
}

li.ariticle_list_single:hover {
    background-color: aquamarine;
}

li.ariticle_list_single {
    padding-left: 50px;
    padding-right: 50px;
    padding-top: 50px;
    padding-bottom: 50px;
}

div.article {
    font-family: monospace;
    line-height: 2px;
}

h1.article {
    font-size: 32px;
    font-weight: bold;
    color: #333;
    text-align: center;
}

h2.article {
    font-size: 28px;
    font-weight: bold;
    color: #333;
    text-align: center;
}

h3.article {
    font-size: 24px;
    font-weight: bold;
    color: #333;
    text-align: center;
}
```

### 3 JavaScript 动态交互功能实现

``` html
<script>
    const article_list_href = document.getElementsByClassName("ariticle_list_single")
    for (i = 0; i < article_list_href.length; i++) {
        article_list_href[i].addEventListener("click", function() {
            console.log(this.innerHTML)
        })
    }
</script>
```

### 4 Apache Tomcat 服务器安装配置

安装一路点是即可，需要说明的是环境系统变量也需要手动配置。需要配置的一共五项：CATALINA_HOME、CATALINA_BASE、CLASSPATH、JAVA_HOME、Path。

- CATALINA_HOME：指向Tomcat的安装目录
- CATALINA_BASE：指向Tomcat的安装目录
- CLASSPATH：`%CATALINA_HOME%\lib\servlet-api.jar;`
- JAVA_HOME：指向Java的安装目录（这条改成指定JRE_HOME也可以，但是不清楚JRE_HOME应该指向哪里）
- Path：多两项：`%CATALINA_HOME%\bin`、`%CATALINA_HOME%\lib`

整体应该是这个效果：

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

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

如果在CMD/Powershell里输入`startup`能够正常启动Tomcat的话，Tomcat安装就算完成了。

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

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

:::tip{title="提示"}
我安装的是Tomcat10版本，Tomcat9和10版本之间有个坑，参照[博客园 | Tomcat10巨坑，软件不是越新越好。(用到tomcat9及以下就可以)
](https://www.cnblogs.com/djma/p/15684017.html)，这事我也是已经安装完成之后才发现的，懒得改了。如果版本不同，import包的时候要注意。
:::

### 5 IntelliJ IDEA 中集成配置 Tomcat 服务器

:::tip{title="提示"}
idea只有Ultimate版可以有自带的Tomcat配置之类的，Community版没有。Community可以通过Smart Tomcat插件来配置项目。
:::

新建一个Jakarta EE项目，选择Java和对应版本，选择好项目路径，在Templates里选择Web Application，在Application server里选择配置好的Tomcat。

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

如果Tomcat还没有在idea里配置的话，点击NEW -> Tomcat Server来进行配置。Tomcat Home和Tomcat base dictionary都指向Tomcat的安装目录。

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

到了下一步选择依赖的时候，初始情况下有个Servlet依赖就够了，直接CREATE。

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

等它自己解析下载完依赖之后，整个项目应该长这样：

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

直接点击左上角开始尝试运行：

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

看见Service里的`Artifact WebStructure:war exploded: Artifact is deployed successfully`说明部署成功。

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

到这里，idea+Tomcat配置就算完成了。

:::tip{title="提示"}
如果是启用了Hyper-V的系统，启动时有较大概率报1099端口被占用的错误，并且查不到谁占用了这个端口。这是Windows和Hyper-V两边一起背的锅。因为Windows有一个*TCP动态端口范围*，它会随机保留49152到65535下的端口为Hyper-V这样的系统服务使用。按理说这个占不到1099，但是Windows自动更新有时会出错，导致这个范围的起始端口被重置为1024。可以使用`netsh int ipv4 show dynamicport tcp`命令查看被Windows保留的端口。

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

理论上这也是一个“保留接口”，还没确定被Hyper-V使用。可以通过`netsh int ipv4 show excludedportrange protocol=tcp`来查看被使用的端口

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

图里这个端口区间正好包括1099端口，所以我的电脑是没有办法使用1099端口了。

解决方法也很简单，修改运行配置中的JMX Port：

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

还有一种方法是通过`netsh int ipv4 set dynamic tcp start=49152 num=16384`命令修改TCP动态端口范围。我没试，所以这个方法我也不保证会有什么问题。
:::

之前制作的所有前端文件，移动到这个位置。如果有idea自己生成的index.jsp，建议改个名字。

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

关于“设置部署路径为/blog”，在这里设置：

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

### 6 理解和实现 Servlet 接口

导入Gson包，以便生成Json字符串。

``` xml
<dependency>
    <groupId>com.google.code.gson</groupId>
    <artifactId>gson</artifactId>
    <version>2.10.1</version>
</dependency>
```

``` java
// 实验所需的Servlet
package org.example.webstructure;

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 java.io.IOException;
import java.io.PrintWriter;

@WebServlet(value = "/queryArticle", name = "queryArticle") // value标识该Servlet的处理请求的路径 name标识Servlet的名称
public class ArticleServlet extends HttpServlet {
    Gson gson = new Gson();
    
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        resp.setContentType("text/json"); // 设置响应类型
        int articleId = Integer.parseInt(req.getParameter("articleId")); // 获取要请求的文章编号
        PrintWriter out = resp.getWriter(); // 获取输出流
        ArticleEntity article = new ArticleEntity(articleId, Util.getArticle(articleId)); // 获取要请求的文章 封装到Json里
        out.write(gson.toJson(article)); // 写入
        resp.flushBuffer(); // 刷新输出流
    }
}
```

``` java
// 上面的Servlet用到的类
// Util类
package org.example.webstructure;

public class Util {
    static String getArticle(int articleId) {
        return "示例文章，编号" + articleId;
    }
}

// ArticleEntity类
package org.example.webstructure;

public class ArticleEntity {
    private int articleId;
    private String articleComment;

    public ArticleEntity(int articleId, String article) {
        this.articleComment = article;
        this.articleId = articleId;
    }

    public int getArticleId() {
        return articleId;
    }

    public void setArticleId(int articleId) {
        this.articleId = articleId;
    }

    public String getArticleComment() {
        return articleComment;
    }

    public void setArticleComment(String articleComment) {
        this.articleComment = articleComment;
    }
}

```

ApiFox测试效果：

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

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

修改javaScript代码如下：

``` html
<script>
    const article_list_href = document.getElementsByClassName("article_list_single")
    const articleCommentElement = document.getElementById("articleComment")
    for (i = 0; i < article_list_href.length; i++) {
        article_list_href[i].addEventListener("click", function() {
            console.log(this.innerHTML)
            fetch(`http://localhost:8080/WebStructure_war_exploded/queryArticle?articleId=${this.innerHTML.substring(2)}`)
                .then(response => response.json())
                .then(data => {
                    console.log(data)
                    articleCommentElement.innerHTML = data.articleComment
                })
        })
    }
</script>
```
实际效果：

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

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

今日任务：

1. 贪心算法理论基础
2. LeetCode455 分发饼干
3. LeetCode376 摆动序列
4. LeetCode53 最大子序和



资料来源：

1. [代码随想录 | 贪心算法理论基础](https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)
2. [代码随想录 | LeetCode455 分发饼干](https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html)
3. [代码随想录 | LeetCode376 摆动序列](https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html)
4. [代码随想录 | LeetCode53 最大子序和](https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html)

### 1 贪心算法理论基础

贴个目录在这。

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

贪心算法，一句话来说就是，在每个决策点都采取最优的选择，直到整体都成为最优的选择。它一没有套路，二没有题目的明确特征，所以需要对每个题目具体分析。判断一个题目是否需要贪心，只能取决于通过举出局部最优无法到达整体最优的反例，和比赛面试里题目要上动态规划时间不够了，只能贪心，能贪点分是点分。

### 2 LeetCode455 分发饼干

:::info{title="题目"}
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值  g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例  1:

- 输入: g = [1,2,3], s = [1,1]
- 输出: 1 解释:你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输出 1。
示例  2:

- 输入: g = [1,2], s = [1,2,3]
- 输出: 2
- 解释:你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出 2.
提示：

- 1 <= g.length <= 3 * 10^4
- 0 <= s.length <= 3 * 10^4
- 1 <= g[i], s[j] <= 2^31 - 1
:::

很贪心的一道题目。贪就完事了，每个孩子都分配尽量少但又能满足胃口的饼干就行

~~我知道能同时对两个数组进行排序再循环，会快的多，但是我已经累的没脑子了，知道有这个解法就过了）~~

``` python
from typing import List

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        result = 0
        s.sort()
        for i in g:
            for j in range(len(s)):
                if s[j] >= i:
                    result += 1
                    s.pop(j)
                    break
        return result
```       

### 2 LeetCode376 摆动序列

:::info{title="题目"}
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3)  是正负交替出现的。相反, [1,4,7,2,5]  和  [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

- 输入: [1,7,4,9,2,5]
- 输出: 6
- 解释: 整个序列均为摆动序列。
示例 2:

- 输入: [1,17,5,10,13,15,10,5,16,8]
- 输出: 7
- 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:

- 输入: [1,2,3,4,5,6,7,8,9]
- 输出: 2

提示：

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

我以为会很简单来着，结果给我整不会了。

代码随想录算法训练营第三十一天 | 贪心算法理论基础、LeetCode455 分发饼干、LeetCode376 摆动序列、LeetCode53 最大子序和

今日任务：

1. 回溯算法总结
2. LeetCode332 重新安排行程（没写）
3. LeetCode51 N皇后（没写）
4. LeetCode37 解数独（没写）



资料来源：

1. [代码随想录 | 回溯算法总结](https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html)
2. [代码随想录 | LeetCode332 重新安排行程](https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html)
3. [代码随想录 | LeetCode51 N皇后](https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html)
4. [代码随想录 | LeetCode37 解数独](https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html)

### 1 回溯算法总结

回溯算法最重要的就是**如何将要解决的问题映射到那颗具体的回溯的树上去**，比如说今天的332和37，一旦能想明白这一点，剩下的就不难了。

**回溯算法模板**：

```
def __init__():
    self.path = []
    self.result = []
    self.题目给定资料...
    
def 入口函数():
    self.题目给定资料赋值
    back_tracking()
    return self.result
    
def back_tracking():
    if 终止条件:
        self.result.append(self.path.copy())
    return
    
    for 单层递归循环
        if 符合条件:
            self.path.append()
            self.back_tracking()  向下递归
            self.path.pop()
```

**回溯算法查重问题**：

根据这几天的题来说，查重有两个问题：**在哪里查？具体查谁？**

1. 在哪里查？
    
    - 树枝查重：生效范围是所有的递归函数，需要在类变量里记录重复元素/下标
    - 树层查重：生效范围是同一层的所有递归函数，需要在上一层的递归函数中记录重复元素/下标或者对题目给定元素进行排序从而在循环中检查前后元素来查重
    - 递归查重：生效范围是单个递归函数内，需要在单个递归函数中记录重复元素/下标

    递归查重和树层查重本身是有相似性的，递归查重可以说就是树层查重另一个版本。但是为了分的清楚点还是分开讨论比较好。
    
3. 具体查谁？
    - 查元素是否重复：要记录的是元素本身，除了通过哈希数组num_used来记录该元素的值是否被用过以外，也可以对题目给定元素进行排序从而在循环中检查前后元素来查重
    - 查下标是否重复：要记录的是元素的位置，只能通过哈希数组index_used来记录该元素是否被用过

**回溯算法参数加不加start_index？**

分情况讨论。如果下一层递归的循环需要从上一层指定位置开始，就需要start_index参数；如果下一层递归的循环可以从头开始/开始位置不和上一层递归有所关联，那么就不需要start_index参数。

代码随想录算法训练营第三十天 | 回溯算法总结

代码随想录算法训练营第二十九天 | LeetCode491 递增子序列、LeetCode46 全排列、LeetCode47 全排列Ⅱ

今日任务：

1. LeetCode93 复原IP地址
2. LeetCode78 子集
3. LeetCode90 子集Ⅱ



资料来源：

1. [代码随想录 | LeetCode93 复原IP地址](https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html)
2. [代码随想录 | LeetCode78 子集](https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html)
3. [代码随想录 | LeetCode90 子集Ⅱ](https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html)

### 1 LeetCode93 复原IP地址

:::info{title="题目"}
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

 

示例 1：
```
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
```
示例 2：
```
输入：s = "0000"
输出：["0.0.0.0"]
```
示例 3：
```
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
```

提示：

- 1 <= s.length <= 20
- s 仅由数字组成
:::

一个比较另类的切割问题，我这个写法属于是有点绕远路，思路走的还是子集问题的思路，其实没有必要将选取的字符还取出来存着，用一个index表示切割的位置就好了。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.s = ""
        self.path = []
        self.result: List[str] = []

    def restoreIpAddresses(self, s: str) -> List[str]:
        self.s = s
        self.back_tracking(0, 1)
        for i in range(len(self.result)):
            self.result[i] = self.result[i][:-1]
        return self.result

    def back_tracking(self, start_index: int, recursion_number: int):
        # recursion_number的作用是记录递归层数 也是记录目前回溯出来的IP地址的段数 递归层数 + 1 = IP地址的段数
        
        # 终止条件
        result = "".join(self.path)
        if len(result) == len(self.s) + 4 and recursion_number == 5:
            self.result.append(result)

        # 剪枝
        if recursion_number > 5:
            return

        # 单层递归逻辑
        part_of_ip = ""
        for i in range(start_index, len(self.s)):
            part_of_ip += self.s[i]
            if (1 <= int(part_of_ip) <= 255 and part_of_ip[0] != "0") or part_of_ip == "0":  # 检查选取的数字是否符合标准
                part_of_ip += "."
                self.path.append(part_of_ip)
                self.back_tracking(i + 1, recursion_number + 1)  # 递归层数 + 1 IP地址的段数 + 1
                self.path.pop()
                part_of_ip = part_of_ip[:-1]
```       

### 2 LeetCode78 子集

:::info{title="题目"}
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集
（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
```
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```
示例 2：
```
输入：nums = [0]
输出：[[],[0]]
```

提示：

- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同
:::

非常标准的回溯写法，只是注意子集问题要找树的所有节点，所以每次进递归都要添加元素，不设添加标准。终止条件还是要有的（就本题而言没有其实也行）。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.nums = []
        self.path = []
        self.result = []

    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.back_tracking(0)
        return self.result

    def back_tracking(self, start_index: int):
        self.result.append(self.path.copy())
        if len(self.path) == len(self.nums):  # 这个终止条件不必要 反正真的到终止的时候下面的循环也没法开始
            return

        for i in range(start_index, len(self.nums)):
            self.path.append(self.nums[i])
            self.back_tracking(i + 1)
            self.path.pop()
``` 

### 3 LeetCode90 子集Ⅱ

:::info{title="题目"}
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 
子集
（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
```
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
```
示例 2：
```
输入：nums = [0]
输出：[[],[0]]
```

提示：

- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
:::

这是子集问题+树层查重，使用的方法就是哈希数组num_used。

``` python
from typing import List

class Solution:
    def __init__(self):
        self.path = []
        self.result = []
        self.nums = []

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.nums = nums
        self.back_tracking(0)
        return self.result

    def back_tracking(self, start_index: int):
        self.result.append(self.path.copy())
        if len(self.path) == len(self.nums):
            return

        used_num_hash = [0] * 21
        for i in range(start_index, len(self.nums)):
            if used_num_hash[self.nums[i]] == 0:  # 检查是否被使用
                self.path.append(self.nums[i])
                used_num_hash[self.nums[i]] = 1
                self.back_tracking(i + 1)
                self.path.pop()
```