二叉树的右视图-LeetCode
二叉树的右视图 🎯 问题描述 给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例 1： 12输入：root = [1,2,3,null,5,null,4]输出：[1,3,4] **示例 2 12输入：root = [1,2,3,4,null,null,null,5]输出：[1,3,4,5] 💻 解题思路 思路：DFS 深度优先搜索（右优先遍历） 核心思想：利用 DFS 优先遍历右子树。对于每一层深度，第一个被访问到的节点，一定是最靠右的节点。 代码实现 from typing import Optional, List # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right c...
二叉树的最小深度-LeetCode
二叉树的最小深度 🎯 问题描述（来源于LeetCode） 描述： 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明：叶子节点是指没有子节点的节点。 示例： 示例 1：12345678输入：root = [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7输出：2解释：最短路径为 3 -> 9，共 2 个节点。 示例 2：123456789101112输入：root = [2,null,3,null,4,null,5,null,6] 2 \ 3 \ 4 \ 5 \ 6输出：5解释：这是一棵单边树（类似链表），最短路径就是整条链，共 5 个节点。 💻 解题思路 思路1：递归（DFS 自底向上） 代码实现 from typing import Optional class Solution: def minD...
求根节点到叶节点数字之和-LeetCode
求根节点到叶节点数字之和 🎯 问题描述 给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字（例如 1->2->3 表示数字 123）。计算从根节点到叶节点生成的所有数字之和。 说明： - 叶子节点是指没有子节点的节点。 - 路径数值的计算逻辑：每往下走一层，之前的数值 × 10 + 当前节点的数值。 示例： 示例 1： 1234- 输入：root = [1,2,3] 1 / \ 2 3 输出：25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25 示例 2： 输入：root = [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 输出：1026 解释： 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此，数字总和...
统计二叉树中好节点的数目-LeetCode
统计二叉树中好节点的数目 🎯 问题描述 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。 「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值（即当前节点的值，是从根到该节点路径上的最大值）。 💻 解题思路 思路：DFS 深度优先搜索（带状态传递） 核心思想：在从根节点向下遍历的过程中，我们需要时刻记录“从根节点到当前节点路径上遇到的最大值”。如果当前节点的值大于等于这个最大值，它就是一个好节点。 代码实现 from typing import Optional # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def goodNodes(sel...
路径总和-LeetCode
路径总和 🎯 问题描述（来源于LeetCode） 描述： 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。 如果存在，返回 true；否则，返回 false。 说明： 叶子节点是指没有子节点的节点。 路径必须是从根节点出发，一直走到叶子节点。 示例： 示例 1：123输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22输出：true解释：存在一条根节点到叶子节点的路径 5 -> 4 -> 11 -> 2，和为 22。 示例 2：123456输入：root = [1,2,3], targetSum = 5输出：false解释：树中存在两条根节点到叶子节点的路径：(1 -> 2): 和为 3(1 -> 3): 和为 4不存在 sum = 5 的路径。 💻 解题思路 思路1：递归（DFS 自顶向下） 代码实现 fro...
K次增加后的最大乘积-LeetCode
2233. K次增加后的最大乘积 🎯 问题描述（来源于LeetCode） 描述： 给你一个非负整数数组 nums 和一个整数 k。你可以执行以下操作恰好 k 次： 选择 nums 中的任意一个元素，将其值增加 1。 请你返回在执行完 k 次操作后，数组中所有元素的最大乘积。由于答案可能很大，请将结果对 10^9 + 7 取余后返回。 说明： 为了让最终的乘积最大，我们的贪心策略是：每次操作都必须选择当前数组中数值最小的那个元素进行加 1。 只有每次都最大程度地“补齐短板”，才能保证整体乘积的增长幅度最大。 示例： 示例 1：123456789输入：nums = [0,4], k = 5输出：20解释：第1次：将0加1，数组变为 [1,4]第2次：将1加1，数组变为 [2,4]第3次：将2加1，数组变为 [3,4]第4次：将3加1，数组变为 [4,4]第5次：将4加1，数组变为 [5,4]最终乘积为 5 * 4 = 20。 示例 2：123输入：nums = [6,3,3,2], k = 2输出：216解释：依次将两个最小的 2 和 3 加 1，最终数组变为 ...
将数组和减半的最少操作次数-LeetCode
2208. 将数组和减半的最少操作次数 🎯 问题描述（来源于LeetCode） 描述： 给你一个正整数数组 nums。每一次操作中，你可以从 nums 中选择任意一个数，将其值减小为原来的一半。 请你返回将 nums 数组和至少减少一半的最少操作数。 说明： 为了让操作次数最少，我们的贪心策略是：每次操作都必须选择当前数组中数值最大的那个元素进行减半。 只有每次都最大程度地减少总和，才能以最少的次数达到总和减半的目标。 示例： 示例 1：1234567输入：nums = [5,19,8,1]输出：3解释：初始总和为 5+19+8+1 = 33，目标是减少到 16.5 以下。第1次：选19减半为9.5，数组变为 [5,9.5,8,1]，总和减少了9.5。第2次：选9.5减半为4.75，数组变为 [5,4.75,8,1]，总和减少了4.75。第3次：选8减半为4，数组变为 [5,4.75,4,1]，总和减少了4。此时总共减少了 9.5+4.75+4 = 18.25，超过了目标16.5，操作数为3。 💻 解题思路 思路1：贪心 + 最大堆（Python...
座位预约管理系统-LeetCode
1845. 座位预约管理系统 🎯 问题描述（来源于LeetCode） 描述： 请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n。 请实现 SeatManager 类： SeatManager(int n)：初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。 int reserve()：返回可以预约座位的 最小编号，此座位变为不可预约。 void unreserve(int seatNumber)：将给定编号 seatNumber 对应的座位变成可以预约。 说明： 每次预约时，必须返回当前所有可预约座位中编号最小的那个。 当座位被释放（unreserve）后，它应该重新变为可预约状态，并参与下一次的最小编号比较。 示例： 示例 1：1234567891011输入：["SeatManager", "reserve", "reserve", "unreserve", "reserve", &...
第K近障碍物查询-LeetCode
3275.第K近障碍物查询 🎯 问题描述（来源于LeetCode） 有一个无限大的二维平面。 给你一个正整数 k ，同时给你一个二维数组 queries ，包含一系列查询： queries[i] = [x, y] ：在平面上坐标 (x, y) 处建一个障碍物，数据保证之前的查询 不会 在这个坐标处建立任何障碍物。 每次查询后，你需要找到离原点第 k 近 障碍物到原点的 距离 。 请你返回一个整数数组 results ，其中 results[i] 表示建立第 i 个障碍物以后，离原地第 k 近障碍物距离原点的距离。如果少于 k 个障碍物，results[i] == -1 。 注意，一开始 没有 任何障碍物。 坐标在 (x, y) 处的点距离原点的距离定义为 |x| + |y| 示例： 示例 1：1234567输入：queries = [[1,2],[3,4],[2,3],[-3,0]], k = 2输出：[-1,7,5,3]解释：- 第0次查询：距离为 3，不足2个点，返回 -1。- 第1次查询：距离为 3, 7。第2小的距离是 7，返回 7。- 第2次查询：距离为...
Dota2参议院-LeetCode
649. Dota2 参议院 🎯 问题描述 描述： Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）。参议院由来自两派的参议员组成。现在他们要对游戏中的改变进行投票。投票过程是轮次的，每位参议员可以行使两项权利之一： 禁止一名参议员的权利：使另一名参议员在后续所有轮次中失去投票权。 宣布胜利：如果当前轮次中，有投票权的参议员都来自同一个阵营，那么他可以宣布胜利。 给定一个代表每个参议员阵营的字符串 senate（‘R’ 代表 Radiant，‘D’ 代表 Dire），假设每位参议员都会为自己的阵营做出最明智的选择（即优先禁止对自己阵营威胁最大的敌方参议员）。你需要预测最终哪一方会宣布胜利。 说明： 这是一个队列模拟与贪心问题。 核心策略： 参议员按照字符串顺序轮流行动。 最明智的选择是：禁止掉下一个即将行动的敌方参议员。因为如果不禁止，对方下一轮就会禁止自己阵营的队友。 使用队列模拟轮流行动的过程，每次行动时直接在队列中寻找并移除敌方参议员。 示例： 示例 1： 12345输入：senate = "RD&quo...
