关注Java领域相关技术 记录有趣的事情

广度优先搜索

LeetCode-1024. 视频拼接

问题地址 LeetCode每日一题/2020-10-24 LeetCode1024. 视频拼接 问题描述 规则 你将会获得一系列视频片段,这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。 视频片段 clips 都用区间进行表示:开始于 clips 并于 clips 结束。我们甚至可以对这些片段自由地再剪辑,例如片段  可以剪切成  +  +  三部分。 我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段()。返回所需片段的最小数目,如果无法完成该任务,则返回 -1 。 示例 示例1 输入:clips = ,,,,,], T = 10…
US-B.Ralph
4 months ago

LeetCode-116. 填充每个节点的下一个右侧节点指针

问题地址 LeetCode每日一题/2020-10-15 LeetCode116. 填充每个节点的下一个右侧节点指针 问题描述 规则 给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下: struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。 初始状态下,所有 next 指针都被设置为 NULL。 进阶 你只能使用常量级额外空间。 使用递归解题也符合要求,本题中递归…
US-B.Ralph
4 months ago

LeetCode-834. 树中距离之和

问题地址 LeetCode每日一题/2020-10-06 LeetCode834. 树中距离之和 问题描述 规则 给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。 第 i 条边连接节点 edges 和 edges 。 返回一个表示节点 i 与其他所有节点距离之和的列表 ans。 示例 示例1 输入: N = 6, edges = ,,,,] 输出: 解释: 如下为给定的树的示意图: 0 / \ 1 2 /|\ 3 4 5 我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) …
US-B.Ralph
4 months ago

LeetCode-145. 二叉树的后序遍历

问题地址 LeetCode每日一题/2020-09-29 LeetCode145. 二叉树的后序遍历 问题描述 规则 给定一个二叉树,返回它的 *后序 遍历。 示例 输入: 1 \ 2 / 3 输出: 进阶 递归算法很简单,你可以通过迭代算法完成吗? 解析 解题思路 后序遍历:是按照访问左右根的顺序遍历这棵树,而在访问左子树或者右子树的时候,我们按照同样的方式遍历,直到遍历完整棵树。整个遍历过程天然具有递归的性质。 递归遍历树的时候隐式的维护一个栈,我们使用迭代的方法遍历树,需要自己维护栈; 下面介绍一种方法标记法,针对树的前、中、后序遍历可以写统一模板的代码; 在使用栈时,无法同时处理访问节…
US-B.Ralph
5 months ago

LeetCode-117. 填充每个节点的下一个右侧节点指针 II

问题地址 LeetCode每日一题/2020-09-28 LeetCode117. 填充每个节点的下一个右侧节点指针 II 问题描述 规则 给定一个二叉树 struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。 初始状态下,所有 next 指针都被设置为 NULL。 进阶 你只能使用常量级额外空间。 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。 示例 输入:root = …
US-B.Ralph
5 months ago

LeetCode-113. 路径总和 II

问题地址 LeetCode每日一题/2020-09-26 LeetCode113. 路径总和 II 问题描述 规则 给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 注意 你可以假设树中没有重复的元素。 示例 示例一: 给定如下二叉树,以及目标和 sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: , ] 解析 解题思路 从根节点开始遍历每一条路径,当遍历到叶子节点且该路径节点之和等于sum则将其添加到结果集中; 数据操作分析 遍历整棵树 当节点为空,直接返回; …
US-B.Ralph
5 months ago

LeetCode-617. 合并二叉树

问题地址 LeetCode每日一题/2020-09-23 LeetCode617. 合并二叉树 问题描述 规则 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。 示例 示例一: 输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / \ 4 5 / \ \ 5 4 7 注意 合并必须从两个树的根节点开始。 解析 解题思路 题目要…
US-B.Ralph
5 months ago

LeetCode-404. 左叶子之和

问题地址 LeetCode每日一题/2020-09-19 LeetCode404. 左叶子之和 问题描述 规则 计算给定二叉树的所有左叶子之和。 示例 示例1 3 / \ 9 20 / \ 15 7 在这个二叉树中,有两个左叶子,分别是 9 和 15,所以返回 24 解析 解题思路 左叶子的判定条件 它是某个节点的左子节点; 它是一个叶子结点; 因此我们遍历整棵树,当我们遍历到某个节点 $\textit{node}$ 时,如果它的左子节点是一个叶子结点,那么就将它的左子节点的值累加计入答案。 数据操作分析 遍历整棵树,在遍历的过程中,判定某个节点是否满足左叶子的条件,判断条件: 左子节点; 叶…
US-B.Ralph
5 months ago

LeetCode-79. 单词搜索

问题地址 LeetCode每日一题/2020-09-13 LeetCode79. 单词搜索 问题描述 规则 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 示例一: board = , , ] 给定 word = "ABCCED", 返回 true 给定 word = "SEE", 返回 true 给定 word = "ABCB", 返回 false 提示 $board$ 和 $word$ 中只包含大写和小写英文字母。 $1 <=…
US-B.Ralph
5 months ago

LeetCode-637. 二叉树的层平均值

问题地址 LeetCode每日一题/2020-09-12 LeetCode637. 二叉树的层平均值 问题描述 规则 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。 示例 示例一: 输入: 3 / \ 9 20 / \ 15 7 输出: 解释: 第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 。 提示 节点值的范围在32位有符号整数范围内。 解析 解题思路 计算每一层的平均值,需要在搜索中存储每一层数据的和、每一层元素的个数; 遍历结束后每一层的平均值=每一层数据的和/每一层元素的个数; 数据操作分析 计算每一层的平均值,需要在搜索中存储每一层数据…
US-B.Ralph
5 months ago