leetcode 1670

leetcode 1670

解题思路

使用2个deque作为类的成员变量

code

class FrontMiddleBackQueue {
public:deque<int> left;deque<int> right;FrontMiddleBackQueue() {}void pushFront(int val) {left.push_front(val);if(left.size() == right.size()+2){right.push_front(left.back());left.pop_back();}}void pushMiddle(int val) {if(left.size() == right.size() + 1){right.push_front(left.back());left.pop_back();}left.push_back(val);}void pushBack(int val) {right.push_back(val);if(left.size() + 1 == right.size()){left.push_back(right.front());right.pop_front();}}int popFront() {if(left.empty()){return -1;}int val = left.front();left.pop_front();if(left.size() + 1 == right.size()){left.push_back(right.front());right.pop_front();}return val;}int popMiddle() {if(left.empty()){return -1;}int val = left.back();left.pop_back();if(left.size() + 1 == right.size()){left.push_back(right.front());right.pop_front();}return val;}int popBack() {if(left.empty()){return -1;}int val = 0;if(right.empty()){val = left.back();left.pop_back();}else{val = right.back();right.pop_back();// pop 之后，left 和 right 相差2个元素的情况if(left.size() == right.size() + 2){right.push_front(left.back());left.pop_back();}}return val;}
};/*** Your FrontMiddleBackQueue object will be instantiated and called as such:* FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();* obj->pushFront(val);* obj->pushMiddle(val);* obj->pushBack(val);* int param_4 = obj->popFront();* int param_5 = obj->popMiddle();* int param_6 = obj->popBack();*/

c++ 相关

成员变量和局部变量

class FrontMiddleBackQueue {
public:deque<int> left;deque<int> right;FrontMiddleBackQueue() {}
}

和

class FrontMiddleBackQueue {
public:FrontMiddleBackQueue() {deque<int> left;deque<int> right;}
}

在第一个示例中，FrontMiddleBackQueue 类包含了两个 deque 类型的成员变量 left 和 right。这意味着每个 FrontMiddleBackQueue 对象都会包含两个 deque 对象作为其成员。

而在第二个示例中，FrontMiddleBackQueue 类的构造函数中定义了两个 deque 对象 left 和 right。这意味着每次创建 FrontMiddleBackQueue 对象时，都会在构造函数中新建两个 deque 对象。

因此，第一个示例中的 left 和 right 是 FrontMiddleBackQueue 类的成员变量，它们在对象的整个生命周期内都存在；而第二个示例中的 left 和 right 是构造函数内的局部变量，它们只在构造函数执行期间存在。

总的来说，第一个示例中的 left 和 right 是 FrontMiddleBackQueue 类的成员变量，而第二个示例中的 left 和 right 只是构造函数内的局部变量。

stl 组成

C++的STL（Standard Template Library）由以下几个组成部分构成：

1. 容器（Containers）：包括vector、list、deque、set、map等，用于存储和管理数据。
2. 算法（Algorithms）：包括对容器中的数据进行排序、查找、遍历等操作的算法，如sort、find、for_each等。
3. 迭代器（Iterators）：用于在容器中进行数据访问和遍历的工具，包括输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器等。
4. 仿函数（Functors）：也称为函数对象，用于封装可调用对象，可以在算法中作为函数参数使用。
5. 适配器（Adapters）：包括stack、queue、priority_queue等，用于提供特定接口的容器适配器。

STL的这些组成部分共同构成了一个强大的工具库，可以大大简化C++程序的开发和维护工作，提高程序的性能和可维护性。

c++ 常见的stl容器

C++的STL（Standard Template Library）提供了多种容器，用于存储和管理数据。常见的STL容器包括：

1. vector（动态数组）
2. list（双向链表）
3. deque（双端队列）
4. set（集合，不重复的有序元素）
5. map（映射，键值对）
6. unordered_set（无序集合）
7. unordered_map（无序映射）
8. stack（栈）
9. queue（队列）
10. priority_queue（优先队列）

除了上述常见的容器外，STL还提供了其他一些容器和适配器，以满足不同的数据存储和访问需求。这些容器提供了不同的性能特点和适用场景，可以根据具体的需求选择合适的容器来存储和管理数据。

c++ 的stl的算法

C++ STL（Standard Template Library）提供了丰富的算法，用于对容器中的数据进行排序、查找、遍历等操作。以下是一些常见的STL算法：

1. 排序算法：

   • sort：对容器中的元素进行排序
   • stable_sort：稳定排序，保持相等元素的相对顺序
   • partial_sort：部分排序，将容器中的一部分元素排序

2. 查找和搜索算法：

   • find：在容器中查找指定元素
   • binary_search：二分查找
   • lower_bound：返回第一个大于等于指定值的元素位置
   • upper_bound：返回第一个大于指定值的元素位置
   • equal_range：返回指定值的范围

3. 数值算法：

   • accumulate：对容器中的元素进行累加
   • inner_product：计算两个容器的内积
   • partial_sum：计算部分和
   • adjacent_difference：计算相邻元素的差值

4. 遍历算法：

   • for_each：对容器中的每个元素执行指定操作
   • transform：对容器中的元素进行转换操作

5. 删除和修改算法：

   • remove：删除容器中指定值的元素
   • replace：将容器中指定值的元素替换为新值
   • reverse：反转容器中的元素顺序
   • rotate：旋转容器中的元素顺序

以上只是一部分常见的STL算法，STL还提供了更多强大的算法，可以根据具体需求选择合适的算法来处理容器中的数据。

stl 的迭代器

C++ STL（Standard Template Library）中的迭代器是一种抽象的数据访问方式，用于遍历和访问容器中的元素。迭代器提供了一种统一的访问容器元素的方式，使得算法可以独立于具体容器类型而操作。

迭代器可以看作是指向容器元素的指针，它提供了类似指针的操作，如解引用、递增、递减等。通过迭代器，我们可以遍历容器中的元素，访问和修改元素的值。

STL中的迭代器分为五种类型：

1. 输入迭代器（Input Iterator）：只能读取容器中的元素，只能单向移动，不支持修改操作。
2. 输出迭代器（Output Iterator）：只能写入容器中的元素，只能单向移动，不支持读取操作。
3. 前向迭代器（Forward Iterator）：既可以读取容器中的元素，也可以写入容器中的元素，支持单向移动。
4. 双向迭代器（Bidirectional Iterator）：具有前向迭代器的所有功能，同时支持逆向移动。
5. 随机访问迭代器（Random Access Iterator）：具有双向迭代器的所有功能，同时支持随机访问，可以像指针一样进行算术运算。

不同类型的迭代器具有不同的功能和操作特性，我们可以根据需要选择合适的迭代器类型来遍历和操作容器中的元素。

当我们谈到STL的迭代器时，我们通常指的是STL容器的迭代器，它们允许我们遍历容器中的元素。以下是一个简单的例子，展示了如何使用STL容器（例如vector）的迭代器：

#include <iostream>
#include <vector>int main() {// 创建一个整数向量std::vector<int> vec = {1, 2, 3, 4, 5};// 使用迭代器遍历向量std::vector<int>::iterator it;for (it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

在上面的例子中，我们创建了一个整数向量vec，然后使用std::vector<int>::iterator来创建一个迭代器it。我们使用begin()方法获取向量的起始迭代器，使用end()方法获取向量的终止迭代器，然后使用迭代器it遍历向量并输出每个元素的值。

这个例子展示了STL中迭代器的基本用法，它们是遍历容器中元素的重要工具。迭代器提供了一种通用的方式来访问容器中的元素，使得算法可以独立于容器类型进行操作，从而增加了STL的灵活性和通用性。

stl的仿函数

C++ STL中的仿函数（functor）是一种可调用对象，它类似于函数指针，可以被用作函数的参数，或者在算法中作为操作的方式。仿函数可以是普通函数指针、函数对象、成员函数指针等。

在STL中，仿函数通常被用于算法中，比如sort、transform等，以提供一种灵活的方式来指定操作。STL中已经定义了一些常用的仿函数，比如less（小于）、greater（大于）、plus（加法）、minus（减法）等，它们可以直接用于算法中。

此外，程序员也可以自定义仿函数，以满足自己的需求。自定义的仿函数需要满足一定的接口要求，比如重载函数调用运算符 operator()，以便能够像函数一样被调用。

使用仿函数可以使得算法更加灵活，可以自定义操作方式，使得算法可以适用于不同的场景。因此，仿函数是STL中非常重要的一部分，它为算法提供了一种通用的操作方式。

当使用仿函数时，我们可以通过定义一个函数对象来实现自定义的操作。以下是一个简单的例子，演示了如何使用仿函数来自定义排序规则：

#include <iostream>
#include <vector>
#include <algorithm>// 定义一个自定义的仿函数，用于比较两个整数的绝对值大小
struct CompareAbsolute {bool operator()(int a, int b) const {return abs(a) < abs(b);}
};int main() {std::vector<int> numbers = {3, -1, 4, -1, 5, -9, 2, -6};// 使用自定义的仿函数进行排序std::sort(numbers.begin(), numbers.end(), CompareAbsolute());// 输出排序后的结果for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

在上面的例子中，我们定义了一个名为CompareAbsolute的仿函数，它重载了函数调用运算符operator()，以实现比较两个整数的绝对值大小的操作。然后，我们在main函数中使用std::sort算法，并传入了自定义的仿函数CompareAbsolute，以实现按照绝对值大小进行排序。最后，我们输出了排序后的结果。

通过这个例子，我们可以看到如何使用自定义的仿函数来实现自定义的操作，从而使得算法更加灵活，适用于不同的需求。

stl的适配器

STL中的适配器（adapter）是一种特殊的容器或迭代器，它们通过改变容器或迭代器的接口，使其适应不同的需求。适配器可以在不改变原有代码的情况下，将容器或迭代器的接口进行转换或扩展，以满足特定的操作要求。

STL中常见的适配器有以下几种：

1. 容器适配器（Container Adapters）：容器适配器是一种特殊的容器，它基于已有的容器实现，提供了不同的接口。常见的容器适配器有栈（stack）、队列（queue）和优先队列（priority_queue）。这些适配器通过限制或改变容器的操作方式，使其符合栈、队列或优先队列的特性。

以下是一个使用STL中的栈（stack）容器适配器的简单例子：

#include <iostream>
#include <stack>int main() {std::stack<int> myStack;// 将元素压入栈myStack.push(1);myStack.push(2);myStack.push(3);// 弹出栈顶元素std::cout << "Top element: " << myStack.top() << std::endl;myStack.pop();// 再次查看栈顶元素std::cout << "Top element after pop: " << myStack.top() << std::endl;// 检查栈是否为空if (myStack.empty()) {std::cout << "Stack is empty" << std::endl;} else {std::cout << "Stack is not empty" << std::endl;}// 获取栈中元素的数量std::cout << "Stack size: " << myStack.size() << std::endl;return 0;
}

在上面的例子中，我们使用了std::stack容器适配器来创建一个栈。我们通过push方法将元素压入栈，通过top方法获取栈顶元素，通过pop方法弹出栈顶元素，通过empty方法检查栈是否为空，以及通过size方法获取栈中元素的数量。这些操作都是栈特有的操作，而std::stack容器适配器通过限制容器的操作方式，使其符合栈的特性。

2. 迭代器适配器（Iterator Adapters）：迭代器适配器是一种特殊的迭代器，它通过改变迭代器的行为，提供了不同的迭代方式。常见的迭代器适配器有插入迭代器（insert_iterator）、反向迭代器（reverse_iterator）和流迭代器（stream_iterator）。这些适配器可以在不修改原有容器的情况下，改变迭代器的行为，使其适应不同的需求。

以下是一个使用STL中的反向迭代器（reverse_iterator）的简单例子：

#include <iostream>
#include <vector>
#include <iterator>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 使用反向迭代器遍历向量std::vector<int>::reverse_iterator rit;for (rit = vec.rbegin(); rit != vec.rend(); ++rit) {std::cout << *rit << " ";}std::cout << std::endl;return 0;
}

在上面的例子中，我们使用了std::vector容器来存储一些整数。然后，我们使用std::vector<int>::reverse_iterator来创建一个反向迭代器，通过rbegin()和rend()方法分别获取向量的反向起始迭代器和反向终止迭代器。然后我们使用反向迭代器rit从向量末尾向向量开头遍历，输出了向量的元素。

反向迭代器允许我们以相反的顺序遍历容器，这在某些情况下非常有用，比如需要逆序遍历一个容器。通过使用反向迭代器，我们可以灵活地改变迭代器的行为，以满足不同的需求。

3. 函数适配器（Function Adapters）：函数适配器是一种特殊的函数对象，它通过改变函数的行为，提供了不同的操作方式。常见的函数适配器有绑定器（binder）、取反器（negator）和成员函数适配器（mem_fun）。这些适配器可以在不修改原有函数的情况下，改变函数的行为，使其适应不同的需求。

以下是一个使用STL中的函数适配器（function adapter）的简单例子：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 使用函数适配器对向量中的元素进行平方操作std::transform(vec.begin(), vec.end(), vec.begin(), std::bind2nd(std::multiplies<int>(), 2));// 输出平方后的结果for (int i : vec) {std::cout << i << " ";}std::cout << std::endl;return 0;
}

在上面的例子中，我们使用了std::transform算法和std::bind2nd函数适配器来对向量中的元素进行平方操作。std::bind2nd函数适配器将std::multiplies<int>()函数对象和第二个参数绑定在一起，这样就可以将每个元素与2相乘。然后，std::transform算法将结果存储回原始的向量中。

函数适配器允许我们以不同的方式使用函数对象，从而实现更加灵活的功能。在上面的例子中，我们使用了std::bind2nd函数适配器来绑定一个参数，实现了对向量中的元素进行平方操作。这种灵活性使得函数适配器成为STL中非常有用的工具之一。

适配器在STL中起到了非常重要的作用，它们可以使得现有的容器、迭代器或函数更加灵活，适应不同的场景和需求。通过使用适配器，我们可以在不改变原有代码的情况下，扩展或转换容器、迭代器或函数的接口，使其更加符合实际应用的要求。

迭代器和适配器的区别

迭代器（Iterator）和适配器（Adapter）是两个在STL中具有不同功能的概念。

迭代器是一种抽象的概念，它提供了一种通用的方式来遍历容器中的元素。迭代器允许我们以统一的方式访问容器中的元素，而不需要了解容器的具体实现细节。迭代器可以分为输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器，每种类型的迭代器提供了不同的功能和操作。

适配器是一种用于修改或扩展现有功能的工具。适配器将一个接口转换为另一个接口，使得原本不兼容的组件可以一起工作。在STL中，函数适配器是一种常见的适配器，它允许我们修改或扩展函数对象的行为，以满足特定的需求。函数适配器包括绑定器（binder）、成员函数适配器（mem_fun_adapter）和函数指针适配器（ptr_fun_adapter）等。

迭代器和适配器在功能和概念上有一些区别：

1. 迭代器是用于遍历容器的工具，它提供了一种统一的访问方式。适配器是用于修改或扩展现有功能的工具，它可以修改函数对象的行为或转换接口。
2. 迭代器是STL的核心概念之一，它在STL中广泛使用。适配器是STL的一个组件，它是对现有功能的扩展和修改。
3. 迭代器的主要目的是提供一种统一的访问方式，使得算法可以独立于容器类型进行操作。适配器的主要目的是修改或扩展现有功能，以满足特定的需求。

总的来说，迭代器和适配器是STL中两个不同的概念，它们分别用于遍历容器和修改或扩展功能。迭代器提供了一种统一的访问方式，而适配器则用于修改函数对象的行为或转换接口。

stl 函数适配器扩展

函数适配器是一种用于修改或扩展函数对象行为的工具。在STL中，有几种函数适配器，包括绑定器（binder）、成员函数适配器（mem_fun_adapter）和函数指针适配器（ptr_fun_adapter）。以下是这些函数适配器的一些例子：

1. 绑定器（binder）：

#include <iostream>
#include <functional>// 定义一个二元函数
int multiply(int a, int b) {return a * b;
}int main() {// 使用绑定器将一个参数绑定到函数上auto multiplyByTwo = std::bind(multiply, std::placeholders::_1, 2);// 调用绑定器函数int result = multiplyByTwo(5);std::cout << result << std::endl;  // 输出：10return 0;
}

在上面的例子中，我们定义了一个二元函数multiply，然后使用std::bind函数创建了一个绑定器multiplyByTwo，将第二个参数绑定为2。最后，我们调用绑定器函数，传入一个参数5，得到结果10。

2. 成员函数适配器（mem_fun_adapter）：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>class Person {
public:Person(int age) : age(age) {}bool isAdult() const {return age >= 18;}private:int age;
};int main() {std::vector<Person> people = {Person(25), Person(15), Person(30), Person(12)};// 使用成员函数适配器判断是否成年auto it = std::find_if(people.begin(), people.end(), std::mem_fun_ref(&Person::isAdult));if (it != people.end()) {std::cout << "Found an adult person." << std::endl;} else {std::cout << "No adult person found." << std::endl;}return 0;
}

在上面的例子中，我们定义了一个Person类，其中有一个成员函数isAdult用于判断是否成年。然后，我们创建了一个std::vector<Person>容器，并使用std::find_if算法和std::mem_fun_ref函数适配器来查找第一个成年人。

3. 函数指针适配器（ptr_fun_adapter）：

#include <iostream>
#include <algorithm>
#include <functional>// 定义一个谓词函数
bool isEven(int num) {return num % 2 == 0;
}int main() {std::vector<int> numbers = {1, 2, 3, 4, 5};// 使用函数指针适配器判断是否为偶数auto it = std::find_if(numbers.begin(), numbers.end(), std::ptr_fun(isEven));if (it != numbers.end()) {std::cout << "Found an even number." << std::endl;} else {std::cout << "No even number found." << std::endl;}return 0;
}

在上面的例子中，我们定义了一个谓词函数isEven，用于判断一个数是否为偶数。然后，我们创建了一个std::vector<int>容器，并使用std::find_if算法和std::ptr_fun函数适配器来查找第一个偶数。

以上是函数适配器的一些例子，它们可以修改或扩展函数对象的行为，使得我们可以根据特定的需求来使用它们。

容器适配器

C++ STL（标准模板库）中的容器适配器是一种特殊类型的容器，它们提供了一种特定的接口和功能，使其适用于特定的用例和算法。容器适配器通常基于标准库中的其他容器类型构建，以提供不同的行为和接口。

在C++ STL中，有三种常见的容器适配器：

1. stack（栈）：基于 deque、list 或 vector 实现的后进先出（LIFO）的数据结构。只能在栈的顶部进行插入和删除操作。

2. queue（队列）：基于 deque 或 list 实现的先进先出（FIFO）的数据结构。允许在队列的前端进行删除操作，在队列的后端进行插入操作。

3. priority_queue（优先队列）：基于 vector 实现的一种特殊队列，它根据元素的优先级进行排序。默认情况下，它是一个最大堆，可以通过自定义比较函数来实现最小堆。

这些容器适配器与标准库中的容器（如 vector、deque、list、map、set 等）的区别在于它们提供了不同的接口和行为，以满足特定的数据结构需求。容器适配器通常限制了对底层容器的访问和操作，使其更适合特定的应用场景。例如，stack 只允许在顶部进行插入和删除操作，而 queue 允许在前端进行删除操作，在后端进行插入操作。

在C++ STL中，stack容器适配器通常可以通过deque或vector实现。在默认情况下，stack使用deque作为其底层容器。这意味着stack的操作会被映射到deque的操作上。

deque（双端队列）是一种支持快速随机访问和在两端进行高效插入和删除操作的序列容器。因此，deque非常适合用作stack的底层容器。通过使用deque作为底层容器，stack可以实现后进先出（LIFO）的行为，同时具有高效的插入和删除操作。

在C++ STL中，stack使用deque作为默认底层容器的实现方式如下：

std::stack<int, std::deque<int>> myStack; // 使用deque作为底层容器

在这个例子中，stack被实例化为使用int类型的元素，并且使用deque作为其底层容器。这意味着stack的操作会被映射到deque的操作上，从而实现了stack的功能。

需要注意的是，虽然deque是stack的默认底层容器，但也可以使用vector或其他序列容器作为stack的底层容器，这取决于具体的需求和性能考虑。