retyrn

分类

题解(3)

/ 注册

全部文章（共206篇）

题解 | #草原上的牛群分布# 数组模拟

知识点模拟计数思路有序数组要求相同值不能超过三个，我们可以维护一个cnt记录当前数字有几个，然后从左到右遍历数组，当不满足三个时加入结果数组。由于结果数组一定不大于原数组，可以在原数组上修改。时间复杂度遍历一遍数组 AC code (c++) class Solution { public: ...

2023-07-23

0 290

题解 | #农场牛的最佳观赏区间# 二叉搜索树

知识点二叉搜索树思路总的思路是遍历二叉树的每一个点，累加在范围内的值，得到答案。但是由于二叉搜索树的左子树的值一定小于根节点小于右子树的值，所以当根节点的值大于low才遍历左子树，当根节点的值小于high才遍历右子树，可以优化常数。最坏复杂度不会变。时间复杂度最坏情况下每一个点都在范围内，遍历一遍二...

2023-07-23

0 325

题解 | #农场牛群族谱# 递归解法

知识点递归最近公共祖先思路要找两个点的最近公共祖先，从根节点查找所在的子树中是否含有这两个值，假如左右子树都含有目标节点，说明它们分居两个子树中，答案是当前父节点；假如有一个子树不存在，说明两个都在另外一个子树中。时间复杂度遍历一遍二叉树 AC code（C++） /** * struct T...

2023-07-23

0 297

题解 | #牛群特殊路径的数量# DFS

知识点DFS 树形DP 哈希表思路树中两点的路径和可以变成这两点到根节点的路径和的差值，我们构造一个dfs函数，来获取从根节点到达当前节点的路径总和，并用一个哈希表来维护已有的不同路径和的个数，那么以当前节点为较下面端点的贡献是mp[cur - sum]计算完当前贡献后，把当前cur加入mp用于...

2023-07-23

0 344

题解 | #牛群的最长距离# 树的直径树形DP

知识点树的直径树形DP思路树的直径板子题，有两次DFS的解法和树形DP的解法，这里是树形DP的做法。我们需要用DFS得到每个节点到叶子节点的最长距离，在每个节点处用左子树的最长距离和右子树最长距离以及本节点更新答案。由于我们求的是节点数，边数应该是-1。时间复杂度每个节点遍历常数次 AC cod...

2023-07-23

0 284

题解 | #调整牛群的位置# O(1)解法三次翻转

知识点利用翻转O(1)解决循环数组位移思路假如要把前k个数循环移动，我们可以先翻转前k个数，再翻转后n-k个数最后整个数组翻转即可实现时空复杂度时间复杂度为空间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数...

2023-07-22

1 270

题解 | #农场最大产奶牛群# 树形DP

知识点树形DP DFS思路答案一定是从某一个节点，到两个叶子结点的路径和。我们可以用树形DP进行解决。dfs返回从某一节点作为根节点的子树到达叶子结点的最大路径和，用经左子树和右子树的两个路径和 + 该结点的val来更新答案，然后将该结点的val加入路径后计算最大到叶子结点路径和，返回父节点。时间...

2023-07-22

0 248

题解 | #牛群的树形结构重建# DFS

知识点DFS 后序遍历中序遍历思路后序遍历是顺序是“左右中”，中序遍历顺序是“左中右”。因此每次找到对应序列的后序遍历的最后一个数作为根节点，然后找到对应的左右子树的对应的范围，把问题化为原问题的子问题，用递归解决。时间复杂度最差情况是一条链，时间复杂度为AC code（C++） /** *...

2023-07-22

0 282

题解 | #牛群的树形结构重建II# DFS

知识点DFS 先序遍历中序遍历思路先序遍历是顺序是“中左右”，中序遍历顺序是“左中右”。因此每次找到对应序列的先序遍历的第一个数作为根节点，然后找到对应的左右子树的对应的范围，把问题化为原问题的子问题，用递归解决。时间复杂度最差情况是一条链，时间复杂度为AC code（C++） /** * ...

2023-07-22

0 263

题解 | #牛群的树形结构展开II# 中序遍历

知识点中序遍历思路先中序遍历获取到指针的先后顺序，之后重新建立指针间的关系。时间复杂度每个节点访问常数次，AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *r...

2023-07-22

0 252