h5手机网站实例无锡全网营销方案

h5手机网站实例,无锡全网营销方案,做网站的销售团队,手工艺品网站建设目的目录 一、相关题目 1. 最小栈 (LeetCode 155) 2. 栈的压入、弹出序列 (Nowcoder) 3. 二叉树的层序遍历 (LeetCode 102) 二、栈模拟实现#xff08;vector版本#xff09; 1. 适配器 2. 模拟实现 3. 模板按需实例化 三、队列模拟实现#xff08;list版本#xff09…目录一、相关题目1. 最小栈 (LeetCode 155)2. 栈的压入、弹出序列 (Nowcoder)3. 二叉树的层序遍历 (LeetCode 102)二、栈模拟实现vector版本1. 适配器2. 模拟实现3. 模板按需实例化三、队列模拟实现list版本四、Deque 介绍五、Priority_queue (优先队列) 使用1. 与 queue 区别2. 仿函数六、优先队列堆模拟实现1. 向上调整 (adjustup)2. 向下调整 (adjustdown)3. 插入 (push)4. 删除 (pop)5. top, size, empty七、堆相关算法库代码队列栈堆一、相关题目由于相关使用和之前的容器欻不多因此先看几个题目1. 最小栈 (LeetCode 155)题目链接https://leetcode.cn/problems/min-stack/大意设计一个栈支持快速返回当前栈中的元素最小值。思路用两个栈一个模拟标准栈操作 (st)另一个记录并同步当前的最小值 (min_st)。代码实现class MinStack { public: MinStack() {} void push(int val) { if(min_st.empty() || val min_st.top()) { min_st.push(val); } st.push(val); } void pop() { if(st.top() min_st.top()) { min_st.pop(); } st.pop(); } int top() { return st.top(); } int getMin() { return min_st.top(); } private: stackint st; stackint min_st; };2. 栈的压入、弹出序列 (Nowcoder)题目链接栈的压入、弹出序列_牛客题霸_牛客网大意判断给定的一组压入序列是否能通过栈操作得到指定的弹出序列。思路简单模拟。将压入序列依次入栈每次入栈后循环判断栈顶是否与弹出序列的当前元素相同若相同则弹出。最终判断弹出序列是否被全部匹配。代码实现bool IsPopOrder(vectorint pushV, vectorint popV) { stackint st; int c1 0, c2 0; for(c1 0; c1 pushV.size(); c1) { st.push(pushV[c1]); while(!st.empty() popV[c2] st.top()) { st.pop(); c2; } } return c2 popV.size(); }3. 二叉树的层序遍历 (LeetCode 102)题目链接102. 二叉树的层序遍历 - 力扣LeetCode题目大意返回二叉树每层的节点值装在一个二维数组里。代码实现vectorvectorint levelOrder(TreeNode* root) { if(!root) { vectorvectorint vvv; return vvv; } queueTreeNode* qu; qu.push(root); int sz qu.size(); vectorint v; vectorvectorint vv; while(!qu.empty()) { while(sz--) { auto e qu.front(); qu.pop(); v.push_back(e-val); if(e-left) { qu.push(e-left); } if(e-right) { qu.push(e-right); } } vv.push_back(v); sz qu.size(); v.clear(); } return vv; }二、栈模拟实现vector版本1. 适配器首先栈和之前的vector、list等容器一个很大的区别就是用范围for遍历栈的每一个元素没有意义破坏了栈的LIFO特性。因此严格意义上讲它不是一个标准容器STL 将其称为容器适配器。其本质为将其它容器如vector,deque,list进行包装实现栈的接口。由于不是完整容器它也没有自己的迭代器。2. 模拟实现即复用底层容器此处选用vector的各个接口。templateclass T, class Container std::vectorT class stack { public: void push(const T val) { _con.push_back(val); } void pop() { _con.pop_back(); } const T top() const { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; };3. 模板按需实例化如果我们在栈的模板实现中错误地调用一个底层容器不存在的函数void pop() { _con.f1(); // vector 并没有 f1() 这个成员函数 }如果我们不使用pop这个接口那么程序编译时不会报错。但一旦调用了pop编译器就会报错f1: 不是 std::vectorT,std::allocatorT 的成员。这是因为模板在不被调用时编译器不会进行实例化检查只会扫描最基础的语法错误。因此模板代码需要全面测试才能确保没有问题。三、队列模拟实现list版本由于vector的头删效率低而list头尾插删效率都高因此队列的底层容器适配器选用list。templateclass T, class Container std::listT class queue { public: void push(const T val) { _con.push_back(val); } void pop() { _con.pop_front(); // 注意队列是 pop_front } const T front() const { // 注意队列是 front return _con.front(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; };四、Deque 介绍在 STL 文档中stack和queue的默认底层容器是deque。为什么是deque先分析 vector 和 list 的优缺点Vector:优尾插尾删效率高支持下标随机访问。物理空间连续CPU高速缓存命中率高。缺空间需扩容有性能代价和空间浪费。头部、中间插入删除效率低。List:优按需申请空间不用扩容。任意位置插入删除效率高。缺不支持下标随机访问。缓存不友好。deque 是 vector 和 list 的融合它试图既能高效头尾插删又能支持随机访问。但这是一种“中庸”的融合在特定场景下好用并非所有方面都最优。deque 大致原理结合了两者deque由多个固定大小的连续“缓冲区”(buff)组成。这些缓冲区的指针由一个“中控数组” (map) 统领。最开始的buff数组的指针存在中控数组中间以便进行快速的头尾插入。当我们要访问第i个元素时会去定位第i / N个buff数组的第i % N个元素即*(*(ptr x) y)。迭代器实现deque迭代器由 4 个指针构成cur(当前位置),first(当前缓冲区头),last(当前缓冲区尾),node(指向中控数组中当前缓冲区指针的指针)。快速头尾插头插在最左边新开一个buff数组插到末尾或直接插到第一个buff数组的第一个元素前面。尾插插到最后一个buff数组的最后一个元素后面或最右边新开一个buff数组。中间插入/删除效率低下因为可能需要移动大量元素。Deque 特点总结头尾插删效率高理论上比vector、list都高因为不用频繁开空间list扩容代价小vector。下标随机访问略慢于vector。中间插入删除远慢于list。用 deque 作为 stack/queue 默认容器的原因栈和队列的操作只涉及头部和尾部的插入删除因此deque是非常合适的选择。五、Priority_queue (优先队列) 使用1. 与 queue 区别push没要求但top()和pop()总是取出当前队列中优先级最高的元素。其本质就是一个堆。默认情况下是大根堆。2. 仿函数写法templateclass T struct cmp { bool operator()(const T a, const T b) const { return a b; // 定义比较规则 } }; cmpint lessfunc; // 实例化一个比较器对象它重载了()运算符可以像函数一样被调用故称“仿函数”。与排序结合的例子冒泡排序泛化// 原始的冒泡排序只能从小到大 void bubble_sort(int* a, int n) { for (int i 0; i n; i) { int fl 0; for (int j 1; j n - i; j) { if (a[j - 1] a[j]) { // 比较逻辑写死 swap(a[j - 1], a[j]); fl 1; } } if (fl 0) break; } }使用仿函数可以灵活定义排序规则templateclass T struct cmp1 { bool operator()(const T a, const T b) const { return a b; } }; templateclass Compare cmp1int void bubble_sort(int* a, int n, Compare cmp cmp1int()) { for (int i 0; i n; i) { int fl 0; for (int j 1; j n - i; j) { if (cmp(a[j], a[j - 1])) { // 使用传入的比较器 swap(a[j - 1], a[j]); fl 1; } } if (fl 0) break; } }使用方式有名对象bubble_sort(a, 10, cmp);匿名对象bubble_sort(a, 10, cmp1int());标准库仿函数C 标准库提供了类似的仿函数如less,greater。从小到大升序bubble_sort(a, 10, lessint());从大到小降序bubble_sort(a, 10, greaterint());六、优先队列堆模拟实现1. 向上调整 (adjustup)void adjustup(int c) { compare com; // 比较器 int p (c - 1) / 2; while (c 0) { if (com(_con[p], _con[c])) { // 父节点不满足堆性质 std::swap(_con[p], _con[c]); c p; p (c - 1) / 2; } else { break; } } }2. 向下调整 (adjustdown)void adjustdown(int p) { int c p * 2 1; compare com; while (c _con.size()) { if (c _con.size() - 1 com(_con[c], _con[c 1])) { c; // 取左右孩子中更大或更小的那个 } if (com(_con[p], _con[c])) { // 父节点不满足堆性质 std::swap(_con[p], _con[c]); p c; c 2 * p 1; } else { break; } } }3. 插入 (push)在底层容器vector最后插入再向上调整。void push(const T val) { _con.push_back(val); adjustup(_con.size() - 1); }4. 删除 (pop)交换堆顶与堆底元素尾删堆底再从堆顶向下调整。void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjustdown(0); }5. top, size, empty调用底层容器vector的接口即可。const T top() { return _con[0]; } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); }七、堆相关算法库STL 提供了algorithm中的堆操作函数make_heap: 在普通数组或容器上建堆。sort_heap: 对一个已建好的堆进行堆排序。is_heap: 判断一个序列是否满足堆结构。注意sort_heap必须在已经建好的堆例如通过make_heap生成上使用。int num[5] {3, 1, 2, 4, 5}; make_heap(num, num 5); // 将数组建成堆 sort_heap(num, num 5); // 对堆进行排序代码队列#includeiostream #includelist #includedeque namespace bit { templateclass T, class container std::dequeT class queue { public: void push(const T val) { _con.push_back(val); } void pop() { _con.pop_back(); } const T front() const { return _con.front(); } const T back() const { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: container _con; }; }栈#includeiostream #includevector #includedeque //using namespace std; namespace bit { templateclass T,class containerstd::dequeT class stack { public: void push(const Tval) { _con.push_back(val); } void pop() { _con.pop_front(); } const T top()const { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: container _con; }; }堆#includeiostream #includevector #includequeue namespace bit { templateclass T, class container std::vectorT,class comparestd::lessint class priority_queue { public: void adjustup(int c) { compare com; int p (c - 1) / 2; while (c 0) { if (com(_con[p], _con[c])) { std::swap(_con[p], _con[c]); c p; p (c - 1) / 2; } else { break; } } } void push(const Tval) { _con.push_back(val); adjustup(_con.size() - 1); } void adjustdown(int p) { int c p * 2 1; compare com; while (c _con.size()) { if (c _con.size() - 1 com(_con[c], _con[c 1])) { c; } if (com(_con[p], _con[c])) { std::swap(_con[p], _con[c]); p c; c 2 * p 1; } else { break; } } } void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjustdown(0); } const T top() { return _con[0]; } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: container _con; }; }