INCOMING TRANSMISSION

题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例 1： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3： 输入：root...

题目 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2. Example: [代码] Constraints: 10^9 <= nums1[i], nums2[i] <...

DFS

1. explode hive wiki对于expolde的解释如下： explode() takes in an array (or a map) as an input and outputs the elements of the array (map) as separate rows. UDTFs can be used in the SELECT expression list and as a part of LATERAL VIEW. As an example of using explode() in the SELECT expression list, consider a table named myTable that has a single column (m...

问题表示 有很多概率问题，尤其是独立重复实验问题，如果用生成函数的方法来做，会显得特别方便。本文要讲的“随机游走”问题便是其中一例，它又被形象地叫做“醉汉问题”，其本质上是一个二项分布，但是由于取了极限，出现了很多新的性质和应用。我们先考虑如下问题： 考虑实数轴上的一个粒子，在 t=0 时刻它位于原点，每过一秒，它要不向前移动一格（+1），要不就向后移动一格（1），问 n 秒后它所处位置的概率分布。 不难发现，这个问题跟二项分布是雷同的。如果把这个粒子形象比喻成一个“喝醉酒的人”，那么上面的走法就类似于一个完全不省人事的醉汉走路问题了。（当然，醉汉是在三维空间走路的，这里简单起见，只描述了一维...

通过卷积和池化等技术可以将图像进行降维，因此，一些研究人员也想办法恢复原分辨率大小的图像，特别是在语义分割领域应用很成熟。 1、Upsampling（上采样）[没有学习过程] 在FCN、Unet等网络结构中，涉及到了上采样。上采样概念：上采样指的是任何可以让图像变成更高分辨率的技术。最简单的方式是重采样和插值：将输入图片进行rescale到一个想要的尺寸，而且计算每个点的像素点，使用如双线性插值等插值方法对其余点进行插值来完成上采样过程。 在PyTorch中，上采样的层被封装在torch.nn中的Vision Layers里面，一共有4种： PixelShuffle Upsample UpsamplingNearest2d UpsamplingBilinear2d 0）PixelShuffl...

计算几何（Computational Geometry），是一系列使用计算机解决几何问题的算法。与解析几何相比，计算几何更适合计算机运算，精度较高，运算速度较快，并且易于编写。 浮点误差 程序设计中，考虑到浮点数 double 有精度误差，在比较时，通常允许一定的误差，即对于两个数 a 、 b ，如果 [Math] ，则认为 a=b 。一般根据题目要求， d （代码中命名为 EPS）取一个较小值，如 10^{8} 。 [代码] 向量 向量（vector）是一个有大小和方向的量，在几何中，它被表示为带箭头的线段。向量可以用起点和终点的坐标来表示 —— 从点 A到点B 的向量表示为 [Math] 。 向量的书写，两个大写字母上加一个箭头（表示方向） [Math] 向量没有位置，即向量可以在平面内...

问题定义 多元二次多项式，维度为 n ，那么可以用以下公式描述该函数： [Formula] 其中 a_{i,j} 为二次项系数，共有 n^2 项， 1≤i,j≤n ，且所有的 a 不全为0，即 ∃a_{i,j}≠0 ; b_k 为一次项系数，共 n 项， 1≤k≤n ; c 为常数项。 记 f(x)=[x_1,x_2,...,x_n]^T ，则上述函数可以写作二次型的形式： 转化过程中A,b满足： A 为n阶对称方阵， A_{i,j}=a_{i,j} 因为 ∃a_{i,j}≠0 ，A不为零矩阵 b_i=b_i 为了后续计算简便，我们将二次型稍作改动： [Formula] 我们的目标就是寻找该函...

基本概念 方向导数：是一个数；反映的是 f(x,y) 在 P_0 点沿方向 v 的变化率。 偏导数：是多个数（每元有一个）；是指多元函数沿坐标轴方向的方向导数，因此二元函数就有两个偏导数。 偏导函数：是一个函数；是一个关于点的偏导数的函数。 梯度：是一个向量；每个元素为函数对一元变量的偏导数；它既有大小（其大小为最大方向导数），也有方向。 方向导数 反映的是 f(x,y) 在 P_0 点沿方向 v 的变化率。 例子如下： 题目 设二元函数 f(x, y) = x^2 + y^2 ，分别计算此函数在点 (1, 2) 沿方向 w=\{3, 4\} 与方向 u=\{1, 0\} 的方向导数。 解： ...

题目 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。 如果数组元素个数小于 2，则返回 0。 Example 1: [代码] 解题思路：如果进行排序，这里会超时。采用桶排序 排序算法 的思想，可以在线性时间解决。 1. 首先建立桶，每个桶中只需要存放这个桶中元素的最大值和最小值。 1. 我们期望将数组中的各个数等距离分配，也就是每个桶的长度相同，也就是对于所有桶来说，桶内最大值减去桶内最小值都是一样的。可以当成公式来记。 1. 确定桶的数量，最后的加一保证了数组的最大值也能分到一个桶。为什么需要这样规定桶的尺寸呢？因为这样可以让最大的间距的两个元素在两个不同的桶中。可以证明一下，因为我们用元素范围之差除以元素个数，所以桶的尺寸就是平均的元素间距，显然最大间距的两个元素不可能...

1. 可以重复选取 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 画出树状搜索图如下， 为了去除重复的情况， 我们需要按照某种顺序搜索，具体做法是：每一次搜索的时候，设置下一轮搜索的起点 [代码] 2. 不能被重复选取 与上面的区别在于 1. index每次不要重复搜索，而是去寻找下一个 1. 排除重复的元素 [代码]