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

递归

LeetCode-1024. 视频拼接

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

LeetCode-234. 回文链表

问题地址 LeetCode每日一题/2020-10-23 LeetCode234. 回文链表 问题描述 规则 请判断一个链表是否为回文链表。 示例 示例1 输入: 1->2 输出: false 示例2 输入: 1->2->2->1 输出: true 进阶 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 思路分析 判断一个链表是否为回文链表，只需要使用两个指针，一个正向移动，一个从后往前移动，移动的过程中比较两个指针所指向节点的值即可。因为题目给定的是单向链表，只能从前往后访问链表元素，所以我们可以使用如下方法： 方法一：使用线性表存储链表元素，遍历线性…
1
US-B.Ralph
US-B.Ralph
2 years ago

LeetCode-143. 重排链表

问题地址 LeetCode每日一题/2020-10-20 LeetCode143. 重排链表 问题描述 规则 给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 示例 示例1 给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例2 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3. 解析 解题思路 最直观的想法是使用线性表存…
1
US-B.Ralph
US-B.Ralph
2 years ago

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

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

LeetCode-24. 两两交换链表中的节点

问题地址 LeetCode每日一题/2020-10-13 LeetCode24. 两两交换链表中的节点 问题描述 规则 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换 示例 给定 1->2->3->4, 你应该返回 2->1->4->3. 解析 解题思路 单链表只能指向下一个节点。这里使用虚拟头节点进行操作； 数据操作分析 操作步骤见下图 复杂度分析 时间复杂度 空间复杂度 编码实现 public class LeetCode0024_SwapNodesInPairs { public…
US-B.Ralph
US-B.Ralph
2 years ago

LeetCode-530. 二叉搜索树的最小绝对差

问题地址 LeetCode每日一题/2020-10-12 LeetCode530. 二叉搜索树的最小绝对差 问题描述 规则 给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。 示例 示例1 输入： 1 \ 3 / 2 输出：1 解释 最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。 提示： 树中至少有 2 个节点。 本题与 783 相同 解析 解题思路 我们都知道二叉搜索树左子树不大于根节点，右子树不小于根节点。我们采用中序遍历的处理这个问题； 方法一：先利用一次中序遍历将值保存在一个数组中再进行遍历求解； 方法二：在中序遍历的过程中…
US-B.Ralph
US-B.Ralph
2 years 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
US-B.Ralph
2 years ago

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

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

LeetCode-235. 二叉搜索树的最近公共祖先

问题地址 LeetCode每日一题/2020-09-27 LeetCode235. 二叉搜索树的最近公共祖先 问题描述 规则 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科 中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树:  root =  示例 示例一： 输入: root = , p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例二： 输入: root = , p …
US-B.Ralph
US-B.Ralph
3 years 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
US-B.Ralph
3 years ago