网站分辨率兼容怎么做,营销型网站教程,南阳做个网站多少钱,网站建设与管理办法总的链接
面试经典 150 题 - 学习计划 - 力扣#xff08;LeetCode#xff09;全球极客挚爱的技术成长平台 关于栈 -- stack 的学习链接
c的STL中的栈 -- stack-CSDN博客
20 . 有效的括号 这题直接用栈模拟就好了;
这里用一种取巧的方法 , 当遇见左括号#xff0c;加入右…总的链接
面试经典 150 题 - 学习计划 - 力扣LeetCode全球极客挚爱的技术成长平台 关于栈 -- stack 的学习链接
c的STL中的栈 -- stack-CSDN博客
20 . 有效的括号 这题直接用栈模拟就好了;
这里用一种取巧的方法 , 当遇见左括号加入右括号遇到右括号直接判断栈顶元素是不是与当前元素相等(这样可以避免再开一个哈希表来存相应括号之间的映射关系),相等的话pop栈顶否则直接return false;
class Solution {
public:bool isValid(string s) {stackchar st ;for(char c : s){if(c() st.push());else if(c[) st.push(]);else if(c{) st.push(});else if(st.empty() || st.top()!c) return false;else st.pop();}return st.empty() ;}
};
71 . 简化路径
先求出夹在两个/之间的目录名根据题意对于空或 . 都不用管然后用栈模拟如果不是..,那么直接入栈是..的话弹出栈顶的字符串;
class Solution {
public:vectorstring get(string p,char ch){vectorstring ans ;string cur ;for(char c : p){if(c ch){ans.push_back(cur);cur.clear();}else{cur c ;}}ans.push_back(cur);return ans ;}string simplifyPath(string path) {vectorstring p get(path,/);vectorstring stk ;for(string s : p){if(s..){if(!stk.empty())stk.pop_back();}else if(!s.empty() s!.){stk.push_back(s);}}string ans ;if(stk.empty()){ans /;}else{for(string s : stk){ans / s ;}}return ans ;}
};
155 . 最小栈
用一个栈来模拟正常的操作用一个递减的栈来维护栈顶为当前序列的最小元素;
详情请看代码 :
class MinStack {
public:stackint mi,st;MinStack() {mi.push(INT_MAX) ;}void push(int val) {st.push(val) ;mi.push(min(val,mi.top()));}void pop() {st.pop();mi.pop();}int top() {return st.top() ;}int getMin() {return mi.top() ;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj new MinStack();* obj-push(val);* obj-pop();* int param_3 obj-top();* int param_4 obj-getMin();*/
150 . 逆波兰表达式求值
栈的典型例题如果是运算符就取出栈顶两位元素进行运算然后将结果压入栈中如果是数字直接压入栈中最后返回栈顶元素即为运算结果 ;
typedef long long LL ;
class Solution {
public:int evalRPN(vectorstring tokens) {stackLL st ;for(string s : tokens){if(s ||s- ||s* ||s/){LL x st.top();st.pop() ;LL y st.top();st.pop();if(s) st.push(xy);else if(s-) st.push(y-x);else if(s*) st.push(1LL * y * x);else st.push(y / x);}else{st.push(stoll(s));}}return st.top() ;}
};
224 . 基本计算器
直接用栈模拟 ;
class Solution {
public:void replace(string s){int pos s.find( );while (pos ! -1) {s.replace(pos, 1, );pos s.find( );}}int calculate(string s) {// 存放所有的数字stackint nums;// 为了防止第一个数为负数先往 nums 加个 0nums.push(0);// 将所有的空格去掉replace(s);// 存放所有的操作包括 /-stackchar ops;int n s.size();for(int i 0; i n; i) {char c s[i];if(c ()ops.push(c);else if(c )) {// 计算到最近一个左括号为止while(!ops.empty()) {char op ops.top();if(op ! ()calc(nums, ops);else {ops.pop();break;}}}else {if(isdigit(c)) {int cur_num 0;int j i;// 将从 i 位置开始后面的连续数字整体取出加入 numswhile(j n isdigit(s[j]))cur_num cur_num*10 (s[j] - 0);// 注意上面的计算一定要有括号否则有可能会溢出nums.push(cur_num);i j-1;}else {if (i 0 (s[i - 1] ( || s[i - 1] || s[i - 1] -)) {nums.push(0);}// 有一个新操作要入栈时先把栈内可以算的都算了while(!ops.empty() ops.top() ! ()calc(nums, ops);ops.push(c);}}}while(!ops.empty())calc(nums, ops);return nums.top();}void calc(stackint nums, stackchar ops) {if(nums.size() 2 || ops.empty())return;int b nums.top(); nums.pop();int a nums.top(); nums.pop();char op ops.top(); ops.pop();nums.push(op ? ab : a-b);}
};
