lc057.另一个树的子树
题目链接
啊这个题如果用暴力做法的话就是枚举s中的节点然后和t的根结点比较，找到后再进行两棵树的遍历去判断是否相等。如1所示，这样做的时间复杂度为O(
s
x
t
)，空间复杂度为O(max{d_s, d_t})，d表示树的深度。
另外一种方法是在DFS序列上做串匹配。我们首先要了解一个小套路：一棵子树上的点在DFS序列（即先序遍历）中是连续的。了解了这个小套路之后，我们可以确定这个问题的方向就是：把s和t先转换成DFS序，然后看t的DFS序是否是s的DFS序的子串。这样做一定正确吗，其实不一定，假设s有两个节点，1是根，2是左孩子，而t也有两个节点，1也是...
pp003.XLNet: Generalized Autoregressive Pretraining for Language Understanding
链接
关键词：预训练模型，自回归语言模型，去噪自编码，Transformer-XL，PLM
摘要：借助于对双向上下文进行建模的能力，基于去噪自编码的预训练模型如BERT相比于基于自回归语言模型的预训练模型拥有更好的性能。但是，依赖于用掩码破坏输入，BERT忽略了被遮盖位置的词的依赖关系并因此遭受了预训练-微调差异的困扰。鉴于这些优缺点，我们提出XLNet，一个广义的自回归预训练方法，该方法（1）通过最大化所有因子分解顺序的排列的期望似然来实现双向上下文学习，并且（2）克服了BERT由于其自回归形式所带来的许多限制。另外，XLNet将最先进的自回归模型Transfomer-XL中的思想整合到了预训练中。根据经验，在可比较的实验设置下，XLNet在多达20个任务上超过了BERT，并且通...
mq043.二叉树的直径
题目链接
一条路径的长度为该路径经过的节点数减一，所以求直径等效于求路径经过的节点数的最大值减一。任意一条路径都可以看作由某个节点为起点，从其左子节点和右子节点向下遍历的路径拼接得到。假设我们知道对于某节点的左子节点向下遍历经过最多的节点数L和其右子节点向下遍历经过最多的节点数R，那么以该节点为起点的路径经过节点数的最大值即为L+R+1。
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# ...
lc543.二叉树的直径
题目链接
一条路径的长度为该路径经过的节点数减一，所以求直径等效于求路径经过的节点数的最大值减一。任意一条路径都可以看作由某个节点为起点，从其左子节点和右子节点向下遍历的路径拼接得到。假设我们知道对于某节点的左子节点向下遍历经过最多的节点数L和其右子节点向下遍历经过最多的节点数R，那么以该节点为起点的路径经过节点数的最大值即为L+R+1。
这个算法的时间复杂度是O（N），空间复杂度是O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# s...
pp002.Task-Oriented Dialogue as Dataflow Synthesis
链接
关键词：语义解析
摘要： 我们描述了一个学习任务导向的对话的途径，其中对话的状态表示成数据流图。对话代理将每个用户话语映射成一个拓展此图的程序。程序包括以供参考和修订的元计算运算符，这些运算符可重用先前回合中的数据流片段。我们基于图的状态使得能够表达和操纵复杂的用户意图，而显示的元计算使得这些意图更易于学习模型进行预测。我们引入一个新的数据集：SMCalFlow，其中包含着关于事件，天气，地点和人物的复杂对话。实验表明，数据流图和元计算可以在这些自然对话显著提高可表示性和可预测性。在MultiWOZ数据集上的额外实验显示，我们的数据流表示使得一个现有的sequence-to-sequence模型能够与现存的最佳的特定任务跟踪模型相匹敌。SMCalFlow数据集，重现实验的代码...
mq041.二叉树的右视图
题目链接
对于这个题有两种思路，我之前的想法是宽度优先遍历既层序遍历二叉树，每一层的最后一个节点就是所求的值，但是有一种更省空间的方法就是记录下每个节点的深度并且用深度作为键节点的值作为值建立字典并同时更新，因为最右边的节点最后才会遍历到所以字典里最后保存的会是最右边的节点的值（如1）。另外一种思路用深度优先遍历并且先遍历右子节点（如2），这样做的结果就是对于某个深度的最开始遇到的节点才是需要记录的值。这两个算法的时间复杂度都是O（N），空间复杂度都是O（N）。
class Solution:
def rightSideView1(self, root: TreeNode) -> List[int]:
most_right = {}
m...
lc199.二叉树的右视图
题目链接
对于这个题有两种思路，我之前的想法是宽度优先遍历既层序遍历二叉树，每一层的最后一个节点就是所求的值，但是有一种更省空间的方法就是记录下每个节点的深度并且用深度作为键节点的值作为值建立字典并同时更新，因为最右边的节点最后才会遍历到所以字典里最后保存的会是最右边的节点的值（如1）。另外一种思路用深度优先遍历并且先遍历右子节点（如2），这样做的结果就是对于某个深度的最开始遇到的节点才是需要记录的值。这两个算法的时间复杂度都是O（N），空间复杂度都是O（N）。
class Solution:
def rightSideView1(self, root: TreeNode) -> List[int]:
most_right = {}
m...
mq061.编辑距离
题目链接
之前做过了，用二维dp做，时间和空间复杂度都是O（MN）。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
l1, l2 = len(word1), len(word2)
dp = [[0]*(l2+1) for x in range(l1+1)]
for x in range(l1+1):
dp[x][0] = x
for y in range(l2+1):
dp[0][y] = y
for x in range(1, l1+1):
...
260 post articles, 26 pages.