0%

空间换时间

使用一个 map 完成有序地映射,从而在每一层根据出发地选取机票时,都能够优先选取目的地字典序最小的机票,此处本质上是一个图,并且题设告知存在路径。使用一个 unordered_map<string,map<string,int>> tic_map 去进行记录,本质上是 unordered_map<出发地,map<目的地,机票数>> tic_map

那么首先在结果数组 res 中加入一个 JFK 作为出发地,那么在每一层递归中只需要在 tic_map[res.back()] 中选取机票,此时优先选到的机票一定是字典序在前的。那么在每次优先选取最优的基础上,那么就一定能够找到最有路径。在找到最有路径后递归结束。

阅读全文 »

1.2 利用完全二叉树的性质实现

希望能够在小于 的时间复杂度内实现。(换句话说:能否在 的时间复杂度内实现。)重点在于最后一层,在前面层都是一个满二叉树。

从深度的角度出发计算:充分利用二叉树的性质,分别计算左右子树的深度。

  • 若是左右子树的深度相等,那么左子树一定是满二叉树,再处理右子树。
  • 不相等只可能是左大于右,那么右子树是满二叉树,此时在递归处理右子树。

对于完全二叉树存在如下性质:完全二叉树的子树也是完全二叉树。

针对上述性质可以推出一个特殊的求解树的深度的方式:从根节点开始不断向左查找即可得到完全二叉树的深度。

阅读全文 »

1.2 DFS自底向上搜索

本质思想就是先判断子树是否是平衡二叉树,当子树是一颗平衡二叉树时,希望能够返回树的深度(如何返回二叉树的深度)。若是子树不平衡,那么整个树一定都是不平衡的。

关于深度的计算:当前节点为空时,直接返回0值,当前节点非空,则需要判断,需要理解递归的思想,在当前节点的两颗子树都是平衡二叉树时,只需要返回max深度+1即可。

阅读全文 »

1.2 单调栈实现

将构造的过程转化为基于节点数和数组实现:

  1. 初始时,我们只有一个根节点,其中存储了整个数组;
  2. 在每一步操作中,我们可以「任选」一个存储了超过一个数的节点,找出其中的最大值并存储在该节点。最大值左侧的数组部分下放到该节点的左子节点,右侧的数组部分下放到该节点的右子节点;
  3. 如果所有的节点都恰好存储了一个数,那么构造结束。

此处,在题解中提出,在进行树的构造过程中,并不需要按照最大二叉树的定义进行构造,实际上在上述的定义中,存在一个特性:对于最大的节点一定是根节点,第二大的节点则一定是根节点的左/右孩子,但是对于第三大的节点就存在不确定性。

构造方式:每次选择数组中值最大的那个节点进行构造。这样一来,我们就可以保证按照数组中元素降序排序的顺序依次构造每个节点。当选择节点中的数组最大值为nums[i]时,说明大于nums[i]的元素已经全部构造,小于的元素还没有构造。

在最终构造出的树上,以nums[i] 为根节点的子树,在原数组中对应的区间,左边界为nums[i] 左侧第一个比它大的元素所在的位置,右边界为nums[i] 右侧第一个比它大的元素所在的位置。左右边界均为开边界。如果某一侧边界不存在,则那一侧边界为数组的边界。如果两侧边界均不存在,说明其为最大值,即根节点。

并且nums[i] 的父结点是两个边界中较小的那个元素对应的节点

此处的思想就是,先找到相应的元素,然后确定当前元素在原来序列中的划分边界,并且有nums[i] 的父结点是两个边界中较小的那个元素对应的节点(左右孩子的问题则需要根据边界的位置来进行确定)

阅读全文 »

双hash+回溯递归

本题在46.全排列问题的基础之上发生了改变,主要的不同之处在于:给定的序列中包含重复的元素,那么在全排列的过程中就会导致重复的结果,例如 nums=[1,1,2] 完全按照排列问题进行处理将会出现重复结果: [1,2,1][1,1,2] ,那么在于全排列问题的基础上此处的重点就在于处理重复的结果。

那么基本思路还是:递归实现,每一层选取一个元素作为排列中的第 cur 个元素,当 cur=nums.size() 选取结束,将排列加入到结果集中。

此处采取双hash的方式进行处理,创建两个hash表:

  1. used[8] 是一个全局变量,记录的是整个序列中那些位置的的元素已经使用了 used[i]=true 代表 nums[i] 处的元素已经在前层使用了。那么在某层选取 nums[i] 后需要对 used[i] 进行标记,在递归返回后需要进行回溯,取消标记( nums 的最大长度为8,定长数组即可)
  2. curUsed[21] 是递归函数中的局部变量,记录的是在当前层中那些元素值已经使用过了, curUed[i]=true 表示在当前层元素值 i 已经使用过了,假设当前的递归层数为第 j 层,那么表示在排列的第 j 个位置已经使用过元素 i ,那么在当前层的后续选择中遇到元素 i 就需要进行跳过
阅读全文 »

排列问题和组合问题类似,都是从数组中选取全部的元素,但是排列问题相较于组合对顺序敏感,也就是对于 [1,2][2,1] 是两个不同的结果,因此在每一层进行元素的选取时,都从 i=0 开始选取,但是需要避免选择前层已经选取过的元素,使用一个hash去记录前层那些元素已经选取过了。在题设中,已知: ,因此只需要个长度为21的bool数组作为hash即可。

阅读全文 »

本题和子集问题90.子集II存在类似,在给定的数组 nums 中存在重复元素,那么在寻找递增序列的过程中就存在着重复的递增子序列问题。

例如对于 nums=[4,7,4,6] 那么直接去寻找就会得到两个相同的递增子序列 [4,6] ,需要在结果中去掉这种重复。

但是本题相较于子集问题的不同之处在于:寻找的是当前序列的子序列,也就是元素的相对位置要和原序列中保持一致。例如 [4,4,3,1] 那么相应的递增子序列就只有 [4,4] ,因此是不能对元素进行排序的。

逐层选取的思想:本题的情形,可以使用一棵树来进行描述。树的第一层选取子序列中的第一个元素,树的第二层选取子序列的第二个元素,那么以序列 [4,7,6,7] 为例,选取元素构造树的过程为:

阅读全文 »

transformer的自注意力机制解读

本质上是对RNN无法实现并行计算的一种改进(并且这种改进本质上就是通过简化的举证乘法来实现的)

使用RNN(单向或者双向)去处理sepuence—to—sepuence时,对于输入序列 输出为序列 ,在双向RNN的情况在,对于每一个输出序列中的元素 都是和全部的 相关的,但是对于RNN中存在一个问题,不便于实现并行优化。要计算 必须逐个处理

RNN

阅读全文 »