AI制药：分子对接

任务：

1、安装学习yutobe上面的软件

https://www.youtube.com/watch?v=Sux91FJ3Xe8&t=629s

2、跑通论文代码

https://www.youtube.com/watch?v=Sux91FJ3Xe8&t=629s

Pymol简介

Pymol是一款操作简单，功能强大的分子以及蛋白的可视化软件，由薛定谔公司研发，科研人员可以从官网申请最新教育版本，同时pymo的开源版（https://github.com/schrodinger/pymol-open-source），可以直接从网站上下载，但是版本较老。所以，根据需求选择版本进行下载。说明： https://cloud.tencent.com/developer/article/1785088

Pymol入门教程：

http://pymol.chenzhaoqiang.com/intro/startManual.html

分子对接教程

1、

https://cloud.tencent.com/developer/inventory/15332

2、https://www.bilibili.com/video/av466685164?from=search&seid=9870338638011316620&spm_id_from=333.337.0.0

vina只负责对接，mgltool负责提供蛋白质分子和配体分子。

先用MGL 生成vina需要的pdbqt文件

MGL tools的作用就是生成pdbqt文件

1、：打开MGL tools，打开受体蛋白的pdb ：file-》read molecule

2、蛋白质的pdb（数据库）：

关于蛋白质结构的PDB文件，做分子对接，估计大家都知道PDB这个蛋白质数据库啦。这里简单的介绍一下。

蛋白质的三级结构是指整条多肽链的三维空间结构，也就是包括碳骨架和侧链在内的所有原子的空间排列。第一个蛋白质的三维空间结构于 1958 年用 X-射线衍射法（X-ray Crystallography）测定。这种方法目前仍然是获取蛋白质三级结构的主要方法。PDB 数据库中绝大多数蛋白质结构都是用这种方法测定的。另一个测定蛋白质三维空间结构的方法是核磁共振法（Nuclear Magnetic Resonance, NMR）。无法结晶的蛋白质，可以利用核磁共振法在液体环境中进行结构测定。但是核磁共振法只能用于质量小于 70 千道尔顿的分子，大约对应 200 个氨基酸的长度。除此之外，还有一些不太常用的方法也可以测定分子的三维空间结构，比如冷冻电子显微镜技术（Cyro-Electron Microscopy）。无论用什么方法测定的空间结构，都要提交到 PDB 数据库。所以我们获取蛋白质三级结构最直接的办法就是去PDB 搜索（http://www.rcsb.org/）。从PDB首页的搜索条里，可以通过搜索PDB ID、分子名称、作者姓名等关键词来查找蛋白质三级结构。此外，利用高级搜索工具，可以通过序列相似性搜索获得与输入序列在序列水平上相似的蛋白质的三级结构。搜索方法选 BLAST，输入序列，点击“Result Count”。这里不详细介绍，因为我们做分子对接，通常蛋白名称是已知的。我们重点介绍怎么选择合适的蛋白结构文件。比如我们搜索PI3K这个蛋白，直接在搜索栏搜索，结果是有很多的。可以看到有393个结构信息。首先我们可以通过左边的栏进行筛选，比如物种信息，我们选择人。当然，结果的显示排序可通过结果上面的选项卡进行选择不同的排序方式。我们筛选合适的蛋白结构，常用Score这个选项.我们选择分辨率较好的在前。这里的0.9Å，Å是光波长度和分子直径的常用计量单位，值越小，分辨率越高，结构越准确。页面往下拉，可以看见这个值越来越大，我们优先选择值小的。我们可以从页面里面看见一下基本信息，比如方法，物种以及被解析的时间等。这里5GJI这个结构获取的方法就是X-RAY。我们点击这个蛋白，进入后可以看见详细的信息。然后我们还要看这个蛋白的描述是不是我们想要的蛋白，从这里面感觉看起来比较费劲。这里我们借助uniprot这个数据库来选择是比较方便的。这里简单介绍一下这个数据库，可能有的同学是第一次知道。翻了多年前的笔记，粘贴在下面。 UniProt 数据库有三个层次。

第一层叫 UniParc，收录了所有 UniProt 数据库子库中的蛋白质序列，量大，粗糙。

第二层是 UniRef，他归纳了 UniProt 几个主要数据库并且是将重复序列去除后的数据库。

第三层是 UniProtKB，他有详细注释并与其他数据库有链接，分为 UniProtKB 下的 Swiss-Prot和 UniProtKB 下的 TrEMBL 数据库。

关系稍有点复杂，但实际上我们最常用的就是 UniProtKB下的 Swiss-Prot 数据库。

从 UniProt 数据库查看一条蛋白质序列（http://www.uniprot.org/）。在UniProt数据库的首页上有一个关于 UniProtKB 数据库的统计表。可以看到，TrEMBL 数据库里存储的序列数量远远大于 Swiss-Prot 中的。统计表里清楚的写着：TrEMBL 是自动注释的，没有经过检查，而 Swiss-Prot 是人工注释的，并且经过检查。

然后点击下载文件就可以直接下载PDB格式的蛋白结构文件。下载的PDB文件可以用pymol或者VMD观察结构。能够实现蛋白质三维结构可视化的软件非常多。比专业级的PyMOL（https://pymol.org/2/）。这个软件已经被世界上著名的生物医药软件公司“薛定谔公司（Schrödinger）”收购。这种专业级的可视化软件不仅能够做出非常漂亮的图片，它还有强大的插件支持各种各样的蛋白质结构分析，这款软件需要购买，如果你发表的文章里提到某些内容是使用PyMOL制作的，而文章中所有作者和作者单位都没有PyMOL的购买记录的话，你可能会面临薛定谔公司的追责。如果要对接的蛋白没有结构，我们又要对接，那就只能是自己通过软件预测了。蛋白质结构预测的方法有从头计算法，同源建模法，穿线法和综合法。常用的是同源建模法，SWISS-MODEL（www.swissmodel.expasy.org）就是一款用同源建模法预测蛋白质三级结构的全自动软件，这里不详细介绍了，预测的模型还要涉及模型好坏的评价，后续有时间，再介绍蛋白质三级结构的预测。

接下来我们打开AutoDockTools(ADT)，打开我们前面保存的文件1E8Y_PYMOL.pdb

删除水分子和其他配体，常规操作不用解释

然后计算电荷和添加原子类型

Edit–Charges–Compute Gasteiger

Edit–Atoms–Assign AD4 type

就可以导出成pbdqt格式的文件了

然后右键吧蛋白删除掉，导入配体小分子，随便从ZINC下了一个

ZINC(http://zinc.docking.org/) 还有一个数据库能下载mol2格式的文件。ZINC)，这里就不介绍了，你要是能从上面的数据库下载到你配体小分子的mol2格式文件，就直接用，如果不能，那就是去PubChem数据库(https://pubchem.ncbi.nlm.nih.gov/)下载sdf文件，然后进行转换，这也是我这里要介绍的。

Ligand-input-open

分子对接教程

1 分子对接的工作环境
1.1 对接基本需求
受体的 pdb 文件、知道配体的结构
1.2 对接软件
使用 AutoDock 进行对接，该软件由 AutoDock 和 MGLTools 两
部分组成，AutoDock 为主程序，仅提供了命令行接口，而 MGLTools
中的 AutoDockTools（ADT）可以看作是 AutoDock 的图形用户界面。
配体使用 ChemDraw 和 Chem3D 绘制，该软件为收费软件，可
使用其它免费的结构式绘制工具进行结构绘制，使用 Open Babel 转
3D 结构和文件格式的转换。
使用 PyMol 开源版本对受体蛋白的 pdb 文件进行处理。

2 准备受体、配体的 pdbqt 文件

AutoDock 只接受 pdbqt 格式的文件，所以需要通过
AutoDockTools 将 pdb 或者其他格式的文件转化为 pdbqt 文件。

2.1 准备受体的 pdbqt 文件
2.1.1 使用 PyMol 软件进行处理

pdb 下载的蛋白需要先使用 PyMol 软件删除多余的离子、水分
子，同源多聚体蛋白还可以只保留一条链。直接从 pdb 下载蛋白可以
使用 fetch [protein name]命令。导入后 pdb 文件后，点击右下角的 S
以显示结构信息、

2.1.2 关于 pdb 文件的格式

该格式省略了一切氢原子，包括游离的水分子都只保留了一个 O，所以后续需要加氢操作。该文件的格式较复杂，最好使用成熟的软件进行编辑，而不上自行编辑。该文件中的氨基酸残基的原子全部记录在 ATOM 行中，后面的每一项分别为原子序号、原子名称（第一个字母为原子的元素符号，第二个字母为远近标识符 A、B、G、D、E、Z、H 分别对应有机化合物命名系统中的 α、β、γ、δ、ε、ζ、η）、残基名称、链编号、残基序号、原子坐标等

而离子、水分子以及结合在蛋白中的配体（如抑制剂等）等非蛋白质的部分记录在 HETNAM（非标准残基的名称）中：

同样的依次是原子编号、原子名称、基团名称（如水这里起名为HOH）、链编号（但是它本身不依附于哪条链）、原子编号、坐标等。

2.1.3 使用 PyMol 命令进行选择和删除
选择也可以使用命令选择，select 命令可以用于选择链如：
select chain A
indicate 命令的格式则为 indicate [element_type] [name]，如根据残基
名称 HOH 选择所有的水分子：
indicate resname HOH
需要注意的是，选择水分子不要使用：
indicate name O
否则其会选中所有氨基酸残基中的氧原子。根据残基名称选择配体
Mr-Greyfun
（示例中配体名称为 STI）：
indicate resname STI
根据原子名称选择氯原子：
indicate name CL
可以使用 remove 命令进行删除操作，命令格式与之类似：
remove resname HOH
remove name CL
remove chain B

2.1.1 保存
在 PyMol 中完成上述处理后使用 Export Molecule-save 保存成pdb 格式的文件。
2.1.2 加氢操作
pdb 文件会省略氢原子，所以需要进行加氢，可以在 PyMol 中使用 h_add 命令加氢（删除为 remove hydrogen ），但最好使用AutoDockTools（ADT）进行加氢。处理好后的文件用 ADT 打开后，点击 Edit-Hydrogens-Add-OK。加氢。
2.1.3 转化为 pdbqt 格式的文件
点击 Grid-Macromolecule-Choose，选择好后点 select molecule，
它会自动加电荷等，点 OK 即可，完成后，会弹出保存窗口，直接保
存 pdbqt 格式即可

2.1.1 保存
在 PyMol 中完成上述处理后使用 Export Molecule-save 保存成
pdb 格式的文件。
2.1.2 加氢操作
pdb 文件会省略氢原子，所以需要进行加氢，可以在 PyMol 中使
用 h_add 命令加氢（删除为 remove hydrogen ），但最好使用
AutoDockTools（ADT）进行加氢。
处理好后的文件用 ADT 打开后，点击 Edit-Hydrogens-Add-OK。
加氢。
2.1.3 转化为 pdbqt 格式的文件
点击 Grid-Macromolecule-Choose，选择好后点 select molecule，
它会自动加电荷等，点 OK 即可，完成后，会弹出保存窗口，直接保
存 pdbqt 格式即可

设置好后点 Done，然后点击 Ligand-Output-Save as PDBQT 即可
保存。

2.2.1 附：用 PyMol 导出 pdb 文件中的配体的方法
在界面上选中小分子，点击(sele)的 A-copy to object-new。红框内
的区域可以点击后将其对应的对象隐藏起来：
然后点击 Export Molecule-save 保存成 pdb 格式的文件。注意，这个
内置的配体也是没有加氢的，需要用 ADT 加氢。

3 对接
3.1 对接操作步骤
3.1.1 导入受体和配体
在 ADT 里面，点击 Grid-Macromolecule-Open 打开受体蛋白
点击 Grid-Set-Map-Types-Open Ligand 打开受体的 pdbqt 文件
3.1.2 定义对接盒子
点击 Grid-Grid Box 定义对接盒子
3.1.3 生成 config.txt 文件
点击 Docking-Output-Vina config 生成 config.txt 文件
3.1.4 启动对接

视频中的步骤：

1、导入protein蛋白质

2、删除水分子如果你的对接区域有水分子，会影响对接结果

pdq该格式省略了一切氢原子，包括游离的水分子都只保留了一个 O，所以后续需要加氢操作。

3、edit ->hydrogens->add->polar only 此时结构中发亮的就是氢键（加氢）

4、加电荷 edit -> charges->add kollman charges

5 报存 grid -> macromolecule ->choose->select

准备配体文件：

以sdf结尾的文件直接拖进 AUTO软件中会报错，需要转换成pdb文件

可以使用pymol可视化工具转换(注意：配体英文 ligend)

1、将该文件拖动到pymol中打开，file ->molecule

配体文件：

1、打开auto dock，将配体文件导入：

2、点击 Ligand（配体）->input->choose (这一步就是生成了配体文件)

3、点击 Ligand（配体）->output->save as pdbqt

接下来就可以进行分子对接：

1、将两个（受体和配体）pdpqt导入

2、重新选择蛋白质分子作为受体

点击NO

接下来设置对接盒子：

grid -> grid box

设置盒子位置（spacing设置为1）

然后 grid box 弹出设置中选择 file->output grid dimensions file（保存盒子设置）

保存：

新建config.txt:用于启动vina

receptor 蛋白质名（生成的蛋白质文件名）

ligand 配体名

center 和size在上一步的grid中有

receptor：指定受体分子的路径

ligand：配体分子的路径

center_x，center_y，center_z：搜索空间中心的坐标

size_x，size_y，size_z：指定搜索空间的大小。这里设置的大小基本就是把整个受体分子都包含了，属于blind docking。如何更准确确定结合口袋的位置，我们稍后再说。

energy_range：默认4，与最优结合模型相差的最大能量值，单位是kcal/mol。比方说，最优模型的能量计算出来是-8.5kcal/mol，那么vina也就最多计算到-4.5kcal/mol的模型就终止了，也就意味着这个值决定了生成模型的最大个数。

exhaustiveness：用来控制对接的细致程度，默认值是8. 大致与时间成正比。

num_modes：最多生成多少个模型。实际生成的模型数由num_modes和energy_range共同决定。

energy_range

 maximum energy difference between the best binding 
 mode and the worst one displayed (kcal/mol)

最后启动vina 进行分子对接:

在config目录中打开cmd->输入vina

其中：这条命令就是利用config.txt文件进行分子对接(cmd 必须在config文件目录下打开)

执行命令：

D:\Autodock\pdbqt>”D:\Vina\vina.exe” –receptor protein.pdbqt –ligand ligend.pdbqt –config config.txt –log log.txt –out output.pdbqt

“D:\Vina\vina.exe” –receptor selected_prediction_ready.pdbqt –ligand Conformer3D_CID_65536.pdbqt –config config.txt –log log.txt –out output.pdbqt

如果上述命令报错，一般是生成的config文件有问题：

正确的config内容如下：

执行完毕可以看到生成一个log文件

vina 中的affinity是亲合力结果排名

最后：

查看生成的模型：

将protein和output输出导入pymol

点击 all -> s查看表面结构

点击左右箭头查看不同的结构：

5.我们挑选第一个模型，看看结构方式是怎样的，见下图。很显然与真实的结合方式相差甚远，可以说是完全错误。

为什么会出现这种情况，很大程度上是因为search space太大，可能需要设置更大的exhaustiveness。

如果我们大致知道binding pocket在什么位置，那准确性应该会高不少，如何大致确定binding pocket的位置呢？我们接着试验。

可以通过实验的方式，比如某个点突变对结合或者活性影响非常大，那么大概率这个残基是结合口袋的一部分。

可以通过软件预测，比如蛋白与配体（底物）结合位点预测：https://zhanglab.ccmb.med.umich.edu/COACH/

再比如Discovery studio软件（专业版的），可以很方便的根据受体分子的表面形状来预测结合口袋位置。

口袋的坐标为：

34.3356，14.9412，26.9615

我们修改下对接参数，新的参数如下：

receptor = r.pdbqt

ligand = nap.pdbqt

center_x = 34.3356

center_y = 14.9412

center_z = 26.9615

size_x = 30.0

size_y = 30.0

size_z = 30.0

energy_range = 4

exhaustiveness = 10

num_modes = 10

最优结果与真实模型的RMSD为1.795埃，可以说非常精准了

比对结果如下：

Souce: 纽普生物 2019-05-07

PyMOL 相关操作：

1、导入蛋白质

先在NCBI子数据库structure检索所需要的蛋白结构，https://www.ncbi.nlm.nih.gov/structure/?term=
记录下该蛋白的PDB ID，然后打开PyMOL，命令行输入：

fetch 5ocn#foxn1
fetch 3uf0#
fetch 1si4#血红蛋白

去除水分子

remove solvent

分离得到蛋白

remove organic

分离配体：

../_images/splitlig2020-03-12_202822.573956.png

pymol教程：

http://pymol.chenzhaoqiang.com/intro/startManual.html

分子对接进阶教程：选定对接位点区域：

如果我们想要将配体和蛋白质受体的某几个位点部位对接：

1、标记这些点 select->select from string ，选择对应的molecule和链，以及residue（寻找的位点），点击add

2、此时，会出现currenr selection ，选择该列中 c，点击绿点，会将对应的分子三D化。

3、接下来设置盒子，spacing 设置为1（相当于比例尺），xyz一般设置为20-22

这样就可以了。

Python中collections.defaultdict()使用

1、以一个例子开始：统计一个列表里各单词重复次数

words = ['hello', 'world', 'nice', 'world']
counter = dict()
for kw in words:
    counter[kw] += 1

这样写肯定会报错的，因为各词的个数都没有初始值，引发KeyError

2、改进一下：加入if判断

words = ['hello', 'world', 'nice', 'world']
counter = dict()
for kw in words:
    if kw in words:
        counter[kw] += 1
    else:
        counter[kw] = 0

3、再改进：使用setdefault()方法设置默认值

words = ['hello', 'world', 'nice', 'world']
counter = dict()
for kw in words:
    counter.setdefault(kw, 0)
    counter[kw] += 1

setdefault()，需提供两个参数，第一个参数是键值，第二个参数是默认值，每次调用都有一个返回值，如果字典中不存在该键则返回默认值，如果存在该键则返回该值，利用返回值可再次修改代码。

4、接着改进
一种特殊类型的字典本身就保存了默认值defaultdict()，defaultdict类的初始化函数接受一个类型作为参数，当所访问的键不存在的时候，可以实例化一个值作为默认值。

from collections import defaultdict
dd = defaultdict(list)
defaultdict(<type 'list'>, {})
#给它赋值，同时也是读取
dd['hh']
defaultdict(<type 'list'>, {'hh': []})
dd['hh'].append('haha')
defaultdict(<type 'list'>, {'hh': ['haha']})

该类除了接受类型名称作为初始化函数的参数之外，还可以使用任何不带参数的可调用函数，到时该函数的返回结果作为默认值，这样使得默认值的取值更加灵活。

>>> from collections import defaultdict
>>> def zero():
...     return 0
...
>>> dd = defaultdict(zero)
>>> dd
defaultdict(<function zero at 0xb7ed2684>, {})
>>> dd['foo']
0
>>> dd
defaultdict(<function zero at 0xb7ed2684>, {'foo': 0})

最终代码：

from collections import defaultdict
words = ['hello', 'world', 'nice', 'world']
#使用lambda来定义简单的函数：函数返回值就是默认key的value值
counter = defaultdict(lambda: 0) 
for kw in words:
    counter[kw] += 1

python 字典树、前缀匹配

在python中可以用字典来实现字典树这一结构。

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.isEnd = '#'

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}  #如果没有这一字母则新建一个字典
            node = node[char]
        node[self.isEnd] = '#'   #加上结束符

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.isEnd in node  #如果没有# 说明只是前缀


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True



# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

2.采用defaultdict创建trie



from collections import defaultdict
from functools import reduce
TrieNode = lambda: defaultdict(TrieNode)
class Trie:
    def __init__(self):
        self.trie = TrieNode()
    def insert(self, word):
        reduce(dict.__getitem__, word, self.trie)['end'] = True
    def search(self, word):
        return reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).get('end', False)
    def startsWith(self, word):
        return bool(reduce(lambda d,k: d[k] if k in d else TrieNode(), word, self.trie).keys())

collections，解释是数据类型容器模块。这里面有一个collections.defaultdict()经常被用到

这里的defaultdict(function_factory)构建的是一个类似dictionary的对象，其中keys的值，自行确定赋值，但是values的类型，是function_factory的类实例，而且具有默认值。比如default(int)则创建一个类似dictionary对象，里面任何的values都是int的实例，而且就算是一个不存在的key, d[key] 也有一个默认值，这个默认值是int()的默认值0.

python 二分查找：bisect模块

bisect模块的源码：

"""Bisection algorithms."""

def insort_right(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

insort = insort_right   # backward compatibility

def bisect_right(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

bisect = bisect_right   # backward compatibility

def insort_left(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

# Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass

方法介绍

bisect模块采用经典的二分算法查找元素。模块提供下面几个方法：

bisect.bisect_left(a, x, lo=0, hi=len(a))：返回待插入值应该放置的位置下标，如果 a 中有和x相同的元素，就在返回该元素左边的下标，即在左边插入

定位x在序列a中的插入点，并保持原来的有序状态不变。参数lo和hi用于指定查找区间。如果x已经存在于a中，那么插入点在已存在元素的左边。函数的返回值是列表的整数下标。

bisect.bisect_right(a, x, lo=0, hi=len(a))

和上面的区别是插入点在右边。函数的返回值依然是一个列表下标整数。

bisect.bisect(a, x, lo=0, hi=len(a))

等同于bisect_right()。

注意，前面这三个方法都是获取插入位置，也就是列表的某个下标的，并不实际插入。但下面三个方法实际插入元素，没有返回值。

bisect.insort_left(a, x, lo=0, hi=len(a))

将x插入有序序列a内，并保持有序状态。相当于a.insert(bisect.bisect_left(a, x, lo, hi), x)。碰到相同的元素则插入到元素的左边。这个操作通常是 O(log n) 的时间复杂度。

bisect.insort_right(a, x, lo=0, hi=len(a))

同上，只不过碰到相同的元素则插入到元素的右边。

bisect.insort(a, x, lo=0, hi=len(a))

等同于insort_right()。

单调栈

单调栈实际上就是栈，只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序（如果新元素入栈不符合要求，则将之前的元素出栈，直到符合要求再入栈），使之形成单调递增/单调递减的一个栈。

单调递增栈：只有比栈顶小的才能入栈，否则就把栈顶出栈后，再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素的数。
单调递减栈：与单调递增栈相反。适用于求解第一个小于该位置元素的数。

如何判断

单调递增/递减栈是根据出栈后的顺序来决定的。例如，栈内顺序[1, 2, 6]，出栈后顺序[6, 2, 1]，这就是单调递减栈。

适用场景

单调栈一般用于解决第一个大于 xxx 或者第一个小于 xxx 这种题目。

int[] ans = new int[T.Length];
Stack<int> stack = new Stack<int>();

for(int i = 0; i < T.Length; i++) {
    while(stack.Count > 0 && T[i] > T[stack.Peek()]) {
        int curI = stack.Pop();
        ans[curI] = i - curI;
    }
    stack.Push(i);
}

python3中的heapq 堆

heapq实现了一个适合与Python的列表一起使用的最小堆排序算法。

满二叉树

树中除了叶子节点，每个节点都有两个子节点

完全二叉树

在满足满二叉树的性质后，最后一层的叶子节点均需在最左边

堆

堆是一种数据结构，它是一颗完全二叉树。最小堆则是在堆的基础增加了新的规则，它的根结点的值是最小的，而且它的任意结点的父结点的值都小于或者等于其左右结点的值。因为二进制堆可以使用有组织的列表或数组来表示，所以元素N的子元素位于位置2 * N + 1和2 * N + 2。这种布局使重新安排堆成为可能，因此在添加或删除项时不需要重新分配那么多内存
区分堆(heap)与栈(stack)：堆与二叉树有关，像一堆金字塔型泥沙；而栈像一个直立垃圾桶，一列下来。

最大堆

最大堆确保父堆大于或等于它的两个子堆。

最小堆

建堆：

heapify()

最小堆要求父堆小于或等于其子堆。Python的heapq模块实现了一个最小堆。

要创建一个堆，可以使用list来初始化为 [] ，或者你可以通过一个函数 heapify() ，来把一个list转换成堆。

定义了以下函数：heapq.heappush(heap, item)

将 item 的值加入 heap 中，保持堆的不变性。

heapq.heappop(heap)

弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出 IndexError 。使用 heap[0] ，可以只访问最小的元素而不弹出它。

heapq.heappushpop(heap, item)

将 item 放入堆中，然后弹出并返回 heap 的最小元素。该组合操作比先调用 heappush() 再调用 heappop() 运行起来更有效率。

heapq.heapify(x)

将list x 转换成堆，原地，线性时间内。heapq.heapreplace(heap, item)

弹出并返回 heap 中最小的一项，同时推入新的 item。堆的大小不变。如果堆为空则引发 IndexError。

这个单步骤操作比 heappop() 加 heappush() 更高效，并且在使用固定大小的堆时更为适宜。 pop/push 组合总是会从堆中返回一个元素并将其替换为 item。

返回的值可能会比添加的 item 更大。如果不希望如此，可考虑改用 heappushpop()。它的 push/pop 组合会返回两个值中较小的一个，将较大的值留在堆中。

heapq.nlargest(n, iterable, key=None)

从 iterable 所定义的数据集中返回前 n 个最大元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。等价于: sorted(iterable, key=key, reverse=True)[:n]。

heapq.nsmallest(n, iterable, key=None)

从 iterable 所定义的数据集中返回前 n 个最小元素组成的列表。如果提供了 key 则其应指定一个单参数的函数，用于从 iterable 的每个元素中提取比较键 (例如 key=str.lower)。等价于: sorted(iterable, key=key)[:n]。

python 全局变量 global 和 nonlocal

两个关键词都用于允许在一个局部作用域中使用外层的变量。

global 表示将变量声明为全局变量
nonlocal 表示将变量声明为外层变量（外层函数的局部变量，而且不能是全局变量）

python引用变量的顺序如下：

当前作用域局部变量
外层作用域变量
当前模块中的全局变量
python内置变量

比如：

a=1
def test(x):
   global x
   a=x
因为a外层变量是全局变量，所以要加global


def test2():
  a=1
  def test(x)
     nonlocal x
     a=x
因为a外层变量不是是全局变量，也是一个外层的局部变量，所以要加nonlocal

python 在新建一个变量时，默认作用域为当前局部作用域。如果不声明global or nonglocal，就认为是一个局部变量。

内部函数，不修改外层变量可以访问外层变量。

a = 1
def fun():
    print(a) # 在函数内部找不到对 a 的定义，则去外层查询。输出1。
fun()

内部函数，修改同名外层变量，则python会认为是定义了一个新的局部变量，与外层变量无关了。

a = 1
def fun():
a = 2 # 声明了一个局部变量，与外面等于1的那个a没有关系了
print(a) # 输出2
fun()
print(a) # 输出1

在内部函数修改同名全局变量之前调用变量名称，则引发Unbound-LocalError

a = 1
def fun():
    print(a) # 先引用
    a = 2 # 再修改
fun()

如果我们想要强制访问外层变量 a，便可以使用 global 关键字

a = 1
def fun():
    global a # a为全局变量
    print(a) # 输出1
    a = 2 # 改变的是全局变量，因此出了这个局部作用域，仍然有效
fun()
print(a) # 输出2
注意，这个时候，不要将 global 换为 nonlocal 关键字，不然会报错：

这是因为 nonlocal 表示外层变量，但是一旦外层变量是全局变量，则只能用 global。如果将这段代码全部放到一个函数中，则可以使用 nonlocal ：

def outer_fun():
a = 1
def fun():
nonlocal a # a为外层变量
print(a) # 输出1
a = 2
fun()
print(a) #输出2
outer_fun()

注意：可以发现，之前的将 global 换为 nonlocal 的报错，和这次的将 nonlocal 改为 global 的报错，错误类型是不同的。前者是 nonlocal a 这一行报错，后者是 print(a) 这一行报错。也就是说，在使用 nonlocal a 之前，必须保证外层的确已经定义过 a 了，但是在 global a 的时候，可以允许全局变量中还没有定义过a，可以留在后面定义。比如将 print(a) 之前加上对a的定义，便不会出错：

def outer_fun():
a = 1
def fun():
global a # a为全局变量，与上面等于1的 a 没有关系
a = 3 # 定义全局变量
print(a) # 输出3
a = 2
fun()
print(a) #输出1，局部变量
outer_fun()
print(a) # 输出2，全局变量

分治算法

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法在每一层递归上都有三个步骤：

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

可使用分治法求解的一些经典问题
（1）二分搜索（2）大整数乘法（3）Strassen矩阵乘法（4）棋盘覆盖（5）合并排序（6）快速排序（7）线性时间选择
（8）最接近点对问题（9）循环赛日程表（10）汉诺塔

例如：

求最大连续和：

给出一个长度为n的序列A1,A2,A3·····An，求最大连续和。如序列（6，-1 , 5, 4，-7), 该序列中的最大和是6 +（ – 1）+ 5 + 4 = 14。

思路分析：

基本思路是使用枚举法，三重嵌套循环，时间复杂度为n的三次方

我们来用分治法解决这个问题

1.划分问题：将序列分成元素个数尽可能相等的两半。

2.递归求解：分别求出位于左半和右半的最佳序列。

3.合并问题：求出起点位于左半，终点位于右半的最大连续和序列，和子问题最优解比较。

int maxsum(int l,int r){
if(l==r)return a[l];
int m=(l+r)/2;
int Max=max(maxsum(l,m),maxsum(m+1,r));//（分解）情况1：完全在左区间，或者完全在右区间

//（合并）情况2：横跨左右两个区间
int suml=a[m],t=0;
for(int i=m;i>=l;i--)
    suml=max(suml,t+=a[i]);
int sumr=a[m+1];t=0;
for(int i=m+1;i<=r;i++)
    sumr=max(sumr,t+=a[i]);

return max(Max,suml+sumr);//取两种情况中最大的

}

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2

解题思路

对于一个形如 x op y（op 为运算符，x 和 y 为数）的算式而言，它的结果组合取决于 x 和 y 的结果组合数，而 x 和 y 又可以写成形如 x op y 的算式。

因此，该问题的子问题就是 x op y 中的 x 和 y：以运算符分隔的左右两侧算式解。

然后我们来进行 分治算法三步走：

分解：按运算符分成左右两部分，分别求解
解决：实现一个递归函数，输入算式，返回算式解
合并：根据运算符合并左右两部分的解，得出最终解

class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:
        # 如果只有数字，直接返回
        if input.isdigit():
            return [int(input)]

        res = []
        for i, char in enumerate(input):
            if char in ['+', '-', '*']:
                # 1.分解：遇到运算符，计算左右两侧的结果集
                # 2.解决：diffWaysToCompute 递归函数求出子问题的解
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                # 3.合并：根据运算符合并子问题的解
                for l in left:
                    for r in right:
                        if char == '+':
                            res.append(l + r)
                        elif char == '-':
                            res.append(l - r)
                        else:
                            res.append(l * r)

        return res

leetcodeday138–复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-10⁴ <= Node.val <= 10⁴
Node.random 为 null 或指向链表中的节点。

关键:需要一个哈希表记录已经访问过的节点。如果节点访问过，则不用入队。

# @lc app=leetcode.cn id=138 lang=python3
#
# [138] 复制带随机指针的链表
#

# @lc code=start
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

from collections import deque
class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        
        if not head:
            return head

        visited = {}

        # 将题目给定的节点添加到队列
        queue = deque([head])
        # 克隆第一个节点并存储到哈希表中
        visited[head] = Node(head.val)

        # 广度优先搜索
        while queue:
            # 取出队列的头节点
            n = queue.popleft()
            # 遍历该节点的邻居
            neighbors=[n.next,n.random] 
            i=0
            for neighbor in neighbors:
                
                if  neighbor!=None and neighbor not in visited:
                    # 如果没有被访问过，就克隆并存储在哈希表中
                    visited[neighbor] = Node(neighbor.val)
                    # 将邻居节点加入队列中
                    queue.append(neighbor)
                    # 更新当前节点的邻居列表
                if neighbor!=None and i==0:
                    visited[n].next=visited[neighbor]
                if neighbor!=None and i==1:
                    visited[n].random=visited[neighbor]
                i=i+1


        return visited[head]
# @lc code=end

leetcodeday136 –只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

# @lc app=leetcode.cn id=136 lang=python3
#
# [136] 只出现一次的数字
#

# @lc code=start
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)
# @lc code=end

reduce() 函数会对参数序列中元素进行累积。

reduce(function, iterable[, initializer])

函数将一个数据集合（链表，元组等）中的所有数据进行下列操作：用传给 reduce 中的函数 function（有两个参数）先对集合中的第 1、2 个元素进行操作，得到的结果再与第三个数据用 function 函数运算，最后得到一个结果。

def add(x, y) :            # 两数相加
    return x + y
sum1 = reduce(add, [1,2,3,4,5])   # 计算列表和：1+2+3+4+5
sum2 = reduce(lambda x, y: x+y, [1,2,3,4,5])  # 使用 lambda 匿名函数
print(sum1)
print(sum2)