INCOMING TRANSMISSION

236. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百 度百科中最近公共祖先的定义为：“对于有根树 \(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 = [1,2], p = 1, q = 2 输出：1 提示： 树中节点数目在范围 [2, 10 5 ] 内。 -10 9 <= Node.val <= 10 9 所有 Node.val...

二叉树结构 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None 递归 时间复杂度： \(O(n)\) ， \(n\) 为节点数，访问每个节点恰好一次。 空间复杂度：空间复杂度： \(O(h)\) ， \(h\) 为树的高度。最坏情况下需要空间 \(O(n)\) ，平均情况为 \(O(logn)\) 递归1: 二叉树遍历最易理解和实现版本 class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: if not root: return [] # 前序递归 return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) ...

48. 旋转图像 题目 给定一个 \(n × n\) 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]] 示例 2： 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]] 提示： n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 题解 这是一个经典的矩阵操作问题。要在原地（In-place）将图像顺时针旋转 90 度，我们可以利用矩阵的几何性质。 最直观且易于实现的方法是将...

分布式深度学习里的通信严重依赖于规则的集群通信，诸如 all-reduce, reduce-scatter, all-gather 等，因此，实现高度优化的集群通信，以及根据任务特点和通信拓扑选择合适的集群通信算法至关重要。 本文以数据并行经常使用的 all-reduce 为例来展示集群通信操作的数学性质。 All-reduce 在干什么？ 图 1：all-reduce 如图 1 所示，一共 4个设备，每个设备上有一个矩阵（为简单起见，我们特意让每一行就一个元素）， all-reduce 操作的目的是，让每个设备上的矩阵里的每一个位置的数值都是所有设备上对应位置的数值之和。 图2 如图 2 所示， all-reduce 可以通过 reduce-scatter 和 all-gather 这两个更基本的集群通信操作来实现。基于 ring 状通信可以高效的实现 reduce-scatter 和 all-gather，下面我们分别用示意图展示其过程。 reduce-scatter 的实现和性质 图 3：通过环状通信实现 reduce-scatter 从图 2...

一个在内存中运行的应用程序。每个进程都有自己独立的一块内存空间，一个进程可以有多个线程，比如在Windows系统中，一个运行的xx.exe就是一个进程。 线程 进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据。 与进程不同的是同类的多个线程共享进程的堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是在各个线程之间作切换工作时，负担要比进程小得多，也正因为如此，线程也被称为轻量级进程。 Java 程序天生就是多线程程序，我们可以通过 JMX 来看一下一个普通的 Java 程序有哪些线程，代码如下。 public class MultiThread { public static void main(String[] args) { // 获取 Java 线程管理 MXBean ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean(); // 不需要获取同步的 monitor 和...