Darlingの妙妙屋

Day116 | 灵神 | 二叉树 | 二叉搜索树中第K小的元素230.二叉搜索树中第K小的元素230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode） 思路： 这道题也比较简单，就是中序遍历到第K个就是答案了 12345678910111213141516171819202122class Solution {public: int res=0; int count=0; void tra(TreeNode *t,int k) { if(t==nullptr) return; tra(t->left,k); count++; if(k==count) { res=t->val; return; } tra(t->right,k); } int kthSmallest(TreeNode* root,...

Day115 | 灵神 | 二叉树 | 二叉搜索树中的众数501.二叉搜索树中的众数501. 二叉搜索树中的众数 - 力扣（LeetCode） 思路： 直接想法：遍历一遍，然后用map统计频率，最后对value排序，选出最大的 更好地做法： 二叉搜索树中序遍历是有序的，收入到一个vector中对这个升序数组进行处理 更好一点的话，那就是中序遍历过程中动态统计频率 用MaxCnt记录最大值，用Cnt表示当前结点值的频率，用pre记录前一个节点 如果当前结点和前一个结点的值相等，那就Cnt++ 如果不相等那么Cnt重新置为1，表示当前结点t是一个新值 如果Cnt大于MaxCnt的话就把MaxCnt更新为Cnt 如果二者相等的话就把当前结点的值放入结果集中 1234567891011121314151617181920212223242526272829303132class Solution {public: int cnt=1; TreeNode* pre=nullptr; int MaxCnt=1; vector<int> res;...

移动IP与手机移动数据流量的概念、原理、区别与联系 一、概念与原理 移动IP 定义：移动IP是一种网络层协议，允许设备在不同网络（如Wi-Fi与蜂窝网络）间移动时保持固定IP地址，实现通信的无缝切换与连续性 核心原理： 代理机制：通过归属代理（Home Agent）和外地代理（Foreign Agent）实现数据转发。当设备移动到外部网络时，归属代理将数据通过隧道技术封装后转发至外地代理，再由外地代理解封装并传递给移动节点 转交地址（Care-of...

...

C++ 中 lower_bound 与 upper_bound 函数详解一、核心定义与区别 lower_bound 作用：在有序序列中查找第一个不小于目标值的元素位置 返回值：若目标值存在，返回第一个匹配元素的迭代器；若不存在，返回首个大于目标值的元素的迭代器 示例：在序列{1,2,4,4,5} 中查找 4，返回第一个4 的位置（索引 2） 用lower_bound在{12,15,17,19,20,22,23,26,29,35,40,51}，查找21时返回22的索引位置 upper_bound 作用：在有序序列中查找第一个大于目标值的元素位置 返回值：若目标值存在，返回最后一个匹配元素的下一个位置；若不存在，行为与lower_bound一致 示例：在相同序列{1,2,4,4,5}中查找4，返回第一个 5的位置（索引...

Day114 | 灵神 | 二叉树 | 二叉搜索树的最小绝对差2476.二叉搜索树最近节点查询2476. 二叉搜索树最近节点查询 - 力扣（LeetCode） 思路： 这道题目拿到手就觉得在树中递归查找太费劲了，还是转化为有序数组在数组中使用二分比较方便 1.中序遍历root得到有序数组arr 2.二分查找queries[i]即可找到最大最小值 C++ 中 lower_bound 与 upper_bound 函数详解-CSDN博客 123456789101112131415161718192021222324252627282930313233343536373839class Solution {public: vector<int> arr; //1.得到有序数组 void tra(TreeNode *t) { if(t==nullptr) return ; tra(t->left); arr.push_back(t->val); ...

Day113 | 灵神 | 二叉树 | 二叉搜索树的最小绝对差530.二叉搜索树的最小绝对差530. 二叉搜索树的最小绝对差 - 力扣（LeetCode） 思路： easy题目，中序遍历是有序的，最小绝对差肯定是相邻的 12345678910111213141516171819class Solution {public: int minVal=INT_MAX; int pre=INT_MIN/2;//防止溢出 void tra(TreeNode *t) { if(t==nullptr) return; tra(t->left); if(t->val-pre<minVal) minVal=t->val-pre; pre=t->val; tra(t->right); } int getMinimumDifference(TreeNode* root) { ...

Day112 | 灵神 | 二叉树 | 二叉搜索树的范围和938.二叉搜索树的范围和938. 二叉搜索树的范围和 - 力扣（LeetCode） 思路： 最直接的思路当然是直接前序遍历一遍，碰到在一个区间的就加到和里面 1234567891011121314151617class Solution {public: int res=0; void dfs(TreeNode* t, int low, int high) { if(t==nullptr) return ; if(t->val<=high&&t->val>=low) res+=t->val; dfs(t->left,low,high); dfs(t->right,low,high); } int rangeSumBST(TreeNode* root, int low, int high) { ...

Day111 | 灵神 | 二叉树 | 验证二叉搜索树98.验证二叉搜索树98. 验证二叉搜索树 - 力扣（LeetCode） 方法一：前序遍历 递归函数传入合法的左右边界，只有当前结点是合法的边界，才是二叉搜索树，否则就返回false 对于左子树就传入当前结点的左边界，和当前结点的值作为右边界，从而验证左子树是一颗二叉搜索树 对于右子树就传入当前结点的右边界，和当前结点的值作为左边界，从而验证右子树是一颗二叉搜索树 只有当前结点符合条件并且左右子树也都是二叉搜索树才会返回true 灵神前序遍历代码： 123456789101112class Solution {public: bool isValidBST(TreeNode* root, long long left = LLONG_MIN, long long right = LLONG_MAX) { if (root == nullptr) { return true; } long long x =...

Day110 | 灵神 | 二叉树 | 根到叶路径上的不足节点1080.根到叶路径上的不足节点1080. 根到叶路径上的不足节点 - 力扣（LeetCode） 思路： 笔者一开始没看懂，只能通过部分的例子，原因是把路径和小于limit的都给删了，但是如果留有左右节点其中一个的话就不能删。后面参考了灵神的，下面是灵神的思路： 一、思考对于一个叶子节点，要想删除它，需要满足什么条件？ 对于一个非叶节点，如果它有一个儿子没被删除，那么它能被删除吗？如果它的儿子都被删除，意味着什么？ 二、解惑对于一个叶子节点 leaf，由于根到 leaf 的路径仅有一条，所以如果这条路径的元素和小于 limit，就删除 leaf。 对于一个非叶节点 node，如果 node 有一个儿子没被删除，那么 node 就不能被删除。这可以用反证法证明：假设可以把 node 删除，那么经过 node 的所有路径和都小于 limit，也就意味着经过 node 的儿子的路径和也小于 limit，说明 node 的儿子需要被删除，矛盾，所以 node 不能被删除。 如果 node 的儿子都被删除，说明经过 node...