企业官网建设流程全解析

凡科网站教程,做设计在哪个网站找图片,注册网站给谁交钱,wordpress引入php文件栈是一种“后进先出#xff08;LIFO#xff09;”的线性数据结构#xff0c;核心优势是高效处理“匹配、抵消、嵌套”类问题。在字符串处理#xff08;去重、回退、解码#xff09;、表达式计算、栈序列验证等场景中#xff0c;栈能将复杂的顺序逻辑简化为直观的入栈/出栈…栈是一种“后进先出LIFO”的线性数据结构核心优势是高效处理“匹配、抵消、嵌套”类问题。在字符串处理去重、回退、解码、表达式计算、栈序列验证等场景中栈能将复杂的顺序逻辑简化为直观的入栈/出栈操作。本文通过5道经典题目拆解栈在不同场景下的解题思路与代码实现。一、删除字符串中的所有相邻重复项题目描述给定字符串s反复删除相邻且相同的字符对直到无法再删除返回最终字符串删除操作会重复进行直到没有相邻重复项。示例输入s abbaca输出cabb删去→aacaaa删去→ca解题思路用栈模拟“相邻抵消”过程遍历字符串的每个字符若栈不为空且栈顶字符与当前字符相同弹出栈顶抵消重复项若栈为空或字符不同将当前字符入栈。遍历结束后栈中剩余字符即为结果。完整代码classSolution{public:stringremoveDuplicates(string s){string ret;// 用string模拟栈效率更高for(autoch:s){if(ret.size()chret.back())ret.pop_back();elseret.push_back(ch);}returnret;}};复杂度分析时间复杂度O(n)O(n)O(n)n为字符串长度每个字符最多入栈/出栈一次。空间复杂度O(n)O(n)O(n)最坏情况无重复字符栈存储所有字符。二、比较含退格的字符串题目描述给定两个字符串s和t其中#表示退格键删除前一个字符判断处理后的两个字符串是否相等。示例输入s ab#c, t ad#c输出true均处理为ac输入s a#c, t b输出false处理后分别为c和b解题思路用栈模拟“退格”过程分别处理两个字符串后比较结果定义辅助函数changeStr遍历字符串遇到非#字符入栈遇到#且栈非空则出栈。分别处理s和t比较处理后的字符串是否相等。完整代码classSolution{public:boolbackspaceCompare(string s,string t){returnchangeStr(s)changeStr(t);}stringchangeStr(strings){string tmp;// 用string模拟栈for(autoch:s){if(ch!#)tmpch;else{if(tmp.size())tmp.pop_back();}}returntmp;}};复杂度分析时间复杂度O(nm)O(nm)O(nm)n/m分别为s/t的长度遍历处理两个字符串。空间复杂度O(nm)O(nm)O(nm)存储处理后的两个字符串。三、基本计算器 II题目描述实现一个基本计算器计算包含、-、*、/的字符串表达式的值表达式不含括号仅包含非负整数和空格。示例输入s 32*2输出7输入s 3/2 输出1解题思路用栈处理“加减延迟计算乘除立即计算”的优先级逻辑初始化栈和运算符op默认遍历表达式跳过空格遇到数字解析完整数值tmp根据当前运算符处理数值数值入栈-负数值入栈*//弹出栈顶数值与当前数值计算后重新入栈。遍历结束后栈中所有数值求和即为结果。完整代码classSolution{public:intcalculate(string s){vectorintst;// 用vector模拟栈inti0,ns.size();intop;// 记录当前运算符初始为while(in){if(s[i] )i;// 跳过空格elseif(s[i]0s[i]9){// 解析完整数字inttmp0;while(ins[i]0s[i]9)tmptmp*10(s[i]-0);// 根据运算符处理if(op)st.push_back(tmp);elseif(op-)st.push_back(-tmp);elseif(op*)st.back()*tmp;elsest.back()/tmp;// 题目保证除数不为0}elseops[i];// 更新运算符}// 求和得到结果intret0;for(autox:st)retx;returnret;}};复杂度分析时间复杂度O(n)O(n)O(n)n为表达式长度每个字符仅遍历一次。空间复杂度O(n)O(n)O(n)栈存储中间计算结果最坏情况存储所有加减项。四、字符串解码题目描述给定编码字符串格式如k[encoded_string]表示将encoded_string重复k次返回解码后的字符串。示例输入s 3[a]2[bc]输出aaabcbc输入s 3[a2[c]]输出accaccacc解题思路用两个栈分别存储“重复次数”和“待拼接的字符串”处理嵌套解码初始化数字栈nums和字符串栈st初始压入空字符串简化拼接逻辑遍历字符串遇到数字解析完整数字压入nums遇到[解析后续的字母串压入st遇到]弹出栈顶字符串和重复次数将字符串重复后拼接到新的栈顶遇到字母直接拼接到栈顶字符串。遍历结束后栈顶字符串即为结果。完整代码classSolution{public:stringdecodeString(string s){stackintnums;// 存储重复次数stackstringst;// 存储待拼接的字符串st.push();// 初始空串避免栈空判断inti0,ns.size();while(in){if(s[i]0s[i]9){// 解析完整数字inttmp0;while(s[i]0s[i]9)tmptmp*10(s[i]-0);nums.push(tmp);}elseif(s[i][){i;// 解析[]内的字母串string tmp;while(s[i]as[i]z)tmps[i];st.push(tmp);}elseif(s[i]]){// 弹出并重复拼接string tmpst.top();st.pop();intknums.top();nums.pop();while(k--){st.top()tmp;}i;}else{// 直接拼接字母string tmp;while(s[i]as[i]z)tmps[i];st.top()tmp;}}returnst.top();}};复杂度分析时间复杂度O(L)O(L)O(L)L为解码后字符串的总长度重复拼接的总操作数。空间复杂度O(L)O(L)O(L)栈存储中间字符串和数字。五、验证栈序列题目描述给定两个整数序列pushed和popped判断是否可以通过对pushed执行入栈操作按popped的顺序执行出栈操作。示例输入pushed [1,2,3,4,5], popped [4,5,3,2,1]输出true输入pushed [1,2,3,4,5], popped [4,3,5,1,2]输出false解题思路模拟栈的入栈/出栈过程遍历pushed数组将元素依次入栈每次入栈后检查栈顶是否与popped的当前元素匹配若匹配弹出栈顶popped指针后移遍历结束后若popped指针遍历完所有元素说明序列合法。完整代码classSolution{public:boolvalidateStackSequences(vectorintpushed,vectorintpopped){stackintst;inti0,npopped.size();for(autox:pushed){st.push(x);// 尽可能出栈while(st.size()popped[i]st.top()){st.pop();i;}}returnin;// 所有出栈操作完成则合法}};复杂度分析时间复杂度O(n)O(n)O(n)n为序列长度每个元素最多入栈/出栈一次。空间复杂度O(n)O(n)O(n)最坏情况栈存储所有元素。