广安市网站建设公司南通网站排名

当前位置： 首页 > news >正文

广安市网站建设公司,南通网站排名,网站内容管理系统使用说明书,医疗器械网站建设方案算法沉淀——栈 01.删除字符串中的所有相邻重复项02.比较含退格的字符串03.基本计算器 II04.字符串解码05.验证栈序列 栈#xff08;Stack#xff09;是一种基于先进后出#xff08;Last In, First Out#xff0c;LIFO#xff09;原则的数据结构。栈具有两个主要的操作Stack是一种基于先进后出Last In, First OutLIFO原则的数据结构。栈具有两个主要的操作 压栈Push将元素添加到栈的顶部。出栈Pop从栈的顶部移除元素。 栈常常用于需要反转操作顺序的场景或者在需要记录操作历史的情况下。在算法中栈的应用广泛以下是一些典型的栈算法 括号匹配问题使用栈来检查表达式中的括号是否匹配例如检查 ()、[]、{} 是否正确嵌套。逆波兰表达式求值通过栈来实现对逆波兰表达式的求值其中操作数和操作符都存储在栈中。函数调用栈在编程语言中函数调用时的执行过程通常使用函数调用栈Call Stack来管理。深度优先搜索DFS在图或树的遍历过程中使用栈来实现深度优先搜索。迭代法求解二叉树的前序、中序、后序遍历通过栈来模拟递归过程实现二叉树的不同遍历方式。表达式求值将中缀表达式转换为后缀表达式然后使用栈求解后缀表达式的值。迷宫求解通过栈来记录路径实现对迷宫的求解过程。 栈的特性使其在某些问题场景中非常有效和方便。在算法设计和实现中栈通常用于临时存储数据、回溯操作、深度优先搜索等。 01.删除字符串中的所有相邻重复项 题目链接https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/ 给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母并删除它们。 在 S 上反复执行重复项删除操作直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例 输入abbaca 输出ca 解释 例如在 abbaca 中我们可以删除 bb 由于两字母相邻且相同这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 aaca其中又只有 aa 可以执行重复项删除操作所以最后的字符串为 ca。提示 1 S.length 20000S 仅由小写英文字母组成。 思路 这里使用栈的思想可以很好的解决这个问题我们每插入一个字符前进行对比如果栈顶存在该字符则删除栈顶字符且不插入否则插入字符最后留在栈中的字符就是需要返回的考虑到字符顺序的问题我们可以直接用字符串来直接模拟栈。 代码 class Solution { public:string removeDuplicates(string s) {string ret;for(int i0;is.size();i){if(ret.size()s[i]ret.back()) ret.pop_back();else rets[i];}return ret;} };02.比较含退格的字符串 题目链接https://leetcode.cn/problems/backspace-string-compare/ 给定 s 和 t 两个字符串当它们分别被输入到空白的文本编辑器后如果两者相等返回 true 。# 代表退格字符。 注意如果对空文本输入退格字符文本继续为空。 示例 1 输入s ab#c, t ad#c 输出true 解释s 和 t 都会变成 ac。示例 2 输入s ab##, t c#d# 输出true 解释s 和 t 都会变成 。示例 3 输入s a#c, t b 输出false 解释s 会变成 c但 t 仍然是 b。提示 1 s.length, t.length 200s 和 t 只含有小写字母以及字符 # 思路 同样我们使用栈的思想分别使用两个空字符串来模拟栈遇到#字符就出栈其他时候进栈最后比较两个字符串即可。 代码 class Solution { public:bool backspaceCompare(string s, string t) {string s1,s2;for(int i0;is.size();i){if(s[i]#) { if(s1.size()) s1.pop_back();}else s1s[i];}for(int i0;it.size();i){ if(t[i]#) { if(s2.size()) s2.pop_back();}else s2t[i];}return s1s2;} };03.基本计算器 II 题目链接https://leetcode.cn/problems/basic-calculator-ii 给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。 你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。 注意不允许使用任何将字符串作为数学表达式计算的内置函数比如 eval() 。 示例 1 输入s 32*2 输出7示例 2 输入s ³⁄₂ 输出1示例 3 输入s 35 / 2 输出5提示 1 s.length 3 * 105s 由整数和算符 (, -, *, /) 组成中间由一些空格隔开s 表示一个 有效表达式表达式中的所有整数都是非负整数且在范围 [0, 231 - 1] 内题目数据保证答案是一个 32-bit 整数 思路 根据题目要求我们只需要考虑空格、数字和四个运算符这几种情况我们可以使用一个数组来模拟栈插入每一个数使用一个前缀字符来进行运算符的标记初始设为加当我们碰到加减都更新碰到乘除就直接在栈顶计算直至字符串结束最后我们将栈中的数相加即可。 代码 class Solution { public:int calculate(string s) {vectorint st;char op;int ns.size(),i0,ret0;while(in){if(s[i] ) i;else if(s[i]0s[i]9){int tmp0;while(ins[i]0s[i]9) tmptmp10(s[i]-0);if(op) st.push_back(tmp);else if(op-) st.push_back(-tmp);else if(op) st.back() *tmp;else if(op/) st.back() /tmp;}else ops[i];}for(int i:st) reti;return ret;} };04.字符串解码 题目链接https://leetcode.cn/problems/decode-string/ 给定一个经过编码的字符串返回它解码后的字符串。 编码规则为: k[encoded_string]表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。 此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输入。 示例 1 输入s 3[a]2[bc] 输出aaabcbc示例 2 输入s 3[a2[c]] 输出accaccacc示例 3 输入s 2[abc]3[cd]ef 输出abcabccdcdcdef示例 4 输入s abc3[cd]xyz 输出abccdcdcdxyz提示 1 s.length 30s 由小写英文字母、数字和方括号 [] 组成s 保证是一个 有效 的输入。s 中所有整数的取值范围为 [1, 300] 思路 这里我们要使用栈来解决问题我们需要模拟每一种情况的发生以及细节的处理我们建立一个重复数的栈和一个字符串的栈遇到数字放入数字栈中遇到左括号把后面的字符串提取出来放入字符串栈中遇到了右括号解析然后放到字符串栈顶字符串之后遇到单独字符放到字符串栈顶字符串之后最后栈顶的字符串即为我们需要的字符串。 代码 class Solution { public:string decodeString(string s) {// 使用两个栈一个用于存储字符串另一个用于存储数字stackstring st;stackint nums;// 初始化栈将一个空字符串入栈用于存储当前解码的结果st.push();int i 0, n s.size();// 遍历输入字符串while (i n) {// 如果当前字符是数字解析数字并入数字栈if (s[i] 0 s[i] 9) {int tmp 0;while (s[i] 0 s[i] 9) tmp tmp * 10 (s[i] - 0);nums.push(tmp);}// 如果当前字符是[入栈一个空字符串用于存储当前括号内的解码结果else if (s[i] [) {i;string tmp;while (s[i] a s[i] z) tmp s[i];st.push(tmp);}// 如果当前字符是]将栈顶字符串重复相应次数后与前一个栈顶字符串拼接else if (s[i] ]) {string tmp st.top();st.pop();int k nums.top();nums.pop();while (k–) st.top() tmp;i;}// 如果当前字符是字母将字母拼接到栈顶字符串else {string tmp;while (i n s[i] a s[i] z) tmp s[i];st.top() tmp;}}// 最终栈中存储的即为解码结果return st.top();} };05.验证栈序列 题目链接https://leetcode.cn/problems/validate-stack-sequences/ 给定 pushed 和 popped 两个序列每个序列中的 值都不重复只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时返回 true否则返回 false 。 示例 1 输入pushed [1,2,3,4,5], popped [4,5,3,2,1] 输出true 解释我们可以按以下顺序执行 push(1), push(2), push(3), push(4), pop() - 4, push(5), pop() - 5, pop() - 3, pop() - 2, pop() - 1示例 2 输入pushed [1,2,3,4,5], popped [4,3,5,1,2] 输出false 解释1 不能在 2 之前弹出。提示 1 pushed.length 10000 pushed[i] 1000pushed 的所有元素 互不相同popped.length pushed.lengthpopped 是 pushed 的一个排列 思路 这里我们可以直接用一个栈来模拟这个过程当栈为空则说明相匹配否则就说明不匹配 代码 class Solution { public:bool validateStackSequences(vectorint pushed, vectorint popped) {stackint st;int i0,npopped.size();for(int x:pushed){st.push(x);while(!st.empty()st.top()popped[i]){st.pop();i;}}return st.empty();} };