TypechoJoeTheme
2023-09-22
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-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.如何去重使得留下的区间最多解题思路：为了让留下的区间最多，首先需要排序，使得所有区间有区分度，重合更少。（作为区间题，或者是一些贪心题，排序总是会有大用处）我们可以使用左区间排序（右区间也可以，这道题的下面的题解用的是左排序）先排序区间，然后进行比较 如何比较？ 因为我们使用的是左排序，所以可以通过比较下一个区间的左区间与这一个区...
2023-09-18
**题目：**给你一个整数数组 nums 和一个整数 k 。每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。返回你可以对数组执行的最大操作数。示例 1：输入：nums = [1,2,3,4], k = 5输出：2解释：开始时 nums = [1,2,3,4]：移出 1 和 4 ，之后 nums = [2,3]移出 2 和 3 ，之后 nums = []不再有和为 5 的数对，因此最多执行 2 次操作。示例 2：输入：nums = [3,1,3,4,3], k = 6输出：1解释：开始时 nums = [3,1,3,4,3]：移出前两个 3 ，之后nums = [1,4,3]不再有和为 6 的数对，因此最多执行 1 次操作。解法一：哈希表这个解法是我根据之前做过的两数之和的题解拓展之后写出的，但是放在这道题上，由于其过多的操作导致其时间和空间效率都很低，因此不推荐class Solution {
public int maxOperations(int[] nums, int k) {
int length = nums.length;...
