代码随想录刷题题Day9

刷题的第九天，希望自己能够不断坚持下去，迎来蜕变。😀😀😀
刷题语言：C++ / Python
Day9 任务
● 20. 有效的括号
● 1047. 删除字符串中的所有相邻重复项
● 150. 逆波兰表达式求值

1 有效的括号

在这里插入图片描述
代码随想录刷题Day8介绍了栈实现队列，队列实现栈，接下来就是栈的经典应用
括号匹配是使用栈解决的经典问题

栈结构的特殊性，非常适合做对称匹配类的题目
思路：

三种不匹配的情况：
（1）字符串左方向的括号多余
（2）括号类型不匹配
（3）字符串右方向的括号多余

在这里插入图片描述
1.已经遍历完了字符串，但是栈不为空：左方向的括号多余
2.遍历字符串匹配的过程中，发现栈里没有要匹配的字符：括号类型不匹配
3.遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了：右方向的括号多余

左括号和右括号全都匹配就是字符串遍历完之后，栈是空的

伪代码：

stack<char> st;
if (s.size % 2 != 0) return false;// 如果s的长度为奇数，一定不符合要求
for (i = 0; i < s.size; i++)
{
	if (s[i] == '(') st.push(')');
	else if (s[i] == '[') st.push(']');
	else if (s[i] == '{') st.push('}');
	// 字符串匹配的过程中，栈已经为空了，没有匹配的字符
	else if (st.empty() || st.top() != s[i]) return false;
	else st.pop();// st.top() 与 s[i]相等，栈弹出元素
}
return st.empty();// 左括号和右括号全都匹配就是字符串遍历完之后，栈是空的，不为空那就是左方向括号多余

C++：

class Solution {
public:
    bool isValid(string s) {
		stack<char> st;
		if (s.size() % 2 != 0) return false;// 如果s的长度为奇数，一定不符合要求
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] == '(') st.push(')');
			else if (s[i] == '[') st.push(']');
			else if (s[i] == '{') st.push('}');
			else if (st.empty() || st.top() != s[i]) return false;
			else st.pop();
		}
		return st.empty();
    }
};

时间复杂度: $O (n)$
空间复杂度: $O (n)$
Python：

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        return not stack

2 删除字符串中的所有相邻重复项

在这里插入图片描述
栈适合做这种类似于爱消除的操作，因为栈遍历数组当前元素时候，前一个元素是什么
匹配问题都是栈的强项

思路：

本题要删除相邻相同元素，相对于上一题也是匹配问题，在删除相邻重复项的时候，就是要知道当前遍历的这个元素在前一位是不是遍历过一样数值的元素。
栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。从栈中弹出剩余元素

伪代码：
字符串模拟栈的行为

string result;
for (char c : s)
{
	if (result.empty() || c != result.back())
	{
		result.push_back(c);
	}
	else
	{
		result.pop_back();
	}
	return result;
}

C++：

class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (char c : s)
        {
            if (result.empty() || c != result.back())
            {
                result.push_back(c);
            }
            else
            {
                result.pop_back();
            }
        }
        return result;
    }
};

时间复杂度: $O (n)$
空间复杂度: $O (1)$ ，返回值不计空间复杂度

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        for (char c : s)
        {
            if (st.empty() || c != st.top())
            {
                st.push(c);
            }
            else
            {
                st.pop();
            }
        }
        string result = "";
        while (!st.empty())// 将栈中元素放到result字符串汇总
        {
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end());// 此时字符串需要反转
        return result;
    }
};

时间复杂度: $O (n)$
空间复杂度: $O (n)$

编程语言的一些功能实现也会使用栈结构，实现函数递归调用就需要栈，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因

Python：

class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = list()
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)# 字符串拼接

3 逆波兰表达式求值

在这里插入图片描述
展现出计算机的思考方式

逆波兰表达式主要有以下两个优点:
（1）去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果
（2）适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中
栈与递归之间在某种程度上是可以转换的！
思路：

逆波兰表达式相当于是二叉树中的后序遍历。

C++ 字符串转换为数字（三：stoi，stoll，stof，stod）
伪代码：

stack<long long> st;
for (i = 0; i < s.size; i++)
{
	if (s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/")
	{
		long long num1 = st.top();
		st.pop();
		long long num2 = st.top();
		st.pop();
		if (s[i] == "+") st.push(num1 + num2);
		if (s[i] == "-") st.push(num1 - num2);
		if (s[i] == "*") st.push(num1 * num2);
		if (s[i] == "/") st.push(num1 / num2);
	}
	else
	{
		st.push(stoll(tokens[i]));
	}
	result = st.top();
	st.pop();
	return result;
}

C++：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (int i = 0; i < tokens.size(); i++)
        {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            }
            else
            {
                st.push(stoll(tokens[i]));
            }
        }
        int result = st.top();
        st.pop();
        return result;
    }
};