当前位置：首页 > news >正文

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

news 2025/6/25 0:15:43

细节

队列

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

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;
}

关键点总结