杭州有哪些做网站的公司好,大连seo网站,好的网站建设公司排名,免费的html大作业网站系列目录
88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 …系列目录
88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 142.环型链表 21.合并两个有序列表 24.两辆交换链表中的节点 876.链表的中间节点 143. 重排链表 2.两数相加 445.两数相加II 目录 系列目录102. 二叉树的层序遍历103. 二叉树的锯齿形层序遍历双端队列Deque树BFS与层序遍历 102. 二叉树的层序遍历 队列BFS/层序遍历 原题链接 C 若未特殊标明以下题解均写用C
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
// #include queue
// #include vector
class Solution {
public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint ans; if (root nullptr)return ans; queueTreeNode* cur; cur.push(root); while (!cur.empty()) { int size cur.size(); // 当前层的节点数 vectorint vals; // 存储当前层的节点值 for (int i 0; i size; i) { TreeNode* node cur.front(); cur.pop(); vals.push_back(node-val); if (node-left) { cur.push(node-left); } if (node-right) { cur.push(node-right); } } ans.push_back(vals); // 将当前层的节点值添加到答案中 } return ans; }
};103. 二叉树的锯齿形层序遍历 队列双端队列BFS/层序遍历 原题链接
本题实为102.二叉树的层序遍历变种题 C 若未特殊标明以下题解均写用C
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {// 因为最终返回的结果是 集合套集合// 定义一个二维向量 res 存放结果vectorvectorint res;if (!root)return res;bool isOrderLeft true;// 初始化普通队列 存放二叉树的树状节点// nodeQueuequeueTreeNode* nq;// 将根节点入队 能正常开始循环nq.push(root);while (!nq.empty()) {// 初始化双端队列 以便不同次序输出每一层的树节点值// floorListDequedequeint fld;int size nq.size();for (int i 0; i size; i ) {auto node nq.front();// 用完当前的node 出队nq.pop();if (isOrderLeft) {// int 类型的双端队列 fld// 从左往右——从队尾入队fld.push_back(node-val);} else {// 从右往左——从队头入队fld.push_front(node-val);}if (node-left) {nq.push(node-left);}if (node-right) {nq.push(node-right);}} // for_endres.emplace_back(vectorint{fld.begin(), fld.end()});isOrderLeft !isOrderLeft;} // while_endreturn res;}
};双端队列Deque
双端队列(Deque全称double-ended queue)是一种具有队列和栈的性质的抽象数据类型 允许我们在两端进行插入和删除操作即可以从头部(front)或尾部(back)添加或移除元素 在C中std::deque是标准模板库(STL)提供的一个双端队列的实现 不过为了深入理解双端队列的工作原理我们可以尝试自己实现一个简单的双端队列 以下是一个简单的双端队列的C实现我们将使用动态数组(例如通过std::vector)来存储元素并提供基本的双端队列操作如push_front、push_back、pop_front、pop_back、front、back等
#include iostream
#include vector
#include stdexcept // For std::out_of_range templatetypename T
class MyDeque {
private: std::vectorT data; public: // 向队尾添加元素 void push_back(const T value) { data.push_back(value); } // 向队首添加元素 void push_front(const T value) { data.insert(data.begin(), value); } // 从队尾移除元素 void pop_back() { if (data.empty()) { throw std::out_of_range(Deque is empty); } data.pop_back(); } // 从队首移除元素 void pop_front() { if (data.empty()) { throw std::out_of_range(Deque is empty); } data.erase(data.begin()); } // 访问队首元素 T front() { if (data.empty()) { throw std::out_of_range(Deque is empty); } return data.front(); } // 访问队尾元素 T back() { if (data.empty()) { throw std::out_of_range(Deque is empty); } return data.back(); } // 判断双端队列是否为空 bool empty() const { return data.empty(); } // 获取双端队列的大小 size_t size() const { return data.size(); }
}; int main() { MyDequeint myDeque; myDeque.push_back(10); myDeque.push_front(5); myDeque.push_back(15); std::cout Front element: myDeque.front() std::endl; std::cout Back element: myDeque.back() std::endl; myDeque.pop_front(); std::cout After pop_front, front element: myDeque.front() std::endl; myDeque.pop_back(); std::cout After pop_back, back element: myDeque.back() std::endl; return 0;
}⚠️注意事项 性能 虽然以上代码实现起来简单易懂但在某些操作上(如push_front和pop_front)由于std::vector的特性可能需要移动大量元素因此性能可能不是最优的
错误处理 在实现中我使用了std::out_of_range异常来处理尝试在空双端队列上进行pop或front/back访问的情况 这是一种常见的错误处理方式但你也可以选择其他方式如返回特殊值或设置错误标志
功能扩展 你可以根据需要扩展这个类比如 添加迭代器支持、更复杂的元素访问方法(如通过索引访问)等 树
树(Tree)是一种特殊的图(Graph) 具体来说树是一种无环的连通图 特性如下
无环(Acyclic) 树中不包含任何环 即从一个节点到另一个节点存在唯一的一条路径连通(Connected) 树中的任意两个节点都通过边(或路径)相连无向图 虽然树的概念也可以扩展到有向图(如二叉树)但在大多数情况下当我们说“树”时我们指的是无向图根节点 虽然图不一定有根节点的概念但树通常被定义为一个或多个特定的节点(称为根节点)以及从根节点出发的一系列边和子树 在只有一个根节点的树中每个节点(除了根节点本身)都有且仅有一个父节点而每个非叶节点都可以有多个子节点叶子节点 树中的叶子节点是没有子节点的节点路径 树中的路径是指从一个节点到另一个节点所经过的一系列边和节点的序列由于树是无环的所以任意两个节点之间的路径是唯一的 BFS与层序遍历
在二叉树的遍历中BFS和层序遍历实际上是同一个概念的不同表述方式
广度优先搜索(BFS, Breadth-First Search) 一种用于图和树的遍历或搜索算法 它从根节点开始先访问离根节点最近的节点(即第一层)然后逐层向下访问每层按从左到右的顺序访问节点 对于二叉树来说这恰好就是层序遍历层序遍历(Level-Order Traversal) 二叉树遍历的一种特殊方式它按照树的层次从上到下、从左到右进行遍历 通常用队列实现 具体来说就是先访问根节点然后遍历根节点的左子树和右子树接着再遍历左子树的左子树和右子树、右子树的左子树和右子树以此类推逐层遍历
