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

递归

LeetCode-1024. 视频拼接

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

LeetCode-234. 回文链表

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

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

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

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

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

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

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