ui设计学校培训机构_学生做微商怎么加入_长春seo技术_怎样在百度答题赚钱

155. 最小栈

题目描述

155. 最小栈

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

实现 MinStack 类:

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

运行代码

class MinStack {
public:MinStack() {}void push(int x) {if (st.size() == 0) {st.push({x, x});} else {st.push({x, min(x, st.top().second)});}}void pop() { st.pop(); }int top() { return st.top().first; }int getMin() { return st.top().second; }private:stack<pair<int, int>> st;
};/*** 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();*/

代码思路

1. MinStack()：构造函数，用于初始化堆栈对象，不执行任何操作。
2. void push(int x)：
   • 首先检查栈是否为空。如果栈为空，将入栈元素 x 和它本身组成一个整数对 {x, x} 推入栈中，因为此时栈中只有一个元素，它既是栈顶元素也是最小元素。
   • 如果栈不为空，将入栈元素 x 和当前栈顶元素中的最小元素（即 min(x, st.top().second)）组成一个整数对推入栈中。这样，每次入栈时都确保栈中的每个元素都记录了当前栈中的最小元素值。
3. void pop()：直接调用栈的 pop 函数删除栈顶部的元素。
4. int top()：返回栈顶元素的第一个整数，即当前栈顶的元素值。
5. int getMin()：返回栈顶元素的第二个整数，即当前栈中的最小元素值。

20. 有效的括号

题目描述

20. 有效的括号

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

有效字符串需满足：

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

运行代码

class Solution {
public:bool isValid(string s) {int n = s.size();if(n % 2) return false;stack<char> st;for (int i = 0; i < n; ++i) {if(s[i] == '(') st.push(')');else if(s[i] == '[') st.push(']');else if(s[i] == '{') st.push('}');else if(st.empty()) return false;else{char c = st.top();st.pop();if(c != s[i]) return false;}}if(!st.empty()) return false;return true;}
};

代码思路

1. bool isValid(string s)：
   • int n = s.size();：获取输入字符串的长度。
   • if(n % 2) return false;：如果字符串的长度是奇数，那么肯定无法形成合法的括号序列，直接返回 false。
   • stack<char> st;：创建一个字符栈，用于存储左括号，以便后续与右括号进行匹配。
   • for (int i = 0; i < n; ++i)：遍历输入字符串中的每个字符。
     • 如果当前字符是左括号 '('、'[' 或 '{'，则将对应的右括号 ')、'] 或 '}' 推入栈中。
     • 如果当前字符是右括号，先检查栈是否为空。如果栈为空，说明没有对应的左括号，返回 false。如果栈不为空，取出栈顶元素 c，并将其与当前字符进行比较。如果不相等，说明括号不匹配，返回 false；如果相等，说明找到了对应的左括号，将栈顶元素弹出。
   • if(!st.empty()) return false;：遍历完字符串后，如果栈不为空，说明有多余的左括号，返回 false。
   • return true;：如果上述所有条件都满足，说明输入字符串中的括号是合法有效的，返回 true。

1249. 移除无效的括号

题目描述

1249. 移除无效的括号

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下 任意一条 要求：

• 空字符串或只包含小写字母的字符串
• 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
• 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

运行代码

class Solution {
public:string minRemoveToMakeValid(string s) {stack<int> st;string result = "";// 第一次遍历，标记需要删除的括号位置for (int i = 0; i < s.length(); ++i) {if (s[i] == '(') {st.push(i);} else if (s[i] == ')') {if (!st.empty()) {st.pop();} else {s[i] = '*';}}}// 处理剩余未匹配的左括号while (!st.empty()) {s[st.top()] = '*';st.pop();}// 第二次遍历，构建有效字符串for (char c : s) {if (c!= '*') {result += c;}}return result;}
};

代码思路

1. 首先遍历给定的字符串，使用栈来记录左括号的位置。
2. 当遇到右括号时，如果栈不为空，说明有左括号可以与之匹配，弹出栈顶的左括号位置；如果栈为空，说明这个右括号没有对应的左括号，将其标记为需要删除（这里用特殊字符 '*' 标记）。
3. 遍历结束后，栈中剩下的就是没有匹配的左括号的位置，将这些位置的字符也标记为需要删除。
4. 最后再次遍历字符串，将没有被标记为删除的字符加入结果字符串中。