# 1 香农墒  量化信息  信息量大小





[https://baike.baidu.com/item/%E9%A6%99%E5%86%9C%E7%86%B5/1649961?fr=aladdin](https://baike.baidu.com/item/%E9%A6%99%E5%86%9C%E7%86%B5/1649961?fr=aladdin)

1948 年，香农提出了“信息熵”(shāng) 的概念，解决了对**信息的量化度量问题**。

实质就是：信息不确定性的多少。

对于任意一个随机变量 X，它的熵定义如下：

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

变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。


# 2 交叉熵

[https://www.cnblogs.com/wangguchangqing/p/12068084.html](https://www.cnblogs.com/wangguchangqing/p/12068084.html)

非常好的解释：[https://www.zhihu.com/question/65288314/answer/244557337](https://www.zhihu.com/question/65288314/answer/244557337)

KL散度（度量2个概率分布之间的距离差异）公式：

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

交叉熵公式：

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

交叉熵=KL散度-熵

KL散度是非负的。

最小化KL散度 等价于 最小化交叉熵。

# 3 交叉熵损失函数

[https://zhuanlan.zhihu.com/p/35709485](https://zhuanlan.zhihu.com/p/35709485)

[https://zhuanlan.zhihu.com/p/35707643](https://zhuanlan.zhihu.com/p/35707643)

为什么它会在分类问题中这么有效呢？

主要原因是逻辑回归配合MSE损失函数时，采用梯度下降法进行学习时，会出现模型一开始训练时，**学习速率非常慢**的情况。

使用MSE的一个缺点就是其偏导值在输出概率值接近0或者接近1的时候非常小，这可能会造成模型刚开始训练时，偏导值几乎消失。

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

Cross Entropy Error Function（交叉熵损失函数）该函数是凸函数，求导时能够得到全局最优值。

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

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

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

香农墒 交叉熵

作者：Ghost





链接：[https://www.zhihu.com/question/51448623/answer/275721105](https://www.zhihu.com/question/51448623/answer/275721105)

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

<font face="微软雅黑" size = 5 color = red > **贝叶斯统计学派和频率派统计是不一样的。贝叶斯统计学派是含有先验知识的。** 

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

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

概率论 贝叶斯公式

代码：[https://github.com/simon20010923/DDAMFN/tree/main](https://github.com/simon20010923/DDAMFN/tree/main)





此算法是当前的第一名：[https://paperswithcode.com/paper/a-dual-direction-attention-mixed-feature](https://paperswithcode.com/paper/a-dual-direction-attention-mixed-feature)




# 介绍

面部表情在人类交流中起着重要作用，是理解情绪和态度的关键信号。因此，计算机需要获得辨识和解释面部表情的能力。[1–3]已经清楚地阐明了视觉感知、环境映射算法与基于生物识别认证计算机视觉的面部表情识别（FER）之间的关系，因此使用深度学习方法解决FER问题是有意义的。FER网络的主流架构通常由主干和头部组成。然而，最近的方法主要集中在头部或颈部区域，并仅使用VGG [4]或ResNet [5]作为其主干。值得注意的是，这些主干最初是为更大的数据集而设计的，可能会从图像中提取冗余信息，在相对较小的数据集中导致过度拟合。本文提出了一种创新的主干网络，称为混合特征网络（MFN）。MFN建立在MobileFaceNets [6]的基础上，这是一个专门为面部验证任务量身定制的轻量级网络。通过引入混合深度卷积核 [7]来增强MFN，这些卷积核利用了不同尺寸卷积核的优势。此外，坐标注意 [8]被引入到MFN架构中，以促进对长距离依赖的捕捉。因此，提取了用于FER的有意义的特征。

此外，FER面临着两个重要挑战：类间差异小和类内差异大。要解决这些挑战，建立各种面部区域之间的连接，如嘴巴、眼睛、鼻子等，至关重要。在这方面，注意机制提供了潜在的解决方案。具体来说，提出了双向注意（DDA）头，该头应用于所提出的方法，旨在根据提取的特征信息构建注意图。根据以前的工作 [8]，设计了从垂直和水平方向生成注意图的注意头。随后，将从双向注意网络（DDAN）获得的注意图与输入特征图相乘，得到一个新的特征图。该特征图经过线性全局深度卷积（GDConv）层 [6]，然后进行重塑操作。采用全连接层生成最终结果。通过集成所提出的DDA头和后续处理步骤，可以增强模型的能力。

最后，本文将MFN和DDAN集成在一起，提出了一种名为双向注意混合特征网络（DDAMFN）的新模型。

为了直观地展示DDAMFN的有效性，进行了涉及ResNet_50、MFN和DDAMFN模型的比较分析。所有模型都在AffectNet-7数据集上进行了训练，并在相同的测试数据上进行了测试。Grad-CAM [9]被应用于捕获各自主干架构提取的特征的见解。该技术通过基于梯度的定位，促进了通过热图突出显示图像中的重要区域进行预测。该分析的结果在图1中呈现。对结果的综合评估展示了模型之间注意焦点的明显模式。很明显，MFN关注的区域比ResNet_50更特定。对于DDAMFN，DDAN允许MFN定位更合适的区域。

图1。七张图像的热图：中性（第1行），快乐（第2行），悲伤（第3行），惊讶（第4行），恐惧（第5行），厌恶（第6行）和愤怒（第7行）。列1：原始图像。列2：ResNet_50。列3：MFN。列4：DDAMFN（MFN + DDAN）。很明显，MFN关注的区域比ResNet_50更特定。DDAN允许MFN定位更合适的区域。

此外，当在各种基准数据集上进行了大量实验时，DDAMFN模型表现出了显着的性能，将其确立为FER领域的当前最先进网络。我们研究的贡献可以总结如下：

（1）为了增强FER的提取特征的质量，本研究提出了一种名为MFN的新型主干网络。MFN利用不同内核尺寸的利用，从而有助于获得强大的特征。此外，在MFN架构中包含坐标注意层，可以捕捉长距离依赖性，进一步增强了其在FER任务中的有效性。

（2）为了有效检测不同面部表情之间的细微变化，引入了DDAN。通过从两个不同方向生成关注，DDAN旨在全面捕捉相关的面部区域，并提高FER的区分能力。

（3）应用了一种新颖的注意力损失机制，以确保DDAN的注意头聚焦在不同区域，从而显著提高了模型的整体性能和区分能力。

（4）对著名的FER数据集进行了广泛的评估，包括A

ffectNet、RAF-DB和FERPlus，以评估DDAMFN的性能。实验结果表明，其在AffectNet-7上的准确率为67.03％，在AffectNet-8上为64.25％，在RAF-DB上为91.35％，在FERPlus上为90.74％。这些出色的结果突显了DDAMFN在FER领域的有效性和优越性。

# 网络结构

DDAMFN的架构概述如图2所示，包括两个主要组件：MFN和DDAN。首先，面部图像被输入到MFN中，产生基本的特征图作为输出。随后，通过DDAN在垂直和水平方向生成注意力图。最终，注意力图被重塑为特定维度，并通过全连接层预测图像的表情类别。

DDAMFN框架有效地结合了MFN的特征提取能力和DDAN的注意机制的判别力。通过整合这些组件，DDAMFN可以在FER任务中实现改善的性能。

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

MFN结构：

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

# 损失

如图2所示，从DDAN获得的大小为7×7×512的特征图经过线性GDConv层和线性层处理。然后，将转换后的特征图重新形状为一个512维的向量。通过全连接层获得类别置信度。在损失函数方面，训练过程中采用标准的交叉熵损失。该损失函数有效地衡量了预测类别概率与真实标签之间的差异，有助于优化模型的参数。整体损失函数可以表示为：

L = L_cls + λ_a * L_att，(3)

其中，L_cls代表标准交叉熵损失，L_att是注意力损失。λ_a是一个超参数，默认值为0.1。


# 指标比较 

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

# 处理数据

在DDAMFN中，只有前8个类别是重要的。我将后面三个类别都归位负样本类别。

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

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

使用此代码处理数据，将原始数据集进行转换：

```python
import os
import shutil
import pandas as pd
from tqdm import tqdm
root = r"/ssd/xd/src_data/Manually_Annotated_Images/"
# training.csv
training_csv = r"/ssd/xd/src_data/training.csv"
# validation.csv
validation_csv = r"/ssd/xd/src_data/validation.csv"
dst_train = r"/ssd/xd/src_data/new_datasets_ImageFolder/train"
os.makedirs(dst_train, exist_ok=True)
dst_val = r"/ssd/xd/src_data/new_datasets_ImageFolder/val"
os.makedirs(dst_val, exist_ok=True)
# subDirectory_filePath列是图片的路径，expression列是标签
# 用标签创建子文件夹，然后对应图片移动到对应文件夹
df_train = pd.read_csv(training_csv)
df_train = df_train[["subDirectory_filePath", "expression"]]
for i in tqdm(range(len(df_train))):
    img_path = os.path.join(root, df_train.iloc[i, 0])
    label = df_train.iloc[i, 1]
    dst = os.path.join(dst_train, str(label))
    os.makedirs(dst, exist_ok=True)
    if os.path.exists(img_path):
        shutil.copy(img_path, dst)
df_val = pd.read_csv(validation_csv)
df_val = df_val[["subDirectory_filePath", "expression"]]
for i in tqdm(range(len(df_val))):
    img_path = os.path.join(root, df_val.iloc[i, 0])
    label = df_val.iloc[i, 1]
    dst = os.path.join(dst_val, str(label))
    os.makedirs(dst, exist_ok=True)
    if os.path.exists(img_path):
        shutil.copy(img_path, dst)
# 0到7的类别标签保留，其余的都转为一个标签8
dst_train_8 = r"/ssd/xd/src_data/new_datasets_ImageFolder/train/8"
dst_train_9 = r"/ssd/xd/src_data/new_datasets_ImageFolder/train/9"
dst_train_10 = r"/ssd/xd/src_data/new_datasets_ImageFolder/train/10"
# 将9和10类别的图片移动到8类别文件夹，然后删除9和10文件夹
files_9 = os.listdir(dst_train_9)
files_10 = os.listdir(dst_train_10)
for file in files_9:
    shutil.move(os.path.join(dst_train_9, file), os.path.join(dst_train_8, file))
for file in files_10:
    shutil.move(os.path.join(dst_train_10, file), os.path.join(dst_train_8, file))
shutil.rmtree(dst_train_9)
shutil.rmtree(dst_train_10)
dst_val_8 = r"/ssd/xd/src_data/new_datasets_ImageFolder/val/8"
dst_val_9 = r"/ssd/xd/src_data/new_datasets_ImageFolder/val/9"
dst_val_10 = r"/ssd/xd/src_data/new_datasets_ImageFolder/val/10"
# 将9和10类别的图片移动到8类别文件夹，然后删除9和10文件夹
files_9 = os.listdir(dst_val_9)
files_10 = os.listdir(dst_val_10)
for file in files_9:
    shutil.move(os.path.join(dst_val_9, file), os.path.join(dst_val_8, file))
for file in files_10:
    shutil.move(os.path.join(dst_val_10, file), os.path.join(dst_val_8, file))
shutil.rmtree(dst_val_9)
shutil.rmtree(dst_val_10)
```


得到：

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

文件夹 0 中的文件数量为: 74874

文件夹 1 中的文件数量为: 134415

文件夹 2 中的文件数量为: 25459

文件夹 3 中的文件数量为: 14090

文件夹 4 中的文件数量为: 6378

文件夹 5 中的文件数量为: 3803

文件夹 6 中的文件数量为: 24882

文件夹 7 中的文件数量为: 3750

文件夹 8 中的文件数量为: 127148

文件夹 0 中的文件数量为: 500

文件夹 1 中的文件数量为: 500

文件夹 2 中的文件数量为: 500

文件夹 3 中的文件数量为: 500

文件夹 4 中的文件数量为: 500

文件夹 5 中的文件数量为: 500

文件夹 6 中的文件数量为: 500

文件夹 7 中的文件数量为: 500

文件夹 8 中的文件数量为: 1500


# 下载代码训练

https://github.com/simon20010923/DDAMFN/tree/main

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

# 效果

垂直领域模型比通用分类模型强多了，这3轮直接干到道心破碎：

(py310_torch)   Tue Mar 19 #   15:54:01 #   /ssd/src_data/eff_train/DDAMFN-main # python affectnet_train.py

Whole train set size: 414798

Validation set size: 5500

[Epoch 1] Training accuracy: 0.4141. Loss: 3.846. LR 0.000100

[Epoch 1] Validation accuracy:0.4827. Loss:7.671

best_acc:0.4827

Model saved.

[Epoch 2] Training accuracy: 0.5221. Loss: 2.075. LR 0.000060

[Epoch 2] Validation accuracy:0.5035. Loss:5.648

best_acc:0.5035

Model saved.

[Epoch 3] Training accuracy: 0.5471. Loss: 1.810. LR 0.000036

[Epoch 3] Validation accuracy:0.5105. Loss:4.621

best_acc:0.5105

Model saved.

[Epoch 4] Training accuracy: 0.5606. Loss: 1.685. LR 0.000022

[Epoch 4] Validation accuracy:0.5198. Loss:3.784

best_acc:0.5198

Model saved.

[Epoch 5] Training accuracy: 0.5674. Loss: 1.618. LR 0.000013

[Epoch 5] Validation accuracy:0.5220. Loss:3.048

best_acc:0.522

Model saved.

 12%|██████████████▌                        


最后结果：

[Epoch 38] Training accuracy: 0.5799. Loss: 1.502. LR 0.000000

[Epoch 38] Validation accuracy:0.5225. Loss:2.505

best_acc:0.5245

Model saved.

[Epoch 39] Training accuracy: 0.5784. Loss: 1.505. LR 0.000000

[Epoch 39] Validation accuracy:0.5235. Loss:2.513

best_acc:0.5245

Model saved.

[Epoch 40] Training accuracy: 0.5799. Loss: 1.504. LR 0.000000

[Epoch 40] Validation accuracy:0.5215. Loss:2.496

best_acc:0.5245

Model saved.



# 试试8个类别的训练

8个类别表情少了一些数据干扰，结果好多了：

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

训练结果：

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


Model saved.

[Epoch 33] Training accuracy: 0.5960. Loss: 1.590. LR 0.000000

[Epoch 33] Validation accuracy:0.6235. Loss:2.621

best_acc:0.6265

Model saved.

[Epoch 34] Training accuracy: 0.5939. Loss: 1.596. LR 0.000000

[Epoch 34] Validation accuracy:0.6258. Loss:2.589

best_acc:0.6265

Model saved.

[Epoch 35] Training accuracy: 0.5967. Loss: 1.593. LR 0.000000

[Epoch 35] Validation accuracy:0.6263. Loss:2.558

best_acc:0.6265

Model saved.

[Epoch 36] Training accuracy: 0.5963. Loss: 1.593. LR 0.000000

[Epoch 36] Validation accuracy:0.6263. Loss:2.578

best_acc:0.6265

Model saved.

[Epoch 37] Training accuracy: 0.5951. Loss: 1.593. LR 0.000000

[Epoch 37] Validation accuracy:0.6252. Loss:2.576

best_acc:0.6265

Model saved.

[Epoch 38] Training accuracy: 0.5960. Loss: 1.591. LR 0.000000

[Epoch 38] Validation accuracy:0.6272. Loss:2.607

best_acc:0.6272

Model saved.

[Epoch 39] Training accuracy: 0.5957. Loss: 1.592. LR 0.000000

[Epoch 39] Validation accuracy:0.6255. Loss:2.612

best_acc:0.6272

Model saved.

[Epoch 40] Training accuracy: 0.5969. Loss: 1.592. LR 0.000000

[Epoch 40] Validation accuracy:0.6235. Loss:2.588

best_acc:0.6272

Model saved.

100%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████| 40/40 [3:58:59<00:00, 358.48s/it]


# 8类验证精度

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

# 8类训练损失变化

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


# 8类混淆矩阵

混淆矩阵很容易看出，本身是某个类别的数据，被误判为哪个类别去了，可以看出某两个类别容易混淆。

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

# 推理测试

推理这张图：

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

a100显卡CUDA推理：

用时0.029578685760498047秒

Class Neutral: 0.0000

Class Happy: 0.0001

Class Sad: 0.0000

Class Surprise: 0.0008

Class Fear: 0.0125

Class Disgust: 0.0001

Class Angry: 0.9865

Class Contempt: 0.0000

# 转onnx模型

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

```cpp
    # Define input example
    dummy_input = torch.randn(1, 3, 112, 112, device=device)
    # Perform inference to capture dynamic computation graph
    with torch.no_grad():
        output, _, _ = model(dummy_input)
    # Export the model to ONNX
    torch.onnx.export(model, dummy_input, args.output_path, verbose=True,opset_version=10)
    print(f"ONNX model exported to {args.output_path}")
```

# onnx推理

```cpp
def inference(args):
    # Load ONNX model
    ort_session = onnxruntime.InferenceSession(args.onnx_model_path)
    time1 = time.time()
    # Preprocess input image
    image_transform = transforms.Compose([
        transforms.Resize((112, 112)),
        transforms.ToTensor(),
        transforms.Normalize(mean=[0.485, 0.456, 0.406],
                             std=[0.229, 0.224, 0.225])
    ])
    image = Image.open(args.image_path).convert('RGB')
    image_tensor = image_transform(image).unsqueeze(0).numpy()
    # Perform inference
    ort_inputs = {ort_session.get_inputs()[0].name: image_tensor}
    ort_outs = ort_session.run(None, ort_inputs)
    logits = np.squeeze(ort_outs[0])
    # Apply softmax
    probabilities = np.exp(logits) / np.sum(np.exp(logits), axis=0)
    time2 = time.time()
    print(f"Inference time: {time2 - time1} seconds")
    return probabilities
```

Inference time: 0.08892297744750977 seconds

Class Neutral: 0.0000

Class Happy: 0.0001

Class Sad: 0.0000

Class Surprise: 0.0008

Class Fear: 0.0125

Class Disgust: 0.0001

Class Angry: 0.9865

Class Contempt: 0.0000


# 结合一些别的项目

本文的分类器只是针对方形图像进行分类的，所以一些日常图片要进行人脸检测，可以参看项目：

[https://github.com/derronqi/yolov8-face](https://github.com/derronqi/yolov8-face)

[https://github.com/hpc203/yolov8-face-landmarks-opencv-dnn/tree/main](https://github.com/hpc203/yolov8-face-landmarks-opencv-dnn/tree/main)

## 跑完后的一些图鉴

![请添加图片描述](/static/img/images/00056.jpeg)

![请添加图片描述](/static/img/images/00057.png)

![请添加图片描述](/static/img/images/00058.png)


![请添加图片描述](/static/img/images/00059.png)

![请添加图片描述](/static/img/images/00060.png)

![请添加图片描述](/static/img/images/00061.png)

![请添加图片描述](/static/img/images/00062.png)

![请添加图片描述](/static/img/images/00063.png)



# 做个gradio的web app

用gradio做了个页面，可以上传图片后，对图片进行人脸检测，然后进行人脸推理，效果如下：

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






# 代码、训练、权重、帮助

如果想获取帮助：

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

【深度学习】表情识别A Dual-Direction Attention Mixed Feature Network for Facial Expression Recognition 训练

# 复现论文





![在这里插入图片描述](/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
```

【算法题目】DFS BFS 动态规划 零钱兑换 Python

算法刷题





```
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
```

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(sol: str, left: int, right: int):
            if left == 0 and right == 0:
                res.append(sol[:])
                return
            if left == right:
                dfs(sol + "(", left - 1, right)  # 使用一个左括号
            elif left < right:
                if left:
                    dfs(sol + "(", left - 1, right)  # 剩余左括号小于右括号，可以选择性来个括号
                dfs(sol + ")", left, right - 1)
        res = []
        dfs("", n, n)
        return res
```

【算法题目】【奇怪的DFS】Python 括号生成

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





# DFS+剪枝：直接超时：
```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def dfs(start, sol: List):
            # print(sol)
            if start > n:  # 结束条件，
                return
            if len(sol) >= 3:
                if sum(sol) == 0:
                    res.append(sol[:])
                return
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:  # 为了排除相同结果
                    continue
                sol.append(nums[i])
                dfs(i + 1, sol)
                sol.pop()
        nums.sort()
        n = len(nums)
        res = []
        dfs(0, [])
        return res
```

# 排序 + 双指针

双指针双向移动也能减少计算，拿到结果就能拜拜进行下一次，不像DFS没有太考虑数据的有序性，在DFS中的排序仅仅剪枝用了一下。

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:  # 指针位置性
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans
```

【算法题目】【DFS】Python 三数之和 DFS+剪枝 排序 + 双指针

# 题目




```
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

# 解答1 动态规划 转为最长子字符串（执行超时 200ms）

如果将字符串倒置，原问题变化到求最长子字符串问题：[https://blog.csdn.net/x1131230123/article/details/124176271](https://blog.csdn.net/x1131230123/article/details/124176271)。

下图是输入`"babad"`的dp，需要注意取的是第一次的i行j列。

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

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 倒序字符串，求最长公共子串
        s1 = s[::-1]
        m, n = len(s), len(s1)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        maxlen = 0
        maxend = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == s1[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = 0
                if maxlen < dp[i][j]: # 保留第一次最大的，字符串多个同长度回文只留第一次的
                    if n - j == i - dp[i][j]: # 判断回文位置，位置必须是同一个位置，比如输入acaabkaaca，回文不是acaa才行
                        maxlen = dp[i][j]
                        maxend = i
        return s[maxend - maxlen:maxend]
```

# 解答2 中心扩散 （1ms量级）

字符串非常长的时候，动态规划 $O(n^2)$ 的时间复杂度，计算量太大，而且停不下来，中心扩散法能够及时止住，时间复杂度虽然也是 $O(n^2)$ ，但期望下来小多了。

```python
class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)  # 奇数个，从本字符扩散
            left2, right2 = self.expandAroundCenter(s, i, i + 1)  # 偶数个，从本字符和下一个字符扩散
            if right1 - left1 > end - start:  # 保留最大的边界
                start, end = left1, right1
            if right2 - left2 > end - start:  # 保留最大的边界
                start, end = left2, right2
        return s[start: end + 1]
```

# 解答3 动态规划 直接

这个动态规划太难想了，建议别看了==
```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i:j] 是否是回文串
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                if s[i] != s[j]:
                    dp[i][j] = 0
                else:
                    if j - i < 3:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]
```

【算法题目】【动态规划】Python 最长回文子串

# 1 巧妙的思路





看到了一个巧妙的思路：

python3
```python
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        h1 = 0
        h2 = 0
        for i in range(len(height)):
            h1 = max(h1,height[i])
            h2 = max(h2,height[-i-1])
            ans = ans + h1 + h2 -height[i]
        return  ans - len(height)*h1
```

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

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

# 2 如何理解

将循环中这句话`ans = ans + h1 + h2 -height[i]`分开理解，对于所有的遍历过程中的所有`h1` ，当`h1` 小于最大值，就会减去`height[i]` ，这样就得到了左边的雨水+ 右边整个面积。下图的红色表示了最终的数值。

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

对于所有的遍历过程中的所有`h2` ，当`h2` 小于等于最大值，就会减去`height[i]` ，这样就得到了右边的雨水+ 左边整个面积。下图的橘色表示了最终的数值。

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

将上面的2个面积加起来，会得到 所有的雨水+ `len(height)*h1` 。


我真是服了。

# 3 动态规划

动态规划没这个思路简单。不写了。

【算法题目】【动态规划】接雨水

员工参加考试，判断题X10（每个2分），单选题X10（每个4分），多选题X5（每个八分）。只能顺序作答，答对得分，答错不得分。答错三道，中止考试。输入考试结果分数，输出答题可能情况个数。





1 需要dfs传递的参数才写成参数，能全局变量就尽量全局。

2 这题传了开始位置、错误次数、分数，三者都是停止条件。

3 搜索也分回溯或者不回溯。

不回溯：

python：
```python
def cal(score_in):
    def dfs(start, error, score):
        if start == n:
            return
        if error >= 3:
            return
        if score == score_in:
            res.append(1)  # 此搜索路径是对的，已经拼凑出
            return
        if score > score_in:
            return
        dfs(start + 1, error, score + nums[start])  # 本题做对
        dfs(start + 1, error + 1, score)  # 本题做错
    nums = [2] * 10 + [4] * 10 + [8] * 5
    n = len(nums)
    res = []
    dfs(0, 0, 0)
    return len(res)
```

回溯：
```python
def cal(score_in):
    def dfs(start, error, score):
        if start == n:
            return
        if error >= 3:
            return
        if score == score_in:
            res.append(1)  # 此搜索路径是对的，已经拼凑出
            return
        if score > score_in:
            return
        for i in range(start, len(nums)):
            score += nums[i]  # 本题对
            dfs(i + 1, error, score)
            score -= nums[i]  # 回溯
            error += 1
    nums = [2] * 10 + [4] * 10 + [8] * 5
    n = len(nums)
    res = []
    dfs(0, 0, 0)
    return len(res)
```

【算法题目】【DFS】考试得分组合

# 1岛屿数量





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

题目很好理解，dfs来一套即可：

（1）二维的，没考虑特殊情况；

（2）对每个网格dfs，每次dfs往上下左右搜

（3）grid是list，在python里面会是一个全局，第一次搜到记一次搜到了一块岛屿，后面的dfs都是为了扫清上下左右的岛屿；

（4）dfs三要素：

a 如何结束

b 如何递归

c 如何剪枝，这里不需要

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(x,y,flagfrist):
            if x<0 or x>=m or y<0 or y>=n:
                return 
            if grid[x][y]=="1":
                if flagfrist==0:
                    res.append(1)
                    flagfrist=1
                grid[x][y]="0"
                dfs(x-1,y,flagfrist)
                dfs(x+1,y,flagfrist)
                dfs(x,y-1,flagfrist)
                dfs(x,y+1,flagfrist)
        m=len(grid)
        n=len(grid[0])
        res=[]
        for i in range(m):
            for j in range(n):
                dfs(i,j,0)
        return len(res)
```

# 2 岛屿中面积最大值

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

写dfs，把重点放在结束条件和如何递归上，多考虑搜索数结构，

能定义为全局变量的就定义为全局变量，**需要往下一级递归的变量才定义为dfs函数的参数**，不然会陷入乱糟糟的传参中！ 

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[str]]) -> int:
        def dfs(x,y):
            if x<0 or x>=m or y<0 or y>=n:
                return 
            if grid[x][y]==1:
                area.append(1)
                grid[x][y]=0
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y-1)
                dfs(x,y+1)
        m=len(grid)
        n=len(grid[0])
        res=0
        for i in range(m):
            for j in range(n):
                area=[]
                dfs(i,j)
                res=max(len(area),res)
        return res
```

【算法题目】【DFS】岛屿数量 岛屿中面积最大值

# 1 组合





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

数字都不同，dfs搜索：
```python
from typing import List
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start):
            if len(sol) == k:
                res.append(sol[:])
                return
            if start == len(nums):
                return
            for i in range(start, len(nums)):
                sol.append(nums[i])
                dfs(i + 1)
                sol.pop()
        res = []
        sol = []
        nums = list(range(1, n + 1))
        dfs(0)
        return res
```

# 2 组合总和

39. 组合总和

[https://leetcode-cn.com/problems/combination-sum/comments/](https://leetcode-cn.com/problems/combination-sum/comments/)

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

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        def recursion(idx, res):
            if idx >= len(candidates) or res >= target:
                if res == target:
                    ans.append(temp[:])
                return
            temp.append(candidates[idx])
            recursion(idx, res + candidates[idx]) 
            temp.pop()
            recursion(idx + 1, res)
        recursion(0, 0)
        return ans 
```

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res
```

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            # 解法1
            # dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            # dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
            # 解法2
            for i in range(index,n):
                sol_sum+=candidates[i]
                sol+=[candidates[i]]
                dfs(i, sol_sum, sol) # 基于此继续选择，传i，下一次就不会选到i左边的数
                sol_sum-=candidates[i]
                sol.pop()
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res
```

# 3 组合总和2

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

[https://leetcode-cn.com/problems/combination-sum/comments/](https://leetcode-cn.com/problems/combination-sum/comments/)
```python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(pos: int, rest: int):
            nonlocal sequence
            if rest == 0:
                ans.append(sequence[:])
                return
            if pos == len(freq) or rest < freq[pos][0]:
                return
            dfs(pos + 1, rest)
            most = min(rest // freq[pos][0], freq[pos][1])
            for i in range(1, most + 1):
                sequence.append(freq[pos][0])
                dfs(pos + 1, rest - i * freq[pos][0])
            sequence = sequence[:-most]
        freq = sorted(collections.Counter(candidates).items())
        ans = list()
        sequence = list()
        dfs(0, target)
        return ans
```

# 4 子集

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

[https://leetcode-cn.com/problems/subsets/](https://leetcode-cn.com/problems/subsets/)

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

[https://leetcode-cn.com/problems/subsets-ii/](https://leetcode-cn.com/problems/subsets-ii/)

1 香农墒量化信息信息量大小

复现论文

介绍

参考资料

1 题目

题目

1 巧妙的思路

1岛屿数量

1 组合

1 香农墒 量化信息 信息量大小