今日任务：

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

代码随想录算法训练营第三十二天 | 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
:::

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