TypechoJoeTheme
2023-09-21
2023-09-20
题目给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。示例 1：输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8输出：3解释：和等于 8 的路径有 3 条，如图所示。示例 2：输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：3两次深度优先搜索一次dfs是只能从一个头结点往下搜索符合情况，但是这道题路径不需要从根节点开始，也不需要在叶子节点结束，可以考虑使用两次dfs两次dfs无非就是让每个节点都当一次头结点，然后以他们为根向下搜索可行情况，但是时间复杂度也会上升到O(N2)代码如下：class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (...
2023-09-20
2023-09-19
2023-09-19
题目：给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。示例 1:输入: intervals = [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后，剩下的区间没有重叠。示例 2:输入: intervals = [ [1,2], [1,2], [1,2] ]输出: 2解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:输入: intervals = [ [1,2], [2,3] ]输出: 0解释: 你不需要移除任何区间，因为它们已经是无重叠的了。解题关键：1.如何判断两个区间是否重合 2.如何去重使得留下的区间最多解题思路：为了让留下的区间最多，首先需要排序，使得所有区间有区分度，重合更少。（作为区间题，或者是一些贪心题，排序总是会有大用处）我们可以使用左区间排序（右区间也可以，这道题的下面的题解用的是左排序）先排序区间，然后进行比较 如何比较？ 因为我们使用的是左排序，所以可以通过比较下一个区间的左区间与这一个区...
