- 0. Leetcode [1441. 用栈 *** 作构建数组](https://leetcode.cn/problems/build-an-array-with-stack-operations/)
- 分析与解答
- 1. Leetcode [1021. 删除最外层的括号](https://leetcode.cn/problems/remove-outermost-parentheses/)
- 分析与解答
- 2. Leetcode [1700. 无法吃午餐的学生数量](https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/)
- 分析与解答
- 3. Leetcode [1381. 设计一个支持增量 *** 作的栈](https://leetcode.cn/problems/design-a-stack-with-increment-operation/)
- 分析与解答
- 总结
分析与解答给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3…, n} 中依序读取一个数字。
请使用下述 *** 作来构建目标数组 target ：
Push：从 list 中读取一个新元素， 并将其推入数组中。
Pop：删除数组中的最后一个元素。
如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
请返回构建目标数组所用的 *** 作序列。
题目数据保证答案是唯一的。
由于题目要求依序读取数字，因此每次调用 Push 将数字放入数组，若该数字不在 target 中，则调用 Pop d出，若该数字在 target 中，继续判断下一个即可：
class Solution {
public:
vector buildArray(vector& target, int n) {
// 依序放入数字 1-n
// 若数字 i 不在 target 中，放入后 pop，否则继续
vector result;
int tarIdx(0);
for (int i = 1; i <= n; ++i) {
result.push_back("Push"); // 所有数字均先 push
// 判断是否需要 pop
if (i == target[tarIdx]) {
tarIdx++;
if (tarIdx == target.size()) {
break;
}
} else {
result.push_back("Pop");
}
}
return result;
}
};
算法时间复杂度为 O ( N ) O(N) O(N)
1. Leetcode 1021. 删除最外层的括号分析与解答有效括号字符串为空 “”、“(” + A + “)” 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。
例如，“”，“()”，“(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 s，考虑将其进行原语化分解，使得： s = P 1 + P 2 + . . . + P k s = P_1 + P_2 + ... + P_k s=P1+P2+...+Pk，其中 P i P_i Pi 是有效括号字符串原语。
对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。
由于栈可以匹配括号，一开始做题时想用该方法直接匹配括号构造结果字符串，但发现该方法无法处理形如 ((())) 的原语，因此改变思路，只要用该方法找出原语在字符串中的起始与结束下标，就可以直接将字符串字串放入结果中：
class Solution {
public:
const char leftCh = '(';
const char rightCh = ')';
string removeOuterParentheses(string s) {
// 用栈找出每个原语后删除最外层括号即可
string result;
stack st;
int oriS(0);
int oriCount(0);
for (int i = 0; i < s.size(); ++i) {
if (s[i] == leftCh) {
// 按规则，栈为空时应该遇到左括号
// 直接放入左括号
st.push(s[i]);
} else {
// 由于字符匹配，栈中只可能有左括号
// 遇到右括号，从栈中弹出一个左括号
st.pop();
if (st.size() == 0) {
// 找到一个原语
oriCount = i - oriS + 1; // 原语长度
// 去除原语最外层括号
result += s.substr(oriS + 1, oriCount - 2);
oriS = i + 1; // 移动原语起始偏移
}
}
}
return result;
}
};
算法时间复杂度为 O ( N ) O(N) O(N)
2. Leetcode 1700. 无法吃午餐的学生数量分析与解答学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：
如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。
对该题使用模拟法即可。使用队列模拟学生队列；使用指针模拟三明治栈。若学生队列队首元素与三明治栈顶元素匹配，则d出队首元素与栈顶元素；若不匹配则d出队首元素并将队首元素送入队尾。重复上述 *** 作，直至所有元素匹配完成或不匹配数量与队列长度相等为止，此时学生队列长度即为最终答案：
class Solution {
public:
int countStudents(vector& students, vector& sandwiches) {
int noSatisfy(0); // 无人取走三明治的次数
int sanIdx(0); // 当前三明治下标
// 构造队列
deque st;
for (auto stu: students) {
st.push_back(stu);
}
while (sanIdx < sandwiches.size()) { // 对所有三明治进行匹配
if (st.front() == sandwiches[sanIdx]) {
// 匹配成功
st.pop_front();
sanIdx++;
// 有人取走，重置计数器
noSatisfy = 0;
} else {
// 匹配失败
int stu = st.front();
st.pop_front();
st.push_back(stu);
// 无人取走，计数器+1
noSatisfy++;
// 计数器与队列大小相等时表明无人取走
if (noSatisfy == st.size()) {
break;
}
}
}
return st.size();
}
};
分析与解答请你设计一个支持下述 *** 作的栈。
实现自定义栈类 CustomStack ：
CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，栈在增长到 maxSize 之后则不支持 push *** 作。
void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
int pop()：d出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。
为实现栈 *** 作，我们只需要一个数组与栈顶元素指针即可。
- 由于最大大小不确定，因此可以使用指针实现数组，在初始化时分配内存。
push*** 作需要比较当前元素与maxSize的大小，因此需要记录maxSize，添加元素x即将栈顶指针向后移动并放入xpop*** 作d出元素，将栈顶指针位置向前移动并返回栈顶指针位置 + 1 处的元素即可- 为改变栈底的
k个元素，只需要从指针头空间开始向后寻找k个改变即可
class CustomStack {
int* _data;
int _topIdx; // 栈顶元素位置
int _maxSize;
public:
CustomStack(int maxSize)
: _data(nullptr)
, _topIdx(-1)
, _maxSize(maxSize)
{
_data = new int[maxSize];
}
~CustomStack() {
delete[] _data;
}
void push(int x) {
// 栈内元素没超过指定大小，可以放入 x
if (_topIdx < _maxSize - 1) {
_topIdx++;
_data[_topIdx] = x;
}
}
int pop() {
// 栈顶元素不为空，弹出
if (_topIdx >= 0) {
int idx = _topIdx;
_topIdx--;
return _data[idx];
} else {
return -1;
}
}
void increment(int k, int val) {
// 要改变的元素数量
int num = k > _topIdx? _topIdx + 1: k;
// 改变栈底 num 个元素
for (int i = 0; i < num; ++i) {
_data[i] += val;
}
}
};
/**
* Your CustomStack object will be instantiated and called as such:
* CustomStack* obj = new CustomStack(maxSize);
* obj->push(x);
* int param_2 = obj->pop();
* obj->increment(k,val);
*/
今天的题目难度都不高，最后一个设计题很有意思，值得尝试~
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）