Darlingの妙妙屋

...

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...

Day109 | 灵神 | 148.排序链表 | 归并排序148. 排序链表 - 力扣（LeetCode） 以下是灵神的题解，笔者认为这题只要可以看懂就好了 两种方法：分治和迭代 前置题目 876. 链表的中间结点 21. 合并两个有序链表 方法一：归并排序（分治） 找到链表的中间结点 head2 的前一个节点，并断开 head2 与其前一个节点的连接。这样我们就把原链表均分成了两段更短的链表 分治，递归调用 sortList，分别排序 head（只有前一半）和 head2。 排序后，我们得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class Solution { // 876. 链表的中间结点（快慢指针） ListNode* middleNode(ListNode* head) { ListNode* pre =...

Day108 | 灵神 | 合并两个有序链表21. 合并两个有序链表 - 力扣（LeetCode） 思路： 这是道easy题，直接写就行 说一下递归的写法 递归函数的含义是合并两个有序链表，返回值是合并后的链表的头结点 递归边界：如果其中一个链表为空，直接返回另一个链表作为合并后的结果 本层逻辑：谁小就把谁接到当前结点的后面，然后返回当前结点作为合并后的结果 完整代码： 1234567891011121314151617181920212223class Solution {public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *t=new ListNode; ListNode *res=t; while(list1&&list2) { if(list1->val<list2->val) { ...

对计网考研中的信道、传输时延、传播时延的理解在学习数据链路层流量控制和可靠传输那一节的三个协议的最大信道利用率时产生的疑惑 情景： 假如A主机和B主机通过集线器连接，A和集线器是光纤连接，B和集线器也是光纤连接，A给B发送帧 问题： 那么信道指的是什么？发送信道指的是什么？包含A到B之间的光纤吗？还是A把数据推到光纤上所经过的地方才是信道，光纤并不算在内？所以才说算信道利用率的时候，只算传输时延而不看传播时延？ 那A的数据在光纤中传播时，算不算信道的空闲时间呢？ 一、信道的定义与范围1.信道（Channel）的物理本质信道是数据传输的物理或逻辑路径。在本场景中，​信道包含A到集线器的光纤链路、集线器内部背板总线以及集线器到B的光纤链路。 光纤作为传输介质是信道的重要组成部分（，而集线器内部采用总线结构实现逻辑上的共享连接 由于集线器工作在物理层，所有端口共享同一冲突域和广播域，因此 整个集线器连接的线路构成一个共享信道 2.发送信道（Transmission...