今日任务：

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

代码随想录算法训练营第三十二天 | LeetCode122 买卖股票的最佳时机 Ⅱ、LeetCode55 跳跃游戏、LeetCode45 跳跃游戏 Ⅱ

记录实验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参数。