# 复现论文





![在这里插入图片描述](/static/img/images/03294.png)

# 什么是柔性作业车间调度问题？


柔性作业车间调度问题（Flexible Job Shop Scheduling Problem，简称FJSP）是传统作业车间调度问题的一种扩展。在传统的作业车间调度问题中，每个工件的每个工序只能在指定的一台机器上加工。而在柔性作业车间调度问题中，突破了这种资源唯一性的限制，允许每个工件的每个工序在多台不同的机器上加工，且这些机器上的加工时间可能不同。

这种灵活性使得作业车间调度问题更加贴合实际生产情况，因为实际生产中，同一道工序可能由不同的机器完成，不同的机器完成同一工序的时间和成本也可能有所差异。因此，FJSP 考虑了更多的生产实际，其目标通常是最小化最大完工时间（makespan），即所有工件中最后一个完工的工件的完成时间。

柔性作业车间调度问题的复杂性较高，因为它不仅要考虑工序的加工顺序，还要考虑不同机器上的加工时间差异，以及可能的机器选择问题。这些问题的组合导致了庞大的搜索空间，使得找到最优解或近似最优解成为一个具有挑战性的优化问题。

在数据集中，有10个待加工的工件，每一行就是一个工件。

下图是数据集截图，表示是，工件0一共有6个工序。后面数字是21534，表示第一道工序可选机器有2个，选择机器1花费时间为5可以完成这个工序的加工，选择机器3花费时间为4可以完成这个工序的加工。后面3533521是一组，表示第二个工序可选机器有3个，选择机器1花费时间为5可以完成这个工序的加工，选择机器3花费时间为4可以完成这个工序的加工，选择机器3花费时间为4可以完成这个工序的加工

![在这里插入图片描述](/static/img/images/03295.png)

全部数据集如下：

```bash
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34
6,2,1,5,3,4,3,5,3,3,5,2,1,2,3,4,6,2,3,6,5,2,6.0,1.0,1.0,1.0,3.0,1.0,3.0,6.0,6.0,3.0,6.0,4.0,3.0
5,1,2,6,1,3,1,1,1,2,2,2,6,4,6,3,6,5,2,6,1,1,,,,,,,,,,,,,
5,1,2,6,2,3,4,6,2,3,6,5,2,6,1,1,3,3,4,2,6,6,6.0,2.0,1.0,1.0,5.0,5.0,,,,,,,
5,3,6,5,2,6,1,1,1,2,6,1,3,1,3,5,3,3,5,2,1,2,3.0,4.0,6.0,2.0,,,,,,,,,
6,3,5,3,3,5,2,1,3,6,5,2,6,1,1,1,2,6,2,1,5,3,4.0,2.0,2.0,6.0,4.0,6.0,3.0,3.0,4.0,2.0,6.0,6.0,6.0
6,2,3,4,6,2,1,1,2,3,3,4,2,6,6,6,1,2,6,3,6,5,2.0,6.0,1.0,1.0,2.0,1.0,3.0,4.0,2.0,,,,
5,1,6,1,2,1,3,4,2,3,3,4,2,6,6,6,3,2,6,5,1,1,6.0,1.0,3.0,1.0,,,,,,,,,
5,2,3,4,6,2,3,3,4,2,6,6,6,3,6,5,2,6,1,1,1,2,6.0,2.0,2.0,6.0,4.0,6.0,,,,,,,
6,1,6,1,2,1,1,5,5,3,6,6,3,6,4,3,1,1,2,3,3,4,2.0,6.0,6.0,6.0,2.0,2.0,6.0,4.0,6.0,,,,
6,2,3,4,6,2,3,3,4,2,6,6,6,3,5,3,3,5,2,1,1,6,1.0,2.0,2.0,6.0,4.0,6.0,2.0,1.0,3.0,4.0,2.0,,
```


最终目标是要求加工完所有工件所需要的最小时间：


![在这里插入图片描述](/static/img/images/03296.png)


# 数据处理

10种类型的工件要加工，一共有6台机器：

```bash
da = data_deal(10, 6)
```

读取数据，解析数据：

```bash
Tmachine, Tmachinetime, tdx, work, tom, machines = da.cacu() 
```

Tmachine 一行就是一个工件可以选择的机器。不足长度的补充0。

![在这里插入图片描述](/static/img/images/03297.png)

Tmachinetime和Tmachine 同样形状，表示每个机器对应需要多少时间：

![在这里插入图片描述](/static/img/images/03298.png)

tdx表示每个工序可选的机器数量，比如第一个零件的第一个工序可以选择2台机器加工。而且tdx[0]的长度表示了零件0需要有6个工序才能加工完成。

![在这里插入图片描述](/static/img/images/03299.png)

# ABC算法

ABC（Artificial Bee Colony）算法是一种启发式优化算法，模拟了蜜蜂在寻找食物过程中的行为。这个算法由三种类型的蜜蜂组成：雇佣蜂、观察蜂和侦查蜂。

1. **雇佣蜂**：雇佣蜂负责在已知的蜜源周围搜索，它们相当于解决问题的候选解。每个蜜源都对应一个雇佣蜂，它们具有记忆功能，能够存储搜索到的蜜源信息，并根据蜜源的好坏与观察蜂分享信息。

2. **观察蜂**：观察蜂接收雇佣蜂分享的蜜源信息，并选择其中满意的蜜源进行跟随。观察蜂的数量与雇佣蜂相等。

3. **侦查蜂**：侦查蜂负责搜索新的蜜源位置，以保持算法的多样性和全局搜索能力。

这三种蜜蜂之间可以相互转换，以达到更好的搜索效果。ABC 算法通过模拟蜜蜂群体的这种协作和信息共享机制，实现了对优化问题的求解。

![在这里插入图片描述](/static/img/images/03300.png)




## 编码解码

ABC算法是一种启发式优化算法，最初用于处理连续解空间的问题。然而，在柔性作业车间调度这种离散问题中，标准的ABC算法并不直接适用。因此，我们需要对问题进行适当的编码和解码。

针对柔性作业车间调度问题，我们采用双层编码的形式：

1. **工序串编码**：这一层编码用于确定工序的加工顺序。比如，考虑一个工序串［3 1 2 1 2 2］，它表示了不同工件的工序顺序。在这个串中，数字代表工件号，数字出现的次数表示该工件有多少个工序。比如，在串中的第一个数字3表示工件3的第一个工序，第一个数字1表示工件1的第一个工序。因此，工序串的加工顺序为：O31 → O11 → O21 → O12 → O22 → O23。

2. **机器串编码**：这一层编码表示每个工序选择的机器。比如，机器串编码［2 2 1 1 3 3］表示了每个工序选择的机器编号。在这个串中，数字代表机器编号，按工件序号和工序顺序排列。比如，在串中的第一个位置的数字2表示工序O11选择了机器M2进行加工，第五个位置的数字1表示工序O23选择了机器M1进行加工。

通过这样的双层编码，我们可以将柔性作业车间调度问题转化为一个适合ABC算法处理的问题。

在代码种，对应为：

```python
class FJSP():
    def __init__(self, job_num, machine_num, P_GLR, parm_data, P_MSR):
        self.job_num = job_num  # 工件数
        self.machine_num = machine_num  # 机器数
        self.p1 = P_GLR[0]  # 全局选择的概率
        self.p2 = P_GLR[1]  # 局部选择的概率
        self.Tmachine, self.Tmachinetime, self.tdx, self.work, self.tom = parm_data[0], parm_data[1], parm_data[2], \
            parm_data[3], parm_data[4]
        self.machines = parm_data[5]
        self.p3 = P_MSR[0]  # 剩余负荷最大规则的概率
        self.p4 = P_MSR[1]  # 加工时间最短的概率
    def creat_Machine(self):
        job = np.copy(self.work)
        Ma_time = np.zeros((self.job_num,))
        machine, machine_time = [], []  # 初始化矩阵
        a_global = np.zeros((1, self.machine_num))
        r = np.random.rand()
        for i in range(self.job_num):
            a_part = np.zeros((1, self.machine_num))
            time = 0
            for j in range(self.machines[i]):
                highs = self.tom[i][j]
                lows = self.tom[i][j] - self.tdx[i][j]
                n_machine = self.Tmachine[i, lows:highs].tolist()
                n_time = self.Tmachinetime[i, lows:highs].tolist()
                index_select = []
                if r < self.p1 or r > 1 - self.p2:
                    for k in range(len(n_machine)):
                        m = int(n_machine[k]) - 1
                        index_select.append(m)
                        t = n_time[k]
                        a_global[0, m] += t  # 全局负荷计算
                        a_part[0, m] += t  # 局部负荷计算
                    if r < self.p1:  # 全局选择
                        select = a_global[:, index_select]
                        idx_select = np.argmin(select[0])
                    else:  # 局部选择
                        select = a_part[:, index_select]
                        idx_select = np.argmin(select[0])
                    m_select = n_machine[idx_select]
                    t_index = n_machine.index(m_select)
                    machine.append(m_select)
                    machine_time.append(n_time[t_index])
                    time += n_time[t_index]
                else:  # 否则随机挑选机器
                    index = np.random.randint(0, len(n_time), 1)
                    machine.append(n_machine[index[0]])
                    machine_time.append(n_time[index[0]])
                    time += n_time[index[0]]
            Ma_time[i] = time
        return machine, machine_time, Ma_time
    def creat_job(self):
        count = np.zeros((1, self.job_num), dtype=np.int_)
        machine, machine_time, Ma_time = self.creat_Machine()
        time_last = Ma_time.copy()
        rember = [sum(self.machines[:i]) for i in range(len(self.machines))]
        job = []
        for i in range(len(self.work)):
            r = np.random.rand()
            a = np.argwhere(time_last > 0)  # 挑选剩余工件加工时间大于0的索引
            if r < self.p3 + self.p4:  # 剩余负荷最大规则和加工时间最短优先规则
                b = time_last[a].reshape(a.shape[0], ).tolist()  # 按照索引取出具体工件的加工时间
                if r < self.p3:  # 剩余负荷最大规则
                    a_index = b.index(max(b))
                    jobb = int(a[a_index, 0])
                    job.append(jobb)
                else:  # 加工时间最短优先规则
                    a_index = b.index(min(b))
                    jobb = int(a[a_index, 0])
                    job.append(jobb)
            else:  # 随机选择规则
                index = np.random.randint(0, a.shape[0], 1)
                jobb = int(a[index, 0])
                job.append(jobb)
            loc = count[0, jobb]
            loc1 = rember[jobb] + loc
            time = machine_time[loc1]
            time_last[jobb] -= time  # 更新剩余工件加工时间
            count[0, jobb] += 1
        return job, machine, machine_time
```

## 种群初始化

种群初始化对于算法的性能至关重要。如果完全随机生成初始种群，那么初始解的质量可能参差不齐，这会影响算法寻找最优解的速度，可能需要增加迭代次数和种群大小来获得更好的结果，这会增加优化时间。为了解决这个问题，我们采用了随机选择和按规则选择相结合的方法来初始化种群。

在机器串编码中，我们采用了三种初始化规则：全局选择（Global Selection，GS）、局部选择（Local Selection，LS）和随机选择（Random Selection，RS）。GS和LS可以平衡每台机器的负载，提高机器利用率，从而在一定程度上减小初始解的最大完工时间。而具有强随机性的RS可以保证初始解的多样性，能够取得解空间中的任意解。

在工序串编码中，我们采用了三种初始化规则：剩余负荷最大规则（Maximum Residual Load，MRL）、加工时间最短优先规则（Shortest Process Time，SPT）和随机选择（Random Selection，RS）。MRL优先处理剩余加工时间最长的工件，SPT优先处理剩余加工时间最短的工件，而RS则随机选择工序进行排序。

为了更好地平衡这些规则的应用，我们对机器串和工序串生成规则进行了概率分配。具体来说，机器串生成规则GS/LS/RS的选择概率分别为30%、30%和40%，而工序串的生成规则MRL/SPT/RS的选择概率也分别为30%、30%和40%。

这样的概率分配旨在保证算法能够在初始阶段充分利用规则性和随机性，从而获得多样性的初始种群，有利于提高算法的搜索效率和收敛性。

## 雇佣蜂操作

针对柔性作业车间调度问题，我们对传统的雇佣蜂操作进行了改进，采用了两种交叉方法：IPOX交叉和多点交叉。

### IPOX交叉

在IPOX交叉中，我们首先从种群中选择一条工序串作为父代X1，并生成一个0到1之间的随机数。如果随机数小于0.5，则选择全局最优解作为X2；否则，从种群中选择另一条工序串作为X2（但不同于X1）。接下来，我们将工件分为两个互补的工件集R1和R2。然后，我们将X1中包含在R1工件集中的工序号按照在X1中的位置复制到子代C1中，并将X2中包含在R2工件集中的工序按照原顺序插入到C1的空缺处。类似地，我们将X2中包含在R2工件集中的工序号复制到子代C2中，并将X1中包含在R1工件集中的工序按照原顺序插入到C2的空缺处。最后，我们计算子代C1和C2的适应度值，选择适应度值较大的子代作为交叉后的子代，并检查是否需要替换父代X1的适应度值。

### 多点交叉

多点交叉作用于机器串的交叉操作。首先，我们选择与父代X1工序串对应的机器串作为机器串父代P1，并选择与父代X2工序串对应的机器串作为机器串父代P2。然后，我们随机生成一个由0和1组成的与机器串长度相等的二进制串。接着，我们将P1中与二进制串中与1位置相同的机器号复制到子代S1的相同位置，并将P2中与二进制串中与0位置相同的机器号复制到S1的相同位置。然后，我们将P2中与二进制串中与1位置相同的机器号复制到子代S2的相同位置，并将P1中与二进制串中与0位置相同的机器号复制到S2的相同位置。最后，我们计算子代S1和S2的适应度值，选择适应度值较大的作为机器串多点交叉后的子代，并检查是否需要替换父代P1的适应度值。

这两种交叉方法不会产生非法解，同时能够将父代个体中的优良基因传递到下一代，从而帮助改进解的质量和收敛速度。


## 观察蜂操作

1. **蜜蜂觅食行为**：

   - 蜜蜂使用轮盘赌选择蜜源的位置，选择概率与蜜源的适应度值成正比。适应度值高的蜜源被选中的概率更大。

   - 选择概率的计算使用公式(10)，其中fit_w是第w个解的适应度值，D是蜜源的数量，即种群数量的一半。

   - 蜜源的适应度值按照公式(12)计算，其中obj_w是蜜源w的目标值。

2. **工序串优化**：

   - 采用变换步长策略对选择的蜜源位置附近进行搜索。大步长交换可行解中多对工序的顺序，增强全局搜索能力，避免陷入局部最优；小步长交换可行解中一对工序的顺序，适合在当前解空间进行更深一步的搜索。

   - 为了结合大步长和小步长的优势，设定了一个阈值，当搜索次数小于阈值时进行小步长搜索，反之进行大步长搜索，并在切换时将搜索次数清零。

   - 在计算适应度值时，采用贪婪策略选择适应度高的个体，以保留精英个体。

   - 对工序串进行插入变异时，从工序串中选择任意一道工序插入到工序串的任意位置，然后按照原有顺序排序，并计算适应度值。同样地，对机器串进行变异操作时，随机选择一道工序，在其可选机器集中随机选择一台机器进行变异，并计算适应度值。最后，采用贪婪策略选择适应度高的染色体保留到下一代种群中。


## 侦察蜂操作


在标准的ABC算法中，如果雇佣蜂在同一个蜜源上进行了limit次（即达到最大搜索次数）而没有改进，那么它就会转变为侦查蜂。在传统ABC算法中，每次只有一只雇佣蜂会被转变为侦查蜂，而侦查蜂生成的随机解对种群的改进影响较小，不利于算法跳出局部最优解。

因此，在这里提出了一种改进的方法：如果有Y个蜜源经过limit次搜索没有改进，那么就采用种群初始化方法（来自文中第2.2节）生成Y个新的蜜源。通过增加侦查蜂的数量，保持种群的多样性，这有助于提高算法的全局搜索能力。

具体来说，当Y个蜜源达到搜索次数上限时，会生成Y个新的蜜源，以增加算法的搜索空间，从而提高发现更好解的可能性，增强算法的全局搜索能力。

## 算法流程

1. 建立柔性作业车间调度模型。

2. 确定调度的约束条件。

3. 初始化种群以及设置参数。

4. 计算适应度值，雇佣蜂进行 IPOX 交叉和多点交叉操作。

5. 计算各蜜源的适应度值，并且计算观察蜂选择跟随各雇佣蜂的概率。

6. 观察蜂采用变步长搜索策略，并且进行变异操作。

7. 判断蜜源是否达到最大搜索次数，若满足条件则雇佣蜂转换为侦查蜂，搜索新的蜜源，否则进入步骤 8。

8. 判断算法是否达到最大迭代次数，如果是则算法结束；如果未达到最大迭代次数，则跳转到步骤 4。


![在这里插入图片描述](/static/img/images/03301.png)


# 结果

计算这个问题，设置了50轮的答案搜索，完工时间由大变小，体现出算法寻找最优解的变化，整体是收敛的。

![在这里插入图片描述](/static/img/images/03302.png)

从甘特图种可以看出6台机器如何分配才能达到最优最短的完工时间，比如可以看到机器M1的加工顺序是零件4、零件4、等等。总的完工时间花费是46。

![在这里插入图片描述](/static/img/images/03303.png)

# 程序截图

![在这里插入图片描述](/static/img/images/03304.png)

用python运行main.py后即可得到甘特图和结果图：

![在这里插入图片描述](/static/img/images/03305.png)

# 问询、帮助

```csharp
https://docs.qq.com/sheet/DUEdqZ2lmbmR6UVdU?tab=BB08J2
```

【算法】人工蜂群算法，解决柔性车间调度问题

the following signatures couldn't be verified because the public key is not available: NO_PUBKEY 3B4FE6ACC0B21F32





This error occurs when trying to install or update a package in Ubuntu or Debian that requires an authentication key which is not present on your system. To resolve the issue, you can import the missing public key using the following command:
```python
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 3B4FE6ACC0B21F32
```

This will fetch and add the missing key to your system's trusted keys list. After that, you should be able to install or update the package without any further issues.

following signatures couldn‘t be verified because the public key is not available: NO_PUBKEY

# 介绍





贪心算法是一种基于贪心思想的算法，它每次选择当前最优的解决方案，从而得到全局最优解。具体来说，贪心算法在每一步都做出局部最优选择，希望通过这种方式最终达到全局最优解。贪心算法通常适用于问题具有最优子结构性质和无后效性的情况。尽管贪心算法并不总是能够得到最优解，但它通常具有高效、简单等优点，并且在许多实际问题中得到了广泛应用。

一般来说，可以从以下几个方面考虑如何区别题目要使用贪心算法还是动态规划算法：

1、问题的性质：贪心算法适用于具有最优子结构性质和无后效性的问题，而动态规划算法则适用于具有重叠子问题和最优子结构性质的问题。

2、对时间复杂度的要求：贪心算法通常比动态规划算法更加高效，但并不总能得到最优解。如果对时间复杂度有较高的要求，可以首先考虑贪心算法；否则可以使用动态规划算法。

3、解决问题的方式：贪心算法通常是从局部最优解推导出全局最优解，即每次都选择当前最优解，并期望通过这种方式得到最终的最优解。而动态规划算法则是通过将问题分解成多个子问题，并保存已经求解过的子问题的结果，然后再利用这些子问题的结果求解更大的子问题，最终得到全局最优解。

4、是否存在贪心选择性质或者无后效性质：关键在于是否能够证明问题具有贪心选择性质或者无后效性质，如果问题确实具有这些性质，那么使用贪心算法也许是一个较好的选择。





![在这里插入图片描述](/static/img/images/04626.png)



# 分配饼干

[https://leetcode.cn/problems/assign-cookies/description/](https://leetcode.cn/problems/assign-cookies/description/)

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

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

```python
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i, j = 0, 0
        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                i += 1
            j += 1
        return i
```

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

[https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/](https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/)

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

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

```python
class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort()
        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
            else:
                break
        nums.sort()
        if k % 2 == 1:
            nums[0] = -nums[0]
        return sum(nums)
```

# 柠檬水找零

[https://leetcode.cn/problems/lemonade-change/](https://leetcode.cn/problems/lemonade-change/)

使用贪心算法解决该问题，具体步骤如下：

1、初始化变量 fives, tens 为 0，分别表示手中拥有的 5 元和 10 元数量。

2、对于每个顾客支付的钞票金额 bill，进行如下操作：

- 如果 bill 为 5 元，则不需要找零，直接将手中的 5 元数量加 1。

- 如果 bill 为 10 元，则需要找零 5 元，此时需要检查手中是否有足够的 5 元可找零，如果没有则返回 False；否则将手中的 10 元数量加 1，将手中的 5 元数量减 1。

- 如果 bill 为 20 元，则需要找零 15 元，优先使用一张 10 元和一张 5 元找零，如果手中没有足够的 10 元和 5 元，则尝试使用三张 5 元找零，如果还是无法找零，则返回 False。

 

3、如果成功为所有顾客找到了零钱，则返回 True。

```python
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        fives = tens = 0
        for bill in bills:
            if bill == 5:
                fives += 1
            elif bill == 10:
                if not fives:
                    return False
                fives -= 1
                tens += 1
            else:
                if tens and fives:
                    tens -= 1
                    fives -= 1
                elif fives >= 3:
                    fives -= 3
                else:
                    return False
        return True
```



# 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。


```python
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)
        up = down = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                up = down + 1
            elif nums[i] < nums[i-1]:
                down = up + 1
        return max(up, down)
```

# 单调递增的数字

[https://leetcode.cn/problems/monotone-increasing-digits/](https://leetcode.cn/problems/monotone-increasing-digits/)

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

```python
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = str(n)
        i = 1
        while i < len(s) and s[i - 1] <= s[i]:
            i += 1
        if i < len(s):
            while i > 0 and s[i - 1] > s[i]:
                s = s[:i - 1] + str(int(s[i - 1]) - 1) + '9' * (len(s) - i)
                i -= 1
        return int(s)
```

# 买卖股票的最佳时机 II

[https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/)

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

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

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

 

在贪心策略中，前一天价格低就买入，然后在今天卖出。
```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        profit = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                profit+=(prices[i]-prices[i-1])
        return profit
```

# 买卖股票的最佳时机含手续费

[https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/)

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

```python
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        if not prices:
            return 0
        profit = 0
        buy_price = prices[0]
        for i in range(1, len(prices)):
            # 如果当前价格比之前买入价加手续费高，就可以卖出股票并获得利润
            if prices[i] >= buy_price + fee:
                profit += prices[i] - (buy_price + fee)
                buy_price = prices[i] - fee  # 更新买入价为当前价减去手续费
            # 如果当前价格比之前买入价便宜，就考虑更新买入价
            elif prices[i] < buy_price:
                buy_price = prices[i]
        return profit
```

# 分发糖果

[https://leetcode.cn/problems/candy/description/](https://leetcode.cn/problems/candy/description/)

```python
class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int 贪心策略，两遍遍历。第一遍右边元素比左遍元素大，则糖果为左边糖果加1.第2遍左边元素比右边元素大，则糖果为右边加1或者或者为本身糖果数量。
        """
        if len(ratings)<2:
            return len(ratings)
        assign=[1 for _ in ratings]
        for i in range(1,len(ratings),1):
            if ratings[i]>ratings[i-1]:
                assign[i]=assign[i-1]+1
        for i in range(len(ratings)-1,0,-1):
            if ratings[i-1]>ratings[i]:
                assign[i-1]=max(assign[i-1],assign[i]+1)
        return sum(assign)
```

# 根据身高重建队列

[https://leetcode.cn/problems/queue-reconstruction-by-height/description/](https://leetcode.cn/problems/queue-reconstruction-by-height/description/)

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

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

 输入：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]] 是重新构造后的队列。

```python
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 按照身高从高到低排列，如果身高相同则按照前面大于等于身高的人数从小到大排序
        people.sort(key=lambda x: (-x[0], x[1]))
        queue = []
        # 将每个人插入到队列中，位置由前面大于等于身高的人数决定
        for p in people:
            queue.insert(p[1], p)
        return queue
```

# 跳跃游戏

[https://leetcode.cn/problems/jump-game/description/](https://leetcode.cn/problems/jump-game/description/)

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

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

# 跳跃游戏 II

[https://leetcode.cn/problems/jump-game-ii/description/](https://leetcode.cn/problems/jump-game-ii/description/)

给定一个长度为 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]。

 
```python
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        max_pos, step, end = 0, 0, 0
        for i in range(n-1):
            max_pos = max(max_pos, i + nums[i])
            if i == end:
                end = max_pos
                step += 1
        return step
```

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

[https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/)

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

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

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
```python
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        # 按照气球结束坐标从小到大排序
        points.sort(key=lambda x:x[1])
        # 初始化箭的射出位置为第一个气球的结束坐标
        arrow_pos = points[0][1]
        count = 1
        for i in range(1, len(points)):
            # 如果下一个气球的开始坐标大于当前箭的射出位置，则需要再发射一支箭
            if points[i][0] > arrow_pos:
                arrow_pos = points[i][1]
                count += 1
        return count
```

# 无重叠区间

[https://leetcode.cn/problems/non-overlapping-intervals/submissions/417134877/](https://leetcode.cn/problems/non-overlapping-intervals/submissions/417134877/)

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

 

具体实现过程如下：

首先判断输入是否为空，如果为空则直接返回0。

对输入列表按照每个区间的结束位置进行排序，即按照x[1]排序。

初始化变量end为第一个区间的结束位置，count为1，表示当前至少需要保留一个区间。

遍历排序后的区间列表，若当前区间的开始位置大于等于end，则说明该区间与前一个区间不重叠，将end更新为当前区间的结束位置，同时count加1。

若当前区间的开始位置小于end，则说明该区间与前一个区间重叠，则需要移除其中一个区间。因为已经将区间按照结束位置排序，所以优先保留结束位置更早的区间，因此将end更新为前一个区间的结束位置和当前区间的结束位置中较小的那个。

最终返回需要移除的区间数量，即总区间数减去保留的区间数。
```python
class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[1])
        end = intervals[0][1]
        count = 1
        for i in range(1, len(intervals)):
            if intervals[i][0] >= end:
                end = intervals[i][1]
                count += 1
            else:
                end = min(end, intervals[i][1])
        return len(intervals) - count
```


# 划分字母区间

[https://leetcode.cn/problems/partition-labels/description/](https://leetcode.cn/problems/partition-labels/description/)

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

 

 遍历字符串，对于每个字符记录它最后一次出现的位置；

维护一个起始位置和结束位置，表示当前片段的范围；

如果当前位置等于结束位置，说明当前位置是一个片段的结束位置，将该片段长度添加到结果数组中，并将起始位置设为结束位置的下一个位置；

最终返回结果数组。

```python
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last = {c:i for i, c in enumerate(s)}
        start = end = 0
        res = []
        for i, c in enumerate(s):
            end = max(end, last[c])
            if i == end:
                res.append(end - start + 1)
                start = end + 1
        return res
```

【算法题目】【Python】一文刷遍贪心算法题目

难度可以控制，且解法唯一，时间复杂度看运气。







首先，我们定义了一个 SudokuGenerator 类。然后，我们定义了 generate 方法来生成数独游戏。该方法生成了一个 9 × 9 的矩阵，初始值为 '.'。接着，使用 solveSudoku 方法来解决数独游戏，并将解决后的结果存放在生成的矩阵中。

在求解数独游戏时，我们使用深度优先搜索算法来实现。对于每个单元格，首先检查它是否有预设值（即是否为 '.'），如果有，直接跳过。如果没有，我们随机生成1~9的数字，并检查该数字是否符合数独规则，如果不符合规则，就换一个数字再次尝试，直到找到符合规则的数字。将符合规则的数字填入该单元格，并继续向后搜索，直到搜索完成整个数独游戏。

然后，我们定义了 removeNumbers 方法来删除数独游戏，使难度符合所选根据。在此方法中，我们使用深度优先搜索算法来逐步删除数独游戏中的数字。我们找到所有预设数字的单元格，并随机打乱它们的顺序。然后尝试删除单元格中的数字，并确保解法唯一，如果解法唯一，继续删除数字，否则回退上一个状态。

最后，我们定义了 isUnique 和 solve 方法来解决数独游戏。isUnique 方法用于确定给定的游戏是否具有唯一解。该方法使用深度优先搜索算法，在填写数字的过程中判断是否出现多个解决方案。 solve 方法解决数独游戏，将字符串表示为数独板，并返回解决结果的一个布尔值。

```python
import random
class SudokuGenerator:
    def __init__(self, difficulty):
        # 限制在30和60之间
        if difficulty < 30:
            self.difficulty = 30
        elif difficulty > 60:
            self.difficulty = 60
        else:
            self.difficulty = difficulty
    def generate(self):
        board = [['.' for _ in range(9)] for _ in range(9)]
        self.solveSudoku(board)
        self.removeNumbers(board, self.difficulty)
        return board
    def solveSudoku(self, board):
        def dfs(board, row, col):
            if col == 9:
                return dfs(board, row + 1, 0)
            if row == 9:
                return True
            if board[row][col] != '.':
                return dfs(board, row, col + 1)
            nums = list(range(1, 10))
            random.shuffle(nums)
            for i in nums:
                if not isValid(board, row, col, str(i)):
                    continue
                board[row][col] = str(i)
                if dfs(board, row, col + 1):
                    return True
                board[row][col] = '.'
            return False
        def isValid(board, row, col, c):
            for i in range(9):
                if board[i][col] == c:
                    return False
                if board[row][i] == c:
                    return False
                if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == c:
                    return False
            return True
        dfs(board, 0, 0)
    def removeNumbers(self, board, difficulty):
        def dfs(board, num):
            if num == 0:
                return True
            lst = [(i, j) for i in range(9) for j in range(9) if board[i][j] != '.']
            lst = sorted(lst, key=lambda x: random.random())
            for i, j in lst:
                c = board[i][j]
                board[i][j] = '.'
                if not self.isUnique(board):
                    board[i][j] = c
                elif dfs(board, num - 1):
                    return True
                else:
                    board[i][j] = c
            return False
        dfs(board, difficulty)
    def isUnique(self, board):
        s = ''.join([''.join(row) for row in board])
        solver = SudokuSolver()
        return solver.solve(s)
class SudokuSolver:
    def solve(self, s):
        board = [[s[i * 9 + j] for j in range(9)] for i in range(9)]
        return self.solveSudoku(board)
    def solveSudoku(self, board):
        def dfs(board, row, col):
            if col == 9:
                return dfs(board, row + 1, 0)
            if row == 9:
                return True
            if board[row][col] != '.':
                return dfs(board, row, col + 1)
            for i in range(1, 10):
                if not isValid(board, row, col, str(i)):
                    continue
                board[row][col] = str(i)
                if dfs(board, row, col + 1):
                    return True
                board[row][col] = '.'
            return False
        def isValid(board, row, col, c):
            for i in range(9):
                if board[i][col] == c:
                    return False
                if board[row][i] == c:
                    return False
                if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == c:
                    return False
            return True
        return dfs(board, 0, 0)
generator = SudokuGenerator(50)  # 挖空多少个格子
board = generator.generate()
for row in board:
    print(row)
print(str(board).count("."))
```


检查时间复杂度：

```python
import time
ties = []
for _ in range(100):
    t0 = time.time()
    generator = SudokuGenerator(60)  # 挖空多少个格子
    board = generator.generate()
    # for row in board:
    #     print(row)
    ties.append(time.time() - t0)
print(max(ties))
print(min(ties))
print(sum(ties) / len(ties))
```

得到的生成游戏所消耗的时间是：

254.41049194335938

0.02700185775756836

7.814508402347565

最大时间居然需要254秒，需要改进。

【算法题目】使用Python生成一个数独游戏的棋盘

【算法题目】【Python】彻底刷遍DFS与回溯的算法题目

参考：[https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/](https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/wo-xie-le--9c7a4/)






#  1 基本介绍

二分查找法（Binary Search）是一种在**有序数组**中查找某一特定元素的搜索算法。其基本思想是，首先将整个有序数列分成前后两部分，判断在哪个部分中可能会找到要查找的数，然后递归地在那个部分中查找。

具体来说，首先选择数列的中间元素。如果要查找的数比中间元素小，则在数列的左半部分继续查找；如果要查找的数比中间元素大，则在数列的右半部分继续查找；如果相等，则找到了要查找的数。这样一直递归进行，直到找到要查找的数或者整个数列被查找完。

二分查找法的时间复杂度为 O(log n)，其中 n 是数列中的元素个数。由于其在有序数列中查找元素的时间复杂度较低，因此常用于大规模有序数列的查找。

> 二分查找并不简单，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼。

- 有哪些细节：

> while循环中使用 low <= high 还是 low < high ？ 

> if条件里写<还是<=? 是low = mid +1？

> 还是low = mid ？



# 2 基本的二分查找

基本的二分查找中有序数组里的元素没有重复数值，而二分查找的目的就是找到符合条件的下标。

比如想在有序数组 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] 中找到元素5的index，该如何写python代码呢：

```python
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            return mid
    return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
result = binary_search(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 3 左边界 vs 右边界，查找相等的元素

当有序数组中存在重复值，即是由多个元素可以满足条件，返回哪一个下标更合适呢？

比如 arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]， 找数值5，那么左边界index是4，右边界index是6。 

如果有序数组中有重复值，并且你想找到左边界的下标，你可以在二分查找的基础上，做一些改变来实现这个功能。

下面的代码展示了左边界和右边界的代码：

```python
def binary_search_leftright(arr, x):
    low = 0
    high = len(arr) - 1
    result = -1
    while low <= high:  # 结束条件是 low > high， 为什么不用<符号呢：因为当low=high时，还需要判断一次，不然[low,high]就会被漏掉
        mid = (low + high) // 2  # 和mid=low+(high-low)//2是一样的结果，low+(high-low)//2可以防止大数溢出
        if arr[mid] < x:
            low = mid + 1  # 在区间 [mid+1, high] 中查找
        elif arr[mid] > x:
            high = mid - 1  # 在区间 [low, mid-1] 中查找
        elif arr[mid] == x:
            result = mid  # 记录符合条件的下标
            # high = mid - 1  # 在区间 [low, mid-1] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往左找. 即找左边界。
            low = mid + 1  # 在区间 [mid+1, high] 中查找，这就很灵性，意味着找到了，但是还要继续找，而且趋势是往右找. 即找右边界。
    return result
arr = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
if result != -1:
    print(f"Element is present at index {result}")
else:
    print("Element is not present in array")
```

# 4 难度升级，找到 x<6 的右边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x<6，且x是右边界元素：
```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low < high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1  # 继续在[mid+1, high]中查找，因为想找右边界
        else:
            high = mid  # 为什么不是mid-1呢?
    if arr[high] >= x:
        return high - 1
    else:
        return high
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 6
result = binary_search_right(arr, x)
print(result)
```

函数返回 high - 1 或者返回high。


- 如果将条件改为while low <= high呢，这样不可以吗？

> 如果你将循环的条件改为 while low <= high，在数组中查找小于目标值的右边界的时候是会有问题的。

> 

> 当low==high时，如果arr[high] >= x 那么最终返回值就是high -1,而实际上并不是小于目标值的右边界。

> 

> 因此，在二分查找中查找右边界时，循环条件应该是 low < high.

> 

> 这样当循环结束时，high指向的就是第一个大于等于目标值的位置，而high - 1就是小于目标值的右边界

> 

> 所以，在二分查找中查找右边界时，循环条件应该是 low < high 而非 low <= high,这是为了确保查找的正确性

> 

> 除此之外，还可能发生死循环。


- 那为什么是high = mid ，而不是high = mid -1？

> 在查找小于目标值的右边界时，如果循环条件是 low < high, 当 arr[mid] >= x 时,如果 high = mid -1 会使得 high 不满足循环条件,从而导致循环终止，而不是移动到小于目标值的右边界。

> 

> 而赋值high = mid会使得high = mid或者 high =

> mid-1,这样high总是满足循环条件且正确地找到了第一个大于等于目标值的位置,而high-1就是小于目标值的右边界。

> 

> 所以如果你想在查找小于目标值的右边界时，应该让 high = mid。这样可以保证查找的正确性。


# 5 找到 x>5 的左边界

在 arr = [4, 4, 5, 5, 6, 6, 7, 8, 9] 中找到一个元素x，满足x>5，且x是左边界元素：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid - 1
    return low
arr = [4, 4, 5, 5, 6, 6, 7, 8, 9]
x = 5
result = binary_search_left(arr, x)
print(result)
```

或者：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr)
    while low < high:
        mid = (low + high) // 2
        if arr[mid] <= x:
            low = mid + 1
        else:
            high = mid 
    return low
```


# 6 总结模板

当使用 "while low <= high" 时，要想结束循环，就需要更严格的判断，从而就不需要再单独对low 和high 进行特判。

如果要查找左边界（x>5的左边界）：

```python
def binary_search_left(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] <= x: # 如果是x>=5，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return low
```

如果要查找右边界（x<6的右边界）：

```python
def binary_search_right(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x: # 如果是x<=6，这里就需要改变查找区间
            low = mid + 1
        else:
            high = mid - 1
    return high
```

【算法题目】一文搞懂二分查找法

![在这里插入图片描述](/static/img/images/04904.png)





普通二叉树，每个节点的数值不相同。写一个函数，输入是树的根节点和要删除的节点的集合，删除某个节点意味着去除掉和这个节点的关联，剩下的都是子树，函数返回剩余子树数量。

input：root，｛1｝

output：2

input：root，｛1,,2,5｝

output：2

input：root，｛1,,2｝

output：3

input：root，｛4｝

output：3

input：root，｛4,9｝

output：2


程序还有点问题：
```python
import copy
from typing import Set
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
def getSubTree(root: Node, elements: Set, node_del=False) -> int:
"""
    if not elements or root is None:
        return 0
    if root.val in elements:
        elements = copy.deepcopy(elements)
        elements.remove(root.val)
        left_num = 1 + getSubTree(root.left, elements, True) if root.left is not None else 0
        right_num = 1 + getSubTree(root.right, elements, True) if root.right is not None else 0
        if node_del:
            return left_num + right_num - 1
        return left_num + right_num
    else:
        left_num = getSubTree(root.left, elements, False) if root.left is not None else 0
        right_num = getSubTree(root.right, elements, False) if root.right is not None else 0
        return left_num + right_num
        """
root = Node(1)
root.left = tree2 = Node(2)
root.right = tree3 = Node(3)
tree2.left = tree4 = Node(4)
tree2.right = tree5 = Node(5)
tree3.left = tree6 = Node(6)
tree3.right = tree7 = Node(7)
tree4.left = tree8 = Node(8)
tree4.right = tree9 = Node(9)
print(getSubTree(root, {1, 2, 5}))
```

【算法题目】【DFS】【一点资讯面试题】二叉树删除节点剩余子树数量

浮点数的 n次方根：





牛顿迭代法：
```python
class Solution:
    def sqrt_n(self, y, n) -> int:
        # f(x)=x**n-y=0
        # f`(x)=n*x^(n-1)
        # x=x-(x**n-y)/(n*2^(n-1))
        if n == 0:
            return 1
        # x1 的 n1 次方
        def pow1(x1, n1):
            if n1 == 0:
                return 1
            y1 = pow1(x1, n1 // 2)
            return y1 * y1 if n1 % 2 == 0 else y1 * y1 * x1
        x = 1  # 牛顿不动点迭代法
        while True:
            x2 = x - (pow1(x, n) - y) / (n * pow1(x, n - 1))
            if abs(x2 - x) < 1e-6:
                break
            x = x2
        return x2
```

二分查找：
```python
class Solution:
    def sqrt_n(self, y, n) -> int:
        assert n > 0
        # x1 的 n1 次方
        def pow1(x1, n1):
            if n1 == 0:
                return 1
            y1 = pow1(x1, n1 // 2)
            return y1 * y1 if n1 % 2 == 0 else y1 * y1 * x1
        # 二分查找，在0到y之间查找
        b1, b2 = 0, y
        while True:
            x = (b1 + b2) / 2
            if pow1(x, n) < y - 1e-2:
                b1 = x
            elif pow1(x, n) > y + 1e-2:
                b2 = x
            else:
                break
        return [x,-x]
```

【算法题目】浮点数的 n次方根 n次方 ，牛顿迭代法

#   1  题目




```
72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成
```

#   2  理解 题解

涉及到字符串的题目，十有八九是动态规划，而且几乎都是二维的。解决动态规划问题三要素：

（1）找出dp[] 元素的定义，题目一般非常隐晦。

（2）找出递推关系。dp[n] = $f($ dp[n-1] $)$  。 即是 **状态转移方程**。 

（3）找出初始状态。

编辑距离的题解理解：

（1）将编辑理解到位，简化为在单词 A 中插入一个字符、在单词 B 中插入一个字符、修改单词 A 的一个字符。

（2）由空字符串开头给初始状态。

（3）找出了状态转移方程。

![在这里插入图片描述](/static/img/images/04917.png)

![在这里插入图片描述](/static/img/images/04918.png)

![在这里插入图片描述](/static/img/images/04919.png)

#   3 程序

只要有状态转移方程，动态规划的程序好写：

注意，dp比word长度多1，因为dp里面存着初始数值。
```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not len(word1) * len(word2):
            return len(word1) + len(word2)
        # 初始状态
        dp = [[0 for _ in range(len(word1) + 1)] for _ in range(len(word2) + 1)]
        dp[0] = [i for i in range(len(word1) + 1)]
        for i in range(len(word2) + 1):
            dp[i][0] = i
        # 状态转移方程计算其余的状态
        for m in range(len(word2)):  # 每一行
            for n in range(len(word1)):  # 每一列
                i = m + 1
                j = n + 1
                # dp[i - 1][j]+1 在word1中插入一个变成word2
                # dp[i - 1][j]+1 在word2中插入一个变成word1
                # dp[i - 1][j - 1]+1 在word1中修改一个变成word2
                if word1[n] == word2[m]:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] - 1)
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[-1][-1]
```

【算法题目】【动态规划】字符串 编辑距离

算法刷题





```
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
```

# DFS 搜索树太深直接超时

```python
from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.coins_num_res = float("inf")
        def dfs(start, coins_num, residue):
            if residue == 0:
                self.coins_num_res = min(self.coins_num_res, coins_num)
                return
            for index in range(start, len(coins)):
                dfs(index + 1, coins_num, residue)  # dfs 路径1， 不选当前的硬币
                if coins[index] > residue:  # 当前的硬币选了后钱会多，剪枝
                    continue
                # 剪枝，coins_num_res 有结果。
                # 剪枝了也会超时
                if self.coins_num_res != float("inf") and (self.coins_num_res - coins_num) * coins[start] < residue:
                    break
                dfs(index, coins_num + 1, residue - coins[index])  # # dfs 路径2， 选上当前的硬币
        dfs(0, 0, amount)
        return self.coins_num_res if self.coins_num_res != float("inf") else -1
print(Solution().coinChange([1, 2, 5], 11))
# print(Solution().coinChange([411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422], 9864))
```

# BFS 最快的

构建BFS搜索必然借助deque，但是deque里面装什么，怎么搜，始终不太好想象：
```python
from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        from collections import deque
        queue = deque([amount])
        step = 0
        visited = set()
        while queue:
            n = len(queue)
            for _ in range(n):  # 本轮选择硬币
                residue = queue.pop()
                if residue == 0:
                    return step
                for coin in coins:
                    # residue >= coin 是停止条件
                    # (residue - coin) not in visited 是剪枝
                    if residue >= coin and (residue - coin) not in visited:
                        visited.add(residue - coin)
                        queue.appendleft(residue - coin)
            step += 1
        return -1
print(Solution().coinChange([411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422], 9864)) # 3万多次循环
```

# 动态规划

```python
class Solution1:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1
```

复现论文

介绍

参考资料

1 题目