分类 栈 下的文章

翻转字符串里的单词

问题描述

给定一个字符串,逐个翻转字符串中的每个单词。

示例 1:
输入: "the sky is blue"
输出: "blue is sky the"

示例 2:
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

说明:
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。
 
进阶:
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-words-in-a-string

思路

基本思路和之前做过的简化路径是一样的,只是这个更简单一些。
简化路径 https://www.irene.ink/archives/163/

题解

class Solution {
public:
    string reverseWords(string s) {
        string ret;
        int n=s.size();
        if(n==0) return ret;
        string tmp;
        stack<string> stack1;
        for(int i=0;i<n;i++){
            if(s[i]==' '){
                if(tmp!=""){
                    stack1.push(tmp);
                } 
                tmp="";
            } else{
                tmp+=s[i];
            }
        }
        if(tmp!=""){
            stack1.push(tmp);
            tmp="";
        }
        while (!stack1.empty()){
            ret+=stack1.top();
            ret+=" ";
            stack1.pop();
        }
        ret=ret.substr(0,ret.size()-1);
        return ret;
    }
};

简化路径

问题描述

# 以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。
在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径
请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。

示例 1:
输入:"/home/"
输出:"/home"
解释:注意,最后一个目录名后面没有斜杠。

示例 2:
输入:"/../"
输出:"/"
解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。

示例 3:
输入:"/home//foo/"
输出:"/home/foo"
解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。

示例 4:
输入:"/a/./b/../../c/"
输出:"/c"

示例 5:
输入:"/a/../../b/../c//.//"
输出:"/c"

示例 6:
输入:"/a//b////c/d//././/.."
输出:"/a/b/c"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/simplify-path

思路

基本思路是用栈来实现。返回值是ret,ret最开始为"/"

  • 单词之间是通过“/“来隔开的。
  • 如果两个”/“之间是".",那么continu;如果是“..",如果栈不为空的话,弹出顶端元素。如果是正常的字母组合,那么将压入栈中。
    此处应该注意,路径的最后不是以“/”结尾,所以应该在遍历结束后,单独进行判断
  • 最后,我用两个栈实现了双端队列,来将栈中的内容存储到ret中

题解

class Solution {
public:
    string simplifyPath(string path) {
        string ret="/";
        stack<string> stack1;
        string tmp = "";
        for (int i = 0; i < path.size(); i++) {
            if (path[i] == '/') {
                if (tmp.size() == 0) {
                    continue;
                } else if (tmp == ".") {
                    tmp="";
                    continue;
                } else if (tmp == "..") {
                    tmp="";
                    if (!stack1.empty()) {
                        stack1.pop();
                    } else continue;
                } else{
                    stack1.push(tmp);
                    tmp="";
                }
            } else{
                tmp+=path[i];
            }
        }
        if(tmp==".."){
            if(!stack1.empty()) stack1.pop();
        } else if(tmp!="."&&tmp.size()!=0){
            stack1.push(tmp);
        }
        stack<string> stack2;
        while (!stack1.empty()){
            stack2.push(stack1.top());
            stack1.pop();
        }
        int flag=1;
        if(!stack2.empty()) flag=0;
        while (!stack2.empty()){
            ret+=stack2.top();
            stack2.pop();
            ret+="/";
        }
        if(flag==0) ret=ret.substr(0,ret.size()-1);
        return ret;
    }
};

逆波兰表达式求值

问题描述

根据逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/evaluate-reverse-polish-notation

思路

本题的意思为,根据后缀表达式求值。

  • 如果是数字就入栈
  • 如果是运算符号的话,就弹出栈顶两个元素,并根据运算符做相应的运算
  • 将运算结果入栈
  • 最后栈内的唯一元素即为最终的结果

题解

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> tmp;
        int n = tokens.size();
        for (int i = 0; i < n; i++) {
            if (tokens[i] == "+") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 + tmp2;
                tmp.push(sum);
            } else if (tokens[i] == "*") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 * tmp2;
                tmp.push(sum);
            } else if (tokens[i] == "-") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 - tmp2;
                tmp.push(sum);
            } else if (tokens[i] == "/") {
                int tmp2 = tmp.top();
                tmp.pop();
                int tmp1 = tmp.top();
                tmp.pop();
                int sum = tmp1 / tmp2;
                tmp.push(sum);
            } else {
                tmp.push(stoi(tokens[i]));
            }
        }
        return tmp.top();
    }
};

字符串解码

题目描述

给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-string

思路

遇到这种括号匹配的问题,自然会想到用栈解决。
在遇到左括号前,将重复的次数存储在num中。
遇到左括号入栈,并将num清0。
将左括号之后,右括号之前的字母存到ret中。
碰到左括号入栈,并将并将num、ret清0。
如此重复,在遇到右括号的时候,将nums.top()次【因为数字在最内层括号的左边】的ret【要重复的部分还没入栈】,加到strs.top()中,然后令ret=str.top()作为新一次的需要重复的部分,在这个过程中别忘记弹出nums.pop()、strs.pop()。
重复以上步骤即可。

题解

class Solution {
public:
    string decodeString(string s) {
        string ret = "";
        int len = s.length();
        int num = 0;
        stack<int> nums;
        stack<string> strs;
        for (int i = 0; i < len; i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num * 10 + s[i] - '0';
            } else if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
            { ret = ret + s[i]; }
            else if (s[i] == '[') {
                nums.push(num);
                num = 0;
                strs.push(ret);
                ret = "";
            } else {
                int tmp=nums.top();
                nums.pop();
                for(int j=0;j<tmp;j++){
                    strs.top()=strs.top()+ret;
                }
                ret=strs.top();
                strs.pop();
            }
        }
        return ret;
    }
};

两数相加 II

问题描述

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。

进阶:
如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。

示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/add-two-numbers-ii

思路

数字相加的时候是从链表的末端开始的,所以用栈将两个链表存储起来会比较合适。
和两数相加I的思路一样,将情况分为3种:
1、两个栈都不为空
2、栈1为空
3、栈2为空
将每次相加的结果取余,余数为低位,压入栈中,栈底就是sum的最低位。
进位为相加的结果/10。
需要注意的是进位也要参与每次的加法。

通过栈构建链表时,需要特别注意:

ListNode *ret 为要返回的头节点。
一定要先建立cur = new ListNode(tmp.top());再让 ret = cur;
否则,ret只有一个节点。

题解

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        stack<int> stack1;
        stack<int> stack2;
        stack<int> tmp;
        int addtion = 0;
        while (l1 != nullptr) {
            stack1.push(l1->val);
            l1 = l1->next;
        }
        while (l2 != nullptr) {
            stack2.push(l2->val);
            l2 = l2->next;
        }
        while (!stack1.empty() || !stack2.empty()) {
            if (!stack1.empty() && !stack2.empty()) {
                tmp.push((stack1.top() + stack2.top() + addtion) % 10);
                addtion = (stack1.top() + stack2.top() + addtion) / 10;
                stack1.pop();
                stack2.pop();
            } else if (!stack1.empty()) {
                tmp.push((stack1.top() + addtion) % 10);
                addtion = (stack1.top() + addtion) / 10;
                stack1.pop();
            } else {
                tmp.push((stack2.top() + addtion) % 10);
                addtion = (stack2.top() + addtion) / 10;
                stack2.pop();
            }
        }
        ListNode *ret, *cur = nullptr;

        if (addtion == 1) {
            tmp.push(1);
        }
        while (!tmp.empty()) {
            if (cur == nullptr) {
                cur = new ListNode(tmp.top());
                ret = cur;
                tmp.pop();
            } else {
                cur->next = new ListNode(tmp.top());
                tmp.pop();
                cur = cur->next;
            }
        }
        return ret;
    }
};