- 栈和队列总结
class Solution {
public:
int calculate(string s) {
mp['+'] = 1;
mp['-'] = 1;
mp['*'] = 2;
mp['/'] = 2;
stack<char> ops;
ops.push('(');
stack<int> nums;
int num = 0;
int len = s.size();
for (int i = 0; i < len; ++i) {
char ch = s[i];
if (ch == ' ') {
continue;
} else if (ch == '(') {
ops.push(ch);
} else if (isNum(ch)) {
num = 0;
while (i < len && isNum(s[i])) {
num = num * 10 + (s[i] - '0');
++i;
}
nums.push(num);
--i;
} else {
calc(ops, nums, ch);
if (ch != ')') {
ops.push(ch);
}
}
}
calc(ops, nums, ')');
return nums.empty() ? 0 : nums.top();
}
bool isNum(char ch) {
return ch >= '0' && ch <= '9';
}
void calc(stack<char>& ops, stack<int>& nums, char ch) {
if (nums.size() < 2) return;
if (ops.empty()) return;
while (!ops.empty() && ops.top() != '(' && nums.size() >= 2 && (ch == ')' || mp[ops.top()] >= mp[ch])) {
int num2 = nums.top();
nums.pop();
int num1 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
nums.push(getByOp(num1, num2, op));
}
if (ch == ')' && !ops.empty() && ops.top() == '(') {
ops.pop();
}
}
int getByOp(int num1, int num2, char op) {
int num = 0;
if (op == '+') {
num = num1 + num2;
} else if (op == '-') {
num = num1 - num2;
} else if (op == '*') {
num = num1 * num2;
} else {
num = num1 / num2;
}
return num;
}
private:
unordered_map<char, int> mp;
};class Solution {
public:
int calculate(string s) {
stack<int> sta;
char flag = '$';
int num = 0;
for (char ch : s) {
if (ch == ' ') continue;
else if (ch >= '0' && ch <= '9') {
num = num * 10 + (ch - '0');
} else {
if (flag == '-') {
num = -1 * num;
} else if (flag == '*') {
num = sta.top() * num;
sta.pop();
} else if (flag == '/') {
num = sta.top() / num;
sta.pop();
}
flag = ch;
sta.push(num);
num = 0;
}
}
if (flag == '-') {
num = -1 * num;
} else if (flag == '*') {
num = sta.top() * num;
sta.pop();
} else if (flag == '/') {
num = sta.top() / num;
sta.pop();
}
sta.push(num);
int res = 0;
while (!sta.empty()) {
res += sta.top();
sta.pop();
}
return res;
}
};设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) -- 将元素 x 推入栈中。
- pop() -- 删除栈顶的元素。
- top() -- 获取栈顶元素。
- getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
容易想到的解法是：每次getMin的时候，遍历栈中的元素，找到最小元素并返回。这样getMin是线性的时间复杂度，不符合要求。
优化解法：开辟一个辅助栈sta2，它的栈顶元素始终是当前数据栈sta中的最小元素。为达到这个要求，在每次push(x)时，比较x和sta2.top()，如果x >= sta2.top()，则sta中的最小元素不变，将sta2.top()压入sta2；如果x < sta2.top()，则更新当前栈中最小元素，将x压入sta2。那么，在getMin时，返回sta2的栈顶元素即可，为常数时间复杂度。
- 时间复杂度：
push,pop和getMin为O(1) - 空间复杂度：O(n)
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if(sta1.empty())
{
sta2.push(x);
}
else{
if(x >= sta2.top())
sta2.push(sta2.top());
else
sta2.push(x);
}
sta1.push(x);
}
void pop() {
sta1.pop();
sta2.pop();
}
int top() {
if(sta1.empty())
return -1;
return sta1.top();
}
int getMin() {
if(sta2.empty()) throw range_error("empty stack!");
return sta2.top();
}
private:
stack<int> sta1,sta2;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/优化：只使用一个栈
思路：解答 中的解答二
class MinStack {
public:
MinStack() {
min_element = INT_MAX;
}
void push(int val) {
if (val <= min_element) {
sta.push(min_element);
min_element = val;
}
sta.push(val);
}
void pop() {
if (sta.top() == min_element) {
sta.pop();
min_element = sta.top();
}
sta.pop();
}
int top() {
return sta.top();
}
int getMin() {
return min_element;
}
private:
stack<int> sta;
int min_element;
};
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意:空字符串可被认为是有效字符串。
示例 1:
输入: "()[]{}"
输出: true
示例 2:
输入: "(]"
输出: false
示例 3:
输入: "([)]"
输出: false
定义一个栈sta，遍历字符串，每当遇到[或(或{，则入栈；每当遇到]或)或},就从栈中弹出一个字符，判断是否和当前字符匹配。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution {
public:
bool isValid(string s) {
if(s.empty())
return true;
stack<char> sta;
for(auto ch : s)
{
if(ch=='(' || ch=='[' || ch=='{')
sta.push(ch);
if(ch==']' || ch==')' || ch=='}')
{
if(sta.empty())
return false;
char tmp=sta.top();
sta.pop();
if((ch==']' && tmp!='[')||(ch==')' && tmp!='(')||(ch=='}' && tmp!='{'))
return false;
}
}
if(!sta.empty())
return false;
return true;
}
};根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6
示例 3：
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
开辟一个栈sta，遍历字符串，对于遍历的每一个字符s，处理情况如下：
- 如果
s是+,-,*,/中的一个，则弹出栈的两个元素num1和num2，根据运算符计算局部结果res，例如如果运算符为*，则res = num1 * num2。然后将res压入栈； - 否则，
s代表的是数字，将s转换成数字压入栈中。
遍历结束后，sta栈顶元素即为所求。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution:
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
sta = []
for s in tokens:
if s == "+" or s == "-" or s == "*" or s == "/":
num2 = sta[-1]
sta.pop()
num1 = sta[-1]
sta.pop()
if s == "+":
res = num1 + num2
elif s == "-":
res = num1 - num2
elif s == "*":
res = num1 * num2
elif s == "/":
res = int(num1 / num2)
sta.append(res)
else:
sta.append(int(s))
return sta[-1]
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1:
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2:
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3:
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/"
输出："/c"
首先将字符串path末尾的所有/清除，维护一个栈结构（类型为string），然后从前往后遍历path，遍历过程中分几种情况处理：
- 遇到两个
/之间的字符串，则将它压入栈； - 遇到
..，则栈中弹出一个元素； - 其他情况，例如遇到
/和.,则不处理，继续向前。
最后将栈中剩下的字符串通过/连接起来，就得到了结果。
特殊情况：多个/连续；/../
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution {
public:
string simplifyPath(string path) {
if(path.size() == 0) return "";
if(path.size() == 1) return "/";
while(path.back() == '/')
path.pop_back();
if(path.size() == 0 || path.size() == 1) return "/";
int len = path.size();
vector<string> vec;
string res("");
int idx = 0;
while(idx < len && path[idx] == '/') idx++;
string tmp;
while(idx < len)
{
char ch = path[idx];
if(ch != '/')
{
tmp += ch;
idx++;
}
else if(ch == '/')
{
while(idx < len && path[idx] == '/') idx++;
if(tmp == "..")
{
if(!vec.empty())
{
vec.pop_back();
}
}
else if(tmp != ".")
{
vec.push_back(tmp);
}
tmp.clear();
}
}
if(tmp == "..")
{
if(!vec.empty())
vec.pop_back();
}
else if(tmp != ".")
{
vec.push_back(tmp);
}
if(vec.empty())
return "/";
else{
for(int i=0;i<vec.size();i++)
{
res += "/" + vec[i];
}
}
return res;
}
};设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作：
- MyCircularQueue(k): 构造器，设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空，返回 -1 。
- Rear: 获取队尾元素。如果队列为空，返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为3
circularQueue.enQueue(1); // 返回true
circularQueue.enQueue(2); // 返回true
circularQueue.enQueue(3); // 返回true
circularQueue.enQueue(4); // 返回false,队列已满
circularQueue.Rear(); // 返回3
circularQueue.isFull(); // 返回true
circularQueue.deQueue(); // 返回true
circularQueue.enQueue(4); // 返回true
circularQueue.Rear(); // 返回4
注意：
- 所有的值都在 1 至 1000 的范围内；
- 操作数将在 1 至 1000 的范围内；
- 请不要使用内置的队列库。
开辟一个固定大小为k+1的数组arr，可以在队列中容纳k个元素，同时定义两个指针first和rear，first指向循环队列队首，rear指向循环队列队尾后一个位置，初始化first = rear = 0，计算first在数组的索引位置是first % (k + 1)，计算rear在数组的索引位置是(rear - 1) % (k + 1)，那么：
- 当队列队尾压入元素时，
arr[rear++] = value； - 当队列队首弹出元素时，
first++； - 当
first % (k + 1) == rear % (k + 1)时，队列为空； - 当
first % (k + 1) == (rear + 1) % (k + 1)时，队列满。
class MyCircularQueue {
public:
/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue(int k) {
arr.resize(k+1);
first = rear = 0;
size = k + 1;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
bool enQueue(int value) {
if(isFull())
return false;
arr[rear % size] = value;
rear++;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
bool deQueue() {
if(isEmpty())
return false;
int res = first % size;
first++;
return true;
}
/** Get the front item from the queue. */
int Front() {
if(isEmpty())
return -1;
return arr[first % size];
}
/** Get the last item from the queue. */
int Rear() {
if(isEmpty())
return -1;
return arr[(rear - 1) % size];
}
/** Checks whether the circular queue is empty or not. */
bool isEmpty() {
if(first % size == rear % size)
return true;
return false;
}
/** Checks whether the circular queue is full or not. */
bool isFull() {
if((rear + 1) % size == first % size)
return true;
return false;
}
private:
vector<int> arr;
int first;
int rear;
int size;
};
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* bool param_1 = obj.enQueue(value);
* bool param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* bool param_5 = obj.isEmpty();
* bool param_6 = obj.isFull();
*/设计实现双端队列。 你的实现需要支持以下操作：
- MyCircularDeque(k)：构造函数,双端队列的大小为k。
- insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
- insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
- deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
- deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
- getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
- getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
- isEmpty()：检查双端队列是否为空。
- isFull()：检查双端队列是否满了。
示例：
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4
注意：
- 所有值的范围为 [1, 1000]
- 操作次数的范围为 [1, 1000]
- 请不要使用内置的双端队列库。
开辟一个固定大小为k+1的数组vec，可以在队列中容纳k个元素，同时定义两个指针first和rear，first指向循环队列队首，rear指向循环队列队尾后一个位置，初始化first = rear = 0，计算first在数组的索引位置是first % (k + 1)，计算rear在数组的索引位置是(rear - 1) % (k + 1)，那么：
- 当队列队首压入元素时，则
first = (first - 1 + size) % size，然后vec[first] = value； - 当队列队尾压入元素时，则
vec[rear] = value,然后rear = (rear + 1) % size； - 当队列队首弹出元素时，如果队列为空，直接返回；否则，
first = (first + 1) % size； - 当队列队尾弹出元素时，如果队列为空，直接返回；否则，
rear = (rear - 1 + size) % size； - 当
first % (k + 1) == rear % (k + 1)时，队列空； - 当
first % (k + 1) == (rear + 1) % (k + 1)时，队列满。
class MyCircularDeque {
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k) {
vec.resize(k + 1);
size = k + 1;
first = rear = 0;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if(isFull())
return false;
first = (first - 1 + size) % size;
vec[first] = value;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if(isFull())
return false;
vec[rear] = value;
rear = (rear + 1) % size;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if(isEmpty())
return false;
first = (first + 1) % size;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if(isEmpty()) return false;
rear = (rear - 1 + size) % size;
return true;
}
/** Get the front item from the deque. */
int getFront() {
if(isEmpty()) return -1;
return vec[first % size];
}
/** Get the last item from the deque. */
int getRear() {
if(isEmpty()) return -1;
if(rear == 0)
return vec[size - 1];
return vec[(rear - 1) % size];
}
/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
if(first % size == rear % size)
return true;
return false;
}
/** Checks whether the circular deque is full or not. */
bool isFull() {
if((rear + 1) % size == first % size)
return true;
return false;
}
private:
vector<int> vec;
int size,first,rear;
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* bool param_1 = obj.insertFront(value);
* bool param_2 = obj.insertLast(value);
* bool param_3 = obj.deleteFront();
* bool param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* bool param_7 = obj.isEmpty();
* bool param_8 = obj.isFull();
*/给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
注意：
你可以假设 k 总是有效的，1 ≤ k ≤ 输入数组的大小，且输入数组不为空。
进阶：
你能在线性时间复杂度内解决此题吗？
维护一个双端队列deq，从前往后遍历数组nums的每一个元素nums[i]：
- 当
0 <= i < k时，从队列尾部开始逐个删除小于nums[i]的元素，然后将i压入队尾； - 当
k <= i < len，先得到队列首部元素tmp，它代表当前滑动窗口的最大值在数组中的索引，然后将nums[tmp]放入结果。然后同样地，从队列尾部开始逐个删除小于nums[i]的元素，然后将i压入队尾。之后，判断i - deq.front()是否大于k-1(即滑动窗口大小大于k)：如果是，那么滑动窗口从队首开始逐个删除元素直到i - deq.front() < k；否则，跳过。
遍历结束后，队列deq中的元素是每个滑动窗口的最大值在数组中的索引，逐个取出队首元素a，然后将nums[a]放入结果，就得到了所有的滑动窗口的最大值。
- 时间复杂度：O(n)
- 空间复杂度：O(k)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.empty())
return vector<int>();
vector<int> res;
deque<int> deq;
for(int i=0;i<k;i++)
{
while(!deq.empty() && nums[i] > nums[deq.back()])
deq.pop_back();
deq.push_back(i);
}
for(int i=k;i<nums.size();i++)
{
int tmp = deq.front();
res.push_back(nums[tmp]);
while(!deq.empty() && nums[i] > nums[deq.back()])
deq.pop_back();
deq.push_back(i);
while(i - deq.front() >= k)
deq.pop_front();
}
if(!deq.empty())
{
int a = deq.front();
res.push_back(nums[a]);
}
return res;
}
};