- 栈和队列总结
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;
}
};