mq002.合并两个有序数组
题目链接
此题与lc088相同。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
t = m + n - 1
i, j = m - 1, n - 1
while i >= 0 and j >= 0:
if nums1[i] &...
mq001.最大子序和
题目链接
这题我做过，就是lc053。首先讲一下第一种做法是用动态规划法，这样的时间复杂度是O（N），该实现如下所示。这个实现的空间复杂度是O（N），就如同典型的一维dp一样，可以将空间优化到O（1）。一种做法是用其他变量来暂时保存某个时刻的最大值，或者我们注意到dp的过程中只与res[i-1]和nums[i]有关，我们可以用nums作为dp数组这样呀也能实现空间复杂度的优化。另外，这题也可以用分治的思想去解决但是时间复杂度为O（NlogN），空间复杂度为O（logN），都不如动态规划来的好所以就不写了。
class Solution:
def maxSubArray1(self, nums) -> int:
res = [0]*len(nums)
...
lc215.数组中的第K大个最大元素
题目链接
此题与jz040有点相似，不过一个是输出前K小的所有数字，这个是只输出第K大的元素。这个算法的时间复杂度是O（N），空间复杂度因为是原地排序所以是O（1）。
import random
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
t = len(nums)-k
l, r = 0, len(nums)-1
while True:
index = self.qsort_rec(nums, l, r)
if index == t:
r...
jz068II.二叉树的最近公共祖先
题目链接
对于这个题我们可以用深度优先遍历分别找到从根节点到两个所比价的节点的路径，然后比较得到的路径，求出最先不同的那个节点之前的那个节点即可。这个算法的时间复杂度是O（N），空间复杂度最差情况下是O（N）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNo...
lc008.把字符串转换成整数
题目链接
此题与jz067一样。这个算法的时间复杂度是O（N），空间复杂度是O（1）。
class Solution:
def strToInt(self, str: str) -> int:
res, i, sign, length = 0, 0, 1, len(str)
int_max, int_min, bndry = 2 ** 31 - 1, -2 ** 31, 2 ** 31 // 10
if not str: return 0 # 空字符串，提前返回
while str[i] == ' ':
i += 1
if i == leng...
jz068I.二叉搜索树的最低公共祖先
题目链接
对于二叉搜索树来说，位于左子树到节点都比父节点小，位于右子树的的节点都比父节点大，我们只需要从树的根结点开始和两个输入的节点进行比较。如果当前节点的值比两个节点的值都大，那么最低的共同父节点一定在当前节点的左子树中，于是下一步遍历当前节点的左子节点。反之，下一步遍历当前节点的右子节点。这样，在树中从上到下找到的第一个在两个输入节点的值之间的节点就是最低的公共祖先。1中的实现的时间复杂度是O（N），空间复杂度是O（N）。2中的实现时间复杂度不变，但是空间复杂度下降为了O（1）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self....
jz067.把字符串转换成整数
题目链接
这个题不难但是要排除各种特殊情况，比如空字符串，数字大于或小于特定值等。如一所示是我丑陋的实现，注意从str转换到int既然不能用int()那么可以用ord(s)去和ord(“0”)去做差。这个算法的时间复杂度是O（N），空间复杂度是O（N）。如2是别人优雅的实现，因为去除了strip()函数所以空间复杂度也降到了O（1）。
class Solution:
def strToInt1(self, s: str) -> int:
s = s.strip(" ")
intmax, intmin = 2**31 - 1, -2**31
if not s:
return 0
if...
jz066.构建乘积数组
题目链接
对于所求B[i] = A[0] x A[1] x … x A[i-1] x A[i+1] x … x A[n-1]，我们可以将其看成C[i] = A[0] x A[1] x … x A[i-1] 和 D[i] = A[i+1] x … x A[n-1]两部分的乘积，对于C和D我们可以用循环依次计算出来。这个算法的时间复杂度是O（N），空间复杂度是O（N）。第二种是别人的实现，比较巧妙地节省了空间，并且由于b这个数组作为返回值不计入空间复杂度的计算（？），所以空间复杂为O（1）。
class Solution:
def constructArr1(self, a: List[int]) -> List[int]:
C, D = [1], [1]...
NeurIPS 2020 NLP Papers
ConvBERT: Improving BERT with Span-based Dynamic Convolution
关键词：
摘要：
2.
TSPNet: Hierarchical Feature Learning via Temporal Semantic Pyramid for Sign Language Translation
Extending a Parser to Distant Domains Using a Few Dozen Partially Annotated Examples
摘要：我们重新审视神经时代语法分析器的领域自适应。首先，我们表明，当目标域和源域在句法上相似时，词表示的最新进展大大减少了域适应的需求。作为证据，我们在单独的Wall Street Journal数据上训练的分析器在Brown语料库上取得了高于90%的$F_1$分数。对于句法上距离更远的域，我们提供了一个简单的方式即只使用几十个部分注释来调整分析器。例如，我们仅用60个训练样本将留出集中的无错误几何域分析器的$F_1$从45%提高到了73%。在这个过程中，我们展示了一个在Wall Street Journal测试集上达到了94.3%的$F_1$分数的SOTA模型，这个模型的表现相比于之前SOTA模型的92.6%提高了1.7%的绝对值。
260 post articles, 26 pages.