C++学习记录-旧题新做-堆盘子

旧题记录：

https://blog.csdn.net/chamao_/article/details/143775934?fromshare=blogdetail&sharetype=blogdetail&sharerId=143775934&sharerefer=PC&sharesource=chamao_&sharefrom=from_link

C++解法：

class StackOfPlates { private: vector<vector<int>> stacks; int cap; public: StackOfPlates(int cap) { this -> cap = cap; } void push(int val) { if (cap == 0) return; if (stacks.empty() || stacks.back().size() == cap) { stacks.push_back(vector<int>()); } stacks.back().push_back(val); } int pop() { if (stacks.empty()) return -1; int val = stacks.back().back(); stacks.back().pop_back(); if (stacks.back().empty()) { stacks.pop_back(); } return val; } int popAt(int index) { if (index < 0 || index >= stacks.size() || stacks[index].empty()) return -1; int val = stacks[index].back(); stacks[index].pop_back(); if (stacks[index].empty()) { stacks.erase(stacks.begin() + index); } return val; } }; /** * Your StackOfPlates object will be instantiated and called as such: * StackOfPlates* obj = new StackOfPlates(cap); * obj->push(val); * int param_2 = obj->pop(); * int param_3 = obj->popAt(index); */

今天来了解vector的常用接口：

一、vector 是什么（一句话）

std::vector<T>

👉动态连续数组

• 内存连续

• 支持随机访问O(1)

• 尾部插入 / 删除高效

二、容量 & 状态相关（非常常用）

1️⃣ size()

v.size();

• 返回当前元素个数

• 类型是size_t（无符号）

⚠️ 注意：

for (int i = 0; i < v.size(); ++i) // 潜在警告

更安全：

for (size_t i = 0; i < v.size(); ++i)

2️⃣ empty()

v.empty();

• 是否为空

• 比size() == 0更语义化

3️⃣ capacity()

v.capacity();

• 当前分配的最大容量

• ≥ size()

4️⃣ reserve(n)

v.reserve(100);

• 提前分配内存

• 避免频繁扩容（性能优化）

⚠️ 不改变 size！

5️⃣ resize(n)

v.resize(5);

• 改变size

• 扩大 → 用默认值填充

• 缩小 → 多余元素被销毁

三、元素访问（刷题必会）

6️⃣ operator[]

v[i];

• O(1)

• 不做越界检查（最快）

7️⃣ at()

v.at(i);

• 越界会抛std::out_of_range

• 调试时更安全

8️⃣ front() / back()

v.front(); // 第一个 v.back(); // 最后一个

⚠️ vector 不能为空！

9️⃣ data()

int* p = v.data();

• 返回底层连续内存指针

• 可与 C API / memcpy 交互

四、修改元素（核心操作）

🔟 push_back()

v.push_back(x);

• 尾插

• 均摊 O(1)

1️⃣1️⃣ emplace_back()

v.emplace_back(1, 2);

• 原地构造

• 避免临时对象（性能更优）

1️⃣2️⃣ pop_back()

v.pop_back();

• 删除最后一个

• 不返回值

1️⃣3️⃣ insert()

v.insert(v.begin() + i, x);

• 在任意位置插入

• O(n)（元素搬移）

1️⃣4️⃣ erase()

v.erase(v.begin() + i);

或区间：

v.erase(v.begin(), v.begin() + 3);

• 删除元素

• 后续元素前移

1️⃣5️⃣ clear()

v.clear();

• 清空所有元素

• capacity 不变

五、迭代器相关（工程 & STL 算法）

1️⃣6️⃣ begin() / end()

for (auto it = v.begin(); it != v.end(); ++it) { ... }

1️⃣7️⃣ rbegin() / rend()

for (auto it = v.rbegin(); it != v.rend(); ++it) { ... }

1️⃣8️⃣ cbegin() / cend()

for (auto it = v.cbegin(); it != v.cend(); ++it) { ... }

• 返回const_iterator

六、赋值 & 构造相关

1️⃣9️⃣ 构造函数

vector<int> v1; // 空 vector<int> v2(5); // 5 个 0 vector<int> v3(5, 3); // 5 个 3 vector<int> v4 = {1,2,3}; // 初始化列表 vector<int> v5(v4); // 拷贝构造

2️⃣0️⃣ assign()

v.assign(5, 10); // 5 个 10

2️⃣1️⃣ swap()

v1.swap(v2);

• O(1)

• 常用于快速清空内存

vector<int>().swap(v);