文章目录
- [20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)
- [225. 用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)
- [42. 接雨水](https://leetcode-cn.com/problems/trapping-rain-water/)
- [剑指 Offer 06. 从尾到头打印链表](https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)
- [剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)
- [155. 最小栈](https://leetcode-cn.com/problems/min-stack/)
- [739. 每日温度](https://leetcode-cn.com/problems/daily-temperatures/)
20. 有效的括号
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W4p8gRAC-1631409448375)([外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pWdKsmO3-1631409804443)([外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ohgiBHVC-1631409833654)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906123907274.png#pic_center)]
#pic_center)]
char pairs(char a) {
if (a == '}') return '{';
if (a == ']') return '[';
if (a == ')') return '(';
return 0;
}
bool isValid(char* s) {
int n = strlen(s);
if (n % 2 == 1) {
return false;
}
int stk[n + 1], top = 0;
for (int i = 0; i < n; i++) {
char ch = pairs(s[i]);
if (ch) {
if (top == 0 || stk[top - 1] != ch) {
return false;
}
top--;
} else {
stk[top++] = s[i];
}
}
return top == 0;
}
---------------------------------------------------------
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if (n % 2 == 1) {
return false;
}
unordered_map<char, char> pairs = {
{')', '('},
{']', '['},
{'}', '{'}
};
stack<char> stk;
for (char ch: s) {
if (pairs.count(ch)) {
if (stk.empty() || stk.top() != pairs[ch]) {
return false;
}
stk.pop();
}
else {
stk.push(ch);
}
}
return stk.empty();
}
};
225. 用队列实现栈
#define LEN 20
typedef struct queue {
int *data;
int head;
int rear;
int size;
} Queue;
typedef struct {
Queue *queue1, *queue2;
} MyStack;
Queue *initQueue(int k) {
Queue *obj = (Queue *)malloc(sizeof(Queue));
obj->data = (int *)malloc(k * sizeof(int));
obj->head = -1;
obj->rear = -1;
obj->size = k;
return obj;
}
void enQueue(Queue *obj, int e) {
if (obj->head == -1) {
obj->head = 0;
}
obj->rear = (obj->rear + 1) % obj->size;
obj->data[obj->rear] = e;
}
int deQueue(Queue *obj) {
int a = obj->data[obj->head];
if (obj->head == obj->rear) {
obj->rear = -1;
obj->head = -1;
return a;
}
obj->head = (obj->head + 1) % obj->size;
return a;
}
int isEmpty(Queue *obj) {
return obj->head == -1;
}
MyStack *myStackCreate() {
MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
obj->queue1 = initQueue(LEN);
obj->queue2 = initQueue(LEN);
return obj;
}
void myStackPush(MyStack *obj, int x) {
if (isEmpty(obj->queue1)) {
enQueue(obj->queue2, x);
} else {
enQueue(obj->queue1, x);
}
}
int myStackPop(MyStack *obj) {
if (isEmpty(obj->queue1)) {
while (obj->queue2->head != obj->queue2->rear) {
enQueue(obj->queue1, deQueue(obj->queue2));
}
return deQueue(obj->queue2);
}
while (obj->queue1->head != obj->queue1->rear) {
enQueue(obj->queue2, deQueue(obj->queue1));
}
return deQueue(obj->queue1);
}
int myStackTop(MyStack *obj) {
if (isEmpty(obj->queue1)) {
return obj->queue2->data[obj->queue2->rear];
}
return obj->queue1->data[obj->queue1->rear];
}
bool myStackEmpty(MyStack *obj) {
if (obj->queue1->head == -1 && obj->queue2->head == -1) {
return true;
}
return false;
}
void myStackFree(MyStack *obj) {
free(obj->queue1->data);
obj->queue1->data = NULL;
free(obj->queue1);
obj->queue1 = NULL;
free(obj->queue2->data);
obj->queue2->data = NULL;
free(obj->queue2);
obj->queue2 = NULL;
free(obj);
obj = NULL;
}
-------------------------------------------------------------------------
class MyStack {
public:
queue<int> queue1;
queue<int> queue2;
MyStack() {
}
void push(int x) {
queue2.push(x);
while (!queue1.empty()) {
queue2.push(queue1.front());
queue1.pop();
}
swap(queue1, queue2);
}
int pop() {
int r = queue1.front();
queue1.pop();
return r;
}
int top() {
int r = queue1.front();
return r;
}
bool empty() {
return queue1.empty();
}
};
typedef struct tagListNode {
struct tagListNode* next;
int val;
} ListNode;
typedef struct {
ListNode* top;
} MyStack;
MyStack* myStackCreate() {
MyStack* stk = calloc(1, sizeof(MyStack));
return stk;
}
void myStackPush(MyStack* obj, int x) {
ListNode* node = malloc(sizeof(ListNode));
node->val = x;
node->next = obj->top;
obj->top = node;
}
int myStackPop(MyStack* obj) {
ListNode* node = obj->top;
int val = node->val;
obj->top = node->next;
free(node);
return val;
}
int myStackTop(MyStack* obj) {
return obj->top->val;
}
bool myStackEmpty(MyStack* obj) {
return (obj->top == NULL);
}
void myStackFree(MyStack* obj) {
while (obj->top != NULL) {
ListNode* node = obj->top;
obj->top = obj->top->next;
free(node);
}
free(obj);
}
------------------------------------------------------------------------
class MyStack {
public:
queue<int> q;
MyStack() {
}
void push(int x) {
int n = q.size();
q.push(x);
for (int i = 0; i < n; i++) {
q.push(q.front());
q.pop();
}
}
int pop() {
int r = q.front();
q.pop();
return r;
}
int top() {
int r = q.front();
return r;
}
bool empty() {
return q.empty();
}
};
42. 接雨水
int trap(vector<int>& height)
{
int ans = 0;
int size = height.size();
for (int i = 1; i < size - 1; i++) {
int max_left = 0, max_right = 0;
for (int j = i; j >= 0; j--) {
max_left = max(max_left, height[j]);
}
for (int j = i; j < size; j++) {
max_right = max(max_right, height[j]);
}
ans += min(max_left, max_right) - height[i];
}
return ans;
}
int trap(vector<int>& height)
{
if (height == null)
return 0;
int ans = 0;
int size = height.size();
vector<int> left_max(size), right_max(size);
left_max[0] = height[0];
for (int i = 1; i < size; i++) {
left_max[i] = max(height[i], left_max[i - 1]);
}
right_max[size - 1] = height[size - 1];
for (int i = size - 2; i >= 0; i--) {
right_max[i] = max(height[i], right_max[i + 1]);
}
for (int i = 1; i < size - 1; i++) {
ans += min(left_max[i], right_max[i]) - height[i];
}
return ans;
}
int trap(vector<int>& height)
{
int ans = 0, current = 0;
stack<int> st;
while (current < height.size()) {
while (!st.empty() && height[current] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty())
break;
int distance = current - st.top() - 1;
int bounded_height = min(height[current], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(current++);
}
return ans;
}
int trap(vector<int>& height)
{
int left = 0, right = height.size() - 1;
int ans = 0;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
++left;
}
else {
height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
--right;
}
}
return ans;
}
剑指 Offer 06. 从尾到头打印链表
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
stack<int> s;
vector<int> res;
ListNode* pre=head;
while(pre){
s.push(pre->val);
pre=pre->next;
}
while(!s.empty()){
res.push_back(s.top());
s.pop();
}
return res;
}
};
剑指 Offer 09. 用两个栈实现队列
class CQueue {
stack<int> stack1,stack2;
public:
CQueue() {
while (!stack1.empty()) {
stack1.pop();
}
while (!stack2.empty()) {
stack2.pop();
}
}
void appendTail(int value) {
stack1.push(value);
}
int deleteHead() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
if (stack2.empty()) {
return -1;
} else {
int deleteItem = stack2.top();
stack2.pop();
return deleteItem;
}
}
};
155. 最小栈
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int x) {
x_stack.push(x);
min_stack.push(min(min_stack.top(), x));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
739. 每日温度
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EPywWZCg-1631409448387)([外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JSdOIJAZ-1631410035291)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906131429529.png#pic_center)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ueN4ESGE-1631410028435)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906131429529.png#pic_center)]
[外链图片转存中…(img-YLbHIkti-1631410023714)]
)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4awxo6MT-1631409448387)(https://raw.githubusercontent.com/xkyvvv/blogpic/main/pic1/image-20210906131445488.png)]
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
int previousIndex = s.top();
ans[previousIndex] = i - previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)