C++ 数据结构算法细节相关

细节

队列

这段代码实现的是二叉树的层序遍历，也就是按照树的层次，一层一层地遍历节点。下面我会为你详细解释这段代码。

1. queue <TreeNode*> q;

   • 这是一个队列，队列中存放的是指向TreeNode的指针。
   • 队列（queue）是一种先进先出（FIFO）的数据结构。你可以把元素添加到队列的尾部，并从队列的头部移除元素。
   • 在这段代码中，队列q用于暂存每一层的节点，以便按层遍历。
   • 详细用法:
     • q.push(element): 将元素添加到队列尾部。
     • q.front(): 返回队列头部的元素，但不移除。
     • q.pop(): 移除队列头部的元素。
     • q.empty(): 判断队列是否为空，如果为空返回true，否则返回false。
     • q.size(): 返回队列中的元素数量

广度优先搜索

所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。

lower_bound和upper_bound

lower_bound

• 定义: lower_bound 返回一个指向容器中第一个不小于给定值的元素的迭代器。如果所有元素都小于该值，则返回容器的末尾迭代器。
• 用法:

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> v = {1, 2, 4, 4, 5, 6};// 查找值为 4 的第一个不小于 4 的位置auto it = std::lower_bound(v.begin(), v.end(), 4);if (it != v.end()) {std::cout << "lower_bound: " << *it << " at index " << (it - v.begin()) << std::endl;} else {std::cout << "No element found." << std::endl;}return 0;
}

upper_bound

• 定义: upper_bound 返回一个指向容器中第一个大于给定值的元素的迭代器。如果所有元素都小于或等于该值，则返回容器的末尾迭代器。
• 用法:

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> v = {1, 2, 4, 4, 5, 6};// 查找值 4 的第一个大于 4 的位置auto it = std::upper_bound(v.begin(), v.end(), 4);if (it != v.end()) {std::cout << "upper_bound: " << *it << " at index " << (it - v.begin()) << std::endl;} else {std::cout << "No element found." << std::endl;}return 0;
}

关键点总结

• lower_bound 查找值范围的开始（第一个不小于给定值），而 upper_bound 查找值范围的结束（第一个大于给定值）。
• 这两个函数都使用二分查找，因此时间复杂度为 O(log n)。
• 返回值是指向容器中的迭代器，可以使用它来得到相应的元素或计算索引。

场景示例

• 如果你想在一个有序数组中插入一个值并保持数组的有序性，可以使用这两个函数来决定插入的位置。
• 在处理重复元素时，lower_bound 可以帮助你找到第一个匹配的元素的位置，而 upper_bound 可以帮助你找到最后一个匹配元素之后的位置，从而可以知道有多少重复元素。

希望这能帮助你更好地理解这两个函数的使用！如果你有任何具体的疑问或者案例，欢迎随时询问。

其他