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

动态规划

LeetCode-1024. 视频拼接

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

LeetCode-416. 分割等和子集

问题地址 LeetCode每日一题/2020-10-11 LeetCode416. 分割等和子集 问题描述 规则 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 示例1 输入: 输出: true 解释: 数组可以分割成 和 . 示例2 输入: 输出: false 解释: 数组不能分割成两个元素和相等的子集. 解析 解题思路 数据操作分析 复杂度分析 时间复杂度 空间复杂度 编码实现 public class LeetCode0416_PartitionEqualSubset…
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-968. 监控二叉树

问题地址 LeetCode每日一题/2020-09-22 LeetCode968. 监控二叉树 问题描述 规则 给定一个二叉树,我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 示例一: 输入: 输出:1 解释:如图所示,一台摄像头足以监控所有节点。 示例二: 输入: 输出:2 解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。 提示 给定树的节点数的范围是 。 每个节点的值都是 0。 解析 解题思路 根据题意,我们给节点定义一些状态: 0:空白节点; 1:被监控节点; 2…
US-B.Ralph
7 months ago

LeetCode-39. 组合总和

问题地址 LeetCode每日一题/2020-09-09 LeetCode39. 组合总和 问题描述 规则 给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明 所有数字(包括 target)都是正整数。 解集不能包含重复的组合。 示例 示例一: 输入:candidates = , target = 7, 所求解集为: , ] 示例二: 输入:candidates = , target = 8, 所求解集为: , , ] 提示 $1 &l…
US-B.Ralph
8 months ago

LeetCode-486. 预测赢家

问题地址 LeetCode每日一题/2020-09-01 LeetCode486. 预测赢家 问题描述 规则 给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数,随后玩家 2 继续从剩余数组任意一端拿取分数,然后玩家 1 拿,…… 。每次一个玩家只能拿取一个分数,分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。 给定一个表示分数的数组,预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。 示例1 输入: 输出:False 解释:一开始,玩家1可以从1和2中进行选择。 如果他选择 2(或者 1 ),那么玩家 2 可以…
US-B.Ralph
8 months ago

LeetCode-647. 回文子串

问题地址 LeetCode每日一题/2020-08-19 LeetCode647. 回文子串 问题描述 规则 给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 示例1 输入:"abc" 输出:3 解释:三个回文子串: "a", "b", "c" 示例2 输入:"aaa" 输出:6 解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 提示 输入的字符串长度不会超过 1000 。 解析 解题思路 回文子串是一个正读和反读都一样的字符串,比如“level”或者“noon”…
US-B.Ralph
8 months ago