您的位置:首页 > 新闻 > 热点要闻 > 天门网站定制_网页设计代码放图片_泰安做网站公司_搜狗指数官网

天门网站定制_网页设计代码放图片_泰安做网站公司_搜狗指数官网

2024/12/23 15:55:38 来源:https://blog.csdn.net/qq_73450329/article/details/143950195  浏览:    关键词:天门网站定制_网页设计代码放图片_泰安做网站公司_搜狗指数官网
天门网站定制_网页设计代码放图片_泰安做网站公司_搜狗指数官网

栈/单调栈

1. 20. 有效的括号

简单

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[ ]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

示例 4:

输入:s = "([ ])"

输出:true

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

// 定义一个名为Solution的类,用于解决括号有效性问题。
class Solution {
public:
    // 函数isValid用于检查输入的字符串s是否是有效的括号序列。
    bool isValid(string s) {
        // 定义一个字符栈st,用于存放预期的闭括号。
        stack<char> st;

        // 获取输入字符串s的长度。
        int n = s.size();

        // 遍历字符串s中的每个字符。
        for(int i{}; i < n; ++i) {
            // 如果当前字符是开括号'(',则将对应的闭括号')'推入栈中。
            if(s[i] == '(') {
                st.push(')');
            } else if(s[i] == '[') {
                // 如果当前字符是开括号'[',则将对应的闭括号']'推入栈中。
                st.push(']');
            } else if(s[i] == '{') {
                // 如果当前字符是开括号'{',则将对应的闭括号'}'推入栈中。
                st.push('}');
            } else {
                // 如果当前字符是闭括号,检查栈是否为空或者栈顶元素是否与当前闭括号匹配。
                // 如果栈为空,或者栈顶元素与当前闭括号不匹配,则说明括号序列无效,返回false。
                if(st.empty() || st.top() != s[i]) return false;

                // 如果栈顶元素与当前闭括号匹配,则弹出栈顶元素。
                st.pop();
            }
        }

        // 遍历结束后,如果栈为空,则说明所有开括号都找到了匹配的闭括号,返回true。
        // 如果栈不为空,则说明有未匹配的开括号,返回false。
        return st.empty();
    }
};

2. 155. 最小栈

中等

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出:
[null,null,null,null,-3,null,0,-2]解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

  • -231 <= val <= 231 - 1
  • poptop 和 getMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        // 如果s2为空或者val小于等于s2的栈顶元素,则将val压入s2
        if(s2.empty() || val <= s2.top()) s2.push(val);
        // 将val压入s1
        s1.push(val);
    }
    
    void pop() {
        // 如果两个栈都为空,则直接返回
        if(s1.empty() && s2.empty()) return;
        // 如果s1的栈顶元素等于s2的栈顶元素,则也需要从s2中弹出元素
        if(s1.top() == s2.top()) s2.pop();
        // 从s1中弹出元素
        s1.pop();
    }
    
    int top() {
        // 如果s1为空,则返回-1表示栈为空
        if(s1.empty()) return -1;
        // 返回s1的栈顶元素
        return s1.top();
    }
    
    int getMin() {
        // 如果s2为空,则返回-1表示栈为空
        if(s2.empty()) return -1;
        // 返回s2的栈顶元素,即当前栈中的最小值
        return s2.top();
    }
private:
    stack<int> s1;
    stack<int> s2;
};

解释:

 pop方法中,返回空(null)是因为pop操作本身不返回任何值,它只是移除栈顶元素。如果栈为空,那么就没有元素可以移除,所以返回空表示没有操作发生。

top方法:当s1为空时,意味着栈中没有任何元素,因此没有栈顶元素可以返回。在这种情况下,返回-1作为一个标志值,表示栈为空。这是因为-1通常不会是一个合法的栈元素值,所以可以用作一个错误标志。

getMin方法:同样,当s2为空时,意味着没有最小值可以返回(因为栈中没有任何元素)。因此,返回-1作为一个标志值,表示栈为空。

3. 394. 字符串解码

中等

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: 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 <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300] 

  class Solution {
public:
    string decodeString(string s) {
        string res = ""; // 用于构建最终的解码字符串
        stack<int> nums; // 用于存储数字,这些数字表示重复的次数
        stack<string> strs; // 用于存储字符串片段
        int num = 0; // 用于记录当前读取的数字
        int len = s.size(); // 字符串s的长度
        for(int i = 0; i < len; ++i) {
            if(s[i] >= '0' && s[i] <= '9') {
                // 如果当前字符是数字,则累加到num中
                num = num * 10 + s[i] - '0';
            } else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
                // 如果当前字符是字母,则添加到res中
                res = res + s[i];
            } else if(s[i] == '[') {
                // 如果遇到'[',则将之前的数字和字符串片段压栈
                nums.push(num);
                num = 0;
                strs.push(res);
                res = "";
            } else {
                // 如果遇到']',则进行解码操作
                int times = nums.top();
                nums.pop();
                for(int j = 0; j < times; ++j)
                    strs.top() += res;
                res = strs.top();
                strs.pop();
            }
        }
        return res; // 返回解码后的字符串
    }
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com