20.有效的括号
题目链接：https://leetcode.cn/problems/valid-parentheses/description/
解题思路：
题目转化：
三种类型的括号，需要做匹配 匹配规则是：左右括号的类型要匹配、数量要一致，而且要按照顺序匹配 例子是：“()”、“(){}[]”、“(([]))” 条件转化：
按照顺序匹配：元素的相对顺序不能做改变 数量一致：
可以做剪枝，假如元素个数是奇数，就直接返回false 三种类型括号，可以各自有一个计数寄存器，同理，假如出现其中一个寄存器的值是奇数，就直接返回false 类型要匹配：
不考虑顺序的情况下，对于单种类型的括号，可以有两个计数寄存器，一个负责计数左括号，一个负责计数右括号，遍历到最后，假如两个寄存器的值不同，就直接返回false但是题目要求相对顺序不能做改变。可以知道是先有左括号，再有右括号。在单种类型的括号匹配下，其实也可以有两个计数寄存器，一个负责计数左括号，一个负责计数右括号。每次遇到右括号就判断一次，假如两个寄存器的值不同，就直接返回false但是，这里有个问题是，单种类型的括号可以这样子处理，三种类型混合的括号，需要再增加额外的条件，防止错配。这个额外条件，我现在也想不出来了，哈哈哈哈哈。但是可以知道，需要再增加一个标志位，来判断左括号类型的先后顺序。 基于条件转化，可以知道暴力解法是通过统计左右括号的个数来模拟匹配的过程。 优化：可以将两个计数寄存器减少为一个计数寄存器，遇到左括号就+1，遇到右括号就-1，判断时，若寄存器的值<0，就返回false 暴力法解决起来很麻烦，在1.2.3.3点中，提到需要在遍历左括号，做计数的同时，增加标志位来判断先后顺序。这个想法和栈有点像，在函数调用中，栈是用来储存上下文以及局部变量的，便于恢复。
在解决这个问题的时候，可以用栈来解决先后顺序问题。由于匹配的顺序不能出错，也就是右括号都是与最靠近它的左括号匹配的，在从左往后遍历的过程中，就是后遍历的左括号去跟右括号做匹配，符合栈先进后出的特性。解决顺序问题是：采用栈存储左括号，遇到左括号就入栈，遇到右括号就将左括号出栈。解决匹配问题是：每次遇到右括号，就与出栈的左括号做类型判断。解决数量问题是：遍历到最后，判断栈是否为空就可以知道数量是否匹配。 代码实现：
调用库函数：
class Solution {
public:
bool isValid(string s) {
// 若数量为0或者为奇数，返回false
if(s.size() == 0 || s.size() % 2 != 0) {
return false;
}
// 申请一个栈
stack
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]){
// 不匹配就返回false
return false;
}
// 若栈不为空，而且左括号匹配，就弹出栈顶左括号
else {
st.pop();
}
}
// 若遍历完，栈中没有元素，说明括号一一匹配
return st.empty();
}
};
不调用库函数：
class Solution {
public:
bool isValid(string s) {
// 若数量为0或者为奇数，返回false
if(s.size() == 0 || s.size() % 2 != 0) {
return false;
}
// 申请一个栈
char stack[s.size()];
int top = 0;
for(int i = 0; i < s.size(); i++) {
// 遇到左括号入栈
if(s[i] == '(' || s[i] == '{' || s[i] == '[') {
stack[top++] = s[i];
}
// 遇到右括号出栈
else {
// 若栈中无元素，返回false
if(top <= 0) {
return false;
}
// 出栈
char tmp = stack[--top];
// 与右括号做匹配
if(s[i] == ')' && tmp != '(') {
return false;
}
else if(s[i] == ']' && tmp != '[') {
return false;
}
else if(s[i] == '}' && tmp != '{') {
return false;
}
else {;}
}
}
if(top == 0) {
return true;
}
// 数量不一致，栈中还有左括号
else {
return false;
}
}
};
总结反思：
每次遇到题目，都是想着暴力解法先行，但是由于考虑条件不够全面，无法解决掉所有的测试用例。开始不断调试，陷入困境，解题效率极低。去看题解，也是懵懵懂懂，一看就会，一做就不会。长期下来，自信心受挫严重。在按照代码随想录刷题的时候，按照提示，知道用栈这个方法来解决这个题目，一刷的时候掌握思路，二刷的时候就可以直接写出框架，并且一次提交通过。由不会到会需要一个过程，接受不会，并且可以模仿思路，把代码写出来，这点还是蛮重要的，模仿着模仿着，就发现掌握了，也就是学会，可以帮助建立自信心。栈可以解决的需求：顺序、数量、匹配、多类型。
1047.删除字符串中的所有相邻重复项
题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
解题思路：
题目转化：
删除两个挨着并且相同字符 删除动作是将两个字符从数组中移除，形成一个新的数组 例子是：
“abbaca” == “ca”“abbaaa” == “” 条件转化：
顺序条件：元素的相对顺序不能做改变消除条件：
元素相同消除的元素是相邻元素消除的元素从数组中移除，后续的元素需要往前移动，填补空位 返回条件：相邻元素不相同的字符串 双指针解法一：
左指针负责按照顺序在原数组中摆放符合要求的元素，右指针负责遍历数组右指针遍历数组时，关注当前元素与下一个元素的关系若两个元素相同，那么右指针指向下下个元素，并且重复第2点若两个元素不相同，需要判断已保存的元素与当前元素的关系
若相同，左指针指向上一个元素，移除已保存的当前元素。右指针指向下一个元素。若不相同，那么将右指针的值赋值给左指针，做保存，右指针指向下一个元素，并且重复第2点 遍历结束后，将左指针的下一个元素赋值为休止符，确定新数组绘图如下： 双指针解法二：
左指针负责存放已有元素，初始化为-1，右指针负责遍历数组，初始化为0关注已有元素跟当前元素的关系若两个元素相同，左指针保存当前元素，右指针遍历下一个元素若两个元素不相同，左指针删除已有元素，右指针遍历下一个元素绘图如下： 栈：
遍历数组，判断栈顶元素与当前元素是否相同若两个元素相同，那么将栈顶元素弹出，并且遍历下一个元素若两个元素不相同，再将当前元素入栈重复第1点遍历结束后，新建一个字符数组，将该栈元素弹出反转新数组返回新的数组绘图如下： 代码实现：
双指针解法一：
class Solution {
public:
string removeDuplicates(string s) {
int left = -1;
int right = 0;
// 右指针遍历数组，防止越界，在size - 1处退出循环
while(right < s.size() - 1) {
// 相邻两个元素相同，要消除，右指针跳过下一个元素，从下下个元素继续遍历
if(s[right] == s[right + 1]) {
right = right + 2;
}
// 相邻两个元素不同，将当前元素保存在原数组中，从下一个元素继续遍历
else if(s[right] != s[right + 1]) {
// 假如left为-1，就将当前元素直保存，从下一个元素开始遍历
if(left < 0) {
s[++left] = s[right];
right++;
}
// 假如left不为-1，而且已有元素和当前元素不匹配，就将当前元素保存，从下一个元素开始遍历
else if(left >= 0 && s[right] != s[left]) {
s[++left] = s[right];
right++;
}
// 假如left不为-1，而且已有元素和当前元素匹配，就将已有元素删除，不保存当前元素，从下一个元素开始遍历
else if(left >= 0 && s[left] == s[right]) {
right++;
left--;
}
else {;}
}
else {;}
// if(left >= 0) {
// cout << left < // } } // 倒数第一个元素和倒数第二个元素相同 if(right == s.size()) { ; } // 倒数第一个元素和倒数第二个元素不同 else if(right == s.size() - 1) { // 判断倒数第一个元素和已有元素是否匹配，若匹配，就删除已有元素 if(left >= 0 && s[left] == s[right]) { left--; } // 若不匹配，就保存倒数第一个元素 else { s[++left] = s[right]; } } else {;} // 划分出新的数组，需要将左指针的下一个值赋值为结束符 // s[++left] = '\0'; s.resize(left + 1); // for(int i = 0; i < s.size(); i++) { // cout << s[i] << std::endl; // } return s; } }; 双指针解法二： class Solution { public: string removeDuplicates(string s) { int left = -1; int right = 0; // 右指针遍历数组，防止越界，在size处退出循环 while(right < s.size()) { // 若左指针指向空，或者左指针指向的值与右指针不同 if((left == -1) || s[left] != s[right]) { // 左指针移动到下一个元素 left++; // 将右指针的值保存下来 s[left] = s[right]; // 右指针指向下一个元素 right++; } // 若左指针的值和右指针的值相同 else if(s[left] == s[right]) { // 左指针移动到上一个元素，删除当前元素 left--; // 右指针直线下一个元素 right++; } else {;} } // 划分出新的数组，需要将左指针的下一个值作为新的数组的大小 s.resize(left + 1); return s; } }; 栈解法： class Solution { public: string removeDuplicates(string s) { // if(s.size() == 0) { // return s; // } // 新建一个栈 stack // 遍历数组 for(int i = 0; i < s.size(); i++) { // 若栈为空或者栈顶元素与当前元素不匹配 if(st.empty() || st.top() != s[i]) { // 当前元素入栈 st.push(s[i]); } // 若栈顶元素与当前元素匹配 else { // 出栈 st.pop(); } // if(!st.empty()) // cout << st.top() << std::endl; } // 新建数组 string result = ""; // 将栈中的元素放置到新数组中 while(!st.empty()) { result += st.top(); st.pop(); } // 反转数组，栈是先进后出的，需要做一次反转 reverse(result.begin(), result.end()); return result; // return s; } }; 总结反思： 采用C的方式来写C++，是一件很蠢的事情。这样子的思维方式，导致我C++的代码也很多冗余逻辑，其实都是可以用库函数来替代删减的。这次主要是字符串的大小： C是采用新增结束符号’\0’，就可以重新定义数组长度C++需要采用resize，才可以重新定义数组长度 基于栈的解法，这次想起来用双指针解法。算是一个小小的进步吧。但是这个双指针法用的不对，是三指针了，还是有很大的进步空间的，属于模拟解法了。 针对双指针法，重新思考之后，框架更清晰一些，其实就是用双指针去模拟栈，核心原理是栈的原理。 针对三个方法都绘图，通过图的比较，可以看出三个方式的优劣。图解还是比文字要清晰很多，以后还是要图文结合比较合适。虽然不是动图，但是也比没有图要好理解很多。比对图如下： 150.逆波兰表达式求值 题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/ 解题思路： 题目转化： 提供一个字符串数组，包含数字和运算符号 完成计算过程，提供结果 例子： [“2”, “1”, “+”, “3”, “*” ] ((2 + 1) * 3) = 9 条件转化： 顺序条件：相对顺序不能改动 计算条件： 中缀算术表达式，两个数字与一个运算符 除数不会为零 除法不需要考虑小数 返回条件：整型值 栈： 将数字按照顺序遍历入栈 遇到操作符号时，将数字出栈，并且做计算 再将结果入栈，重复执行第1点 最后将栈顶的结果返回 绘图如下： 代码实现： class Solution { public: int evalRPN(vector // 建立一个栈，longlong类型防止溢出 stack 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); } else if(tokens[i] == "-") { st.push(num2 - num1); } else if(tokens[i] == "*") { st.push(num2 * num1); } else if(tokens[i] == "/") { st.push(num2 / num1); } else {;} } // 遍历到数字，要将数字从字符串转为数字后，再入栈 else { st.push(stoll(tokens[i])); } } // 取栈顶元素，即唯一的一个元素，是结果 int result = st.top(); st.pop(); return result; } }; 总结反思： 需要额外注意数据类型溢出的问题，实际工程中极容易出现该情况。int类型是32位，2^31 - 1为数字上限。两个数字相加或者相乘，容易超出范围。需要转为longlong。其次是注意字符串转为数字的库函数实现逻辑。虽然可以方便调用，但是还是要知道原理，知道怎样去做这个转换。要将字符串反转，这样子第一个字符就是个位数，依此类推，十位、百位、千位等。栈的先进后出性质可以做后续遍历，其实字符串反转的实现跟栈的原理是一样的，所以在考虑逆序的问题解答时，可以优先考虑栈结构。但是递归需要注意，容易出现栈溢出的情况，而且很难排查这个错误原因。这次的解答属实是折磨人。 做出来题目，跟能够以文字或者讲的形式，去思维清晰的表达出来，差距很大的。可能做出来只需要30分钟，但是做个讲解需要1个小时甚至更长时间。但是好处也是巨大的，对于各个细节都要考虑，并且找到解答，更好的掌握这个知识点以及题目。尽管已经有很多类似的文章或者讲解出现，尽管AI可以取代这部份的工作，但，始终那都是别人的东西，不是么。自己在理解别人的东西的时候也会出现难以理解的情况，并且希望能找到便于理解的解决思路。坚持做下去，一段时间后回顾，也是一个关键的里程碑，成长的路径。 文章来源
您阅读本篇文章共花了：
发表评论