代码随想录算法训练营第十天｜LeetCode 20.有效的括号、1047.删除字符串中的所有相邻重复项、150.逆波兰表达式求值

20.有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/description/

1. 解题思路：

   1. 题目转化：

      1. 三种类型的括号，需要做匹配

      2. 匹配规则是：左右括号的类型要匹配、数量要一致，而且要按照顺序匹配

      3. 例子是：“()”、“(){}[]”、“(([]))”

   2. 条件转化：

      1. 按照顺序匹配：元素的相对顺序不能做改变

      2. 数量一致：

         1. 可以做剪枝，假如元素个数是奇数，就直接返回false

         2. 三种类型括号，可以各自有一个计数寄存器，同理，假如出现其中一个寄存器的值是奇数，就直接返回false

      3. 类型要匹配：

         1. 不考虑顺序的情况下，对于单种类型的括号，可以有两个计数寄存器，一个负责计数左括号，一个负责计数右括号，遍历到最后，假如两个寄存器的值不同，就直接返回false
         2. 但是题目要求相对顺序不能做改变。可以知道是先有左括号，再有右括号。在单种类型的括号匹配下，其实也可以有两个计数寄存器，一个负责计数左括号，一个负责计数右括号。每次遇到右括号就判断一次，假如两个寄存器的值不同，就直接返回false
         3. 但是，这里有个问题是，单种类型的括号可以这样子处理，三种类型混合的括号，需要再增加额外的条件，防止错配。这个额外条件，我现在也想不出来了，哈哈哈哈哈。但是可以知道，需要再增加一个标志位，来判断左括号类型的先后顺序。

   3. 基于条件转化，可以知道暴力解法是通过统计左右括号的个数来模拟匹配的过程。

   4. 优化：可以将两个计数寄存器减少为一个计数寄存器，遇到左括号就+1，遇到右括号就-1，判断时，若寄存器的值<0，就返回false

   5. 暴力法解决起来很麻烦，在1.2.3.3点中，提到需要在遍历左括号，做计数的同时，增加标志位来判断先后顺序。这个想法和栈有点像，在函数调用中，栈是用来储存上下文以及局部变量的，便于恢复。

      1. 在解决这个问题的时候，可以用栈来解决先后顺序问题。
      2. 由于匹配的顺序不能出错，也就是右括号都是与最靠近它的左括号匹配的，在从左往后遍历的过程中，就是后遍历的左括号去跟右括号做匹配，符合栈先进后出的特性。
      3. 解决顺序问题是：采用栈存储左括号，遇到左括号就入栈，遇到右括号就将左括号出栈。
      4. 解决匹配问题是：每次遇到右括号，就与出栈的左括号做类型判断。
      5. 解决数量问题是：遍历到最后，判断栈是否为空就可以知道数量是否匹配。

2. 代码实现：

   1. 调用库函数：

  class Solution {
  public:
      bool isValid(string s) {
          // 若数量为0或者为奇数，返回false
          if(s.size() == 0 || s.size() % 2 != 0) {
              return false;
          }
          // 申请一个栈
          stack<char> st;
          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();
      }
  };

2. 不调用库函数：

  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;
          }
      }
  };

3. 总结反思：

   1. 每次遇到题目，都是想着暴力解法先行，但是由于考虑条件不够全面，无法解决掉所有的测试用例。开始不断调试，陷入困境，解题效率极低。去看题解，也是懵懵懂懂，一看就会，一做就不会。长期下来，自信心受挫严重。
   2. 在按照代码随想录刷题的时候，按照提示，知道用栈这个方法来解决这个题目，一刷的时候掌握思路，二刷的时候就可以直接写出框架，并且一次提交通过。由不会到会需要一个过程，接受不会，并且可以模仿思路，把代码写出来，这点还是蛮重要的，模仿着模仿着，就发现掌握了，也就是学会，可以帮助建立自信心。
   3. 栈可以解决的需求：顺序、数量、匹配、多类型。

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

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

1. 解题思路：

   1. 题目转化：

      1. 删除两个挨着并且相同字符

      2. 删除动作是将两个字符从数组中移除，形成一个新的数组

      3. 例子是：

         1. “abbaca” == “ca”
         2. “abbaaa” == “”

   2. 条件转化：

      1. 顺序条件：元素的相对顺序不能做改变
      2. 消除条件：
         1. 元素相同
         2. 消除的元素是相邻元素
         3. 消除的元素从数组中移除，后续的元素需要往前移动，填补空位
      3. 返回条件：相邻元素不相同的字符串

   3. 双指针解法一：

      1. 左指针负责按照顺序在原数组中摆放符合要求的元素，右指针负责遍历数组
      2. 右指针遍历数组时，关注当前元素与下一个元素的关系
      3. 若两个元素相同，那么右指针指向下下个元素，并且重复第2点
      4. 若两个元素不相同，需要判断已保存的元素与当前元素的关系
         1. 若相同，左指针指向上一个元素，移除已保存的当前元素。右指针指向下一个元素。
         2. 若不相同，那么将右指针的值赋值给左指针，做保存，右指针指向下一个元素，并且重复第2点
      5. 遍历结束后，将左指针的下一个元素赋值为休止符，确定新数组
      6. 绘图如下：

   4. 双指针解法二：

      1. 左指针负责存放已有元素，初始化为-1，右指针负责遍历数组，初始化为0
      2. 关注已有元素跟当前元素的关系
      3. 若两个元素相同，左指针保存当前元素，右指针遍历下一个元素
      4. 若两个元素不相同，左指针删除已有元素，右指针遍历下一个元素
      5. 绘图如下：

   5. 栈：

      1. 遍历数组，判断栈顶元素与当前元素是否相同
      2. 若两个元素相同，那么将栈顶元素弹出，并且遍历下一个元素
      3. 若两个元素不相同，再将当前元素入栈
      4. 重复第1点
      5. 遍历结束后，新建一个字符数组，将该栈元素弹出
      6. 反转新数组
      7. 返回新的数组
      8. 绘图如下：

2. 代码实现：

   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 <<s[left] << s[right] << std::endl;
              // }
          }
          // 倒数第一个元素和倒数第二个元素相同
          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;
      }
  };

2. 双指针解法二：

  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;
      }
  };

3. 栈解法：

  class Solution {
  public:
      string removeDuplicates(string s) {
          // if(s.size() == 0) {
          //     return s;
          // }
          // 新建一个栈
          stack<char> st;
          // 遍历数组
          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;
      }
  };

3. 总结反思：

   1. 采用C的方式来写C++，是一件很蠢的事情。这样子的思维方式，导致我C++的代码也很多冗余逻辑，其实都是可以用库函数来替代删减的。这次主要是字符串的大小：

      1. C是采用新增结束符号’\0’，就可以重新定义数组长度
      2. C++需要采用resize，才可以重新定义数组长度

   2. 基于栈的解法，这次想起来用双指针解法。算是一个小小的进步吧。但是这个双指针法用的不对，是三指针了，还是有很大的进步空间的，属于模拟解法了。

   3. 针对双指针法，重新思考之后，框架更清晰一些，其实就是用双指针去模拟栈，核心原理是栈的原理。

   4. 针对三个方法都绘图，通过图的比较，可以看出三个方式的优劣。图解还是比文字要清晰很多，以后还是要图文结合比较合适。虽然不是动图，但是也比没有图要好理解很多。比对图如下：

150.逆波兰表达式求值

题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

1. 解题思路：

   1. 题目转化：

      1. 提供一个字符串数组，包含数字和运算符号

      2. 完成计算过程，提供结果

      3. 例子：

         1. [“2”, “1”, “+”, “3”, “*” ]

         2. ((2 + 1) * 3) = 9

   2. 条件转化：

      1. 顺序条件：相对顺序不能改动

      2. 计算条件：

         1. 中缀算术表达式，两个数字与一个运算符

         2. 除数不会为零

         3. 除法不需要考虑小数

      3. 返回条件：整型值

   3. 栈：

      1. 将数字按照顺序遍历入栈

      2. 遇到操作符号时，将数字出栈，并且做计算

      3. 再将结果入栈，重复执行第1点

      4. 最后将栈顶的结果返回

      5. 绘图如下：

2. 代码实现：

class Solution {
   public:
       int evalRPN(vector<string>& tokens) {
           // 建立一个栈，longlong类型防止溢出
           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);
                   }
                   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;
       }
   };

3. 总结反思：

   1. 需要额外注意数据类型溢出的问题，实际工程中极容易出现该情况。int类型是32位，2^31 - 1为数字上限。两个数字相加或者相乘，容易超出范围。需要转为longlong。
   2. 其次是注意字符串转为数字的库函数实现逻辑。虽然可以方便调用，但是还是要知道原理，知道怎样去做这个转换。要将字符串反转，这样子第一个字符就是个位数，依此类推，十位、百位、千位等。
   3. 栈的先进后出性质可以做后续遍历，其实字符串反转的实现跟栈的原理是一样的，所以在考虑逆序的问题解答时，可以优先考虑栈结构。但是递归需要注意，容易出现栈溢出的情况，而且很难排查这个错误原因。
   4. 这次的解答属实是折磨人。
      1. 做出来题目，跟能够以文字或者讲的形式，去思维清晰的表达出来，差距很大的。
      2. 可能做出来只需要30分钟，但是做个讲解需要1个小时甚至更长时间。
      3. 但是好处也是巨大的，对于各个细节都要考虑，并且找到解答，更好的掌握这个知识点以及题目。
      4. 尽管已经有很多类似的文章或者讲解出现，尽管AI可以取代这部份的工作，但，始终那都是别人的东西，不是么。自己在理解别人的东西的时候也会出现难以理解的情况，并且希望能找到便于理解的解决思路。
      5. 坚持做下去，一段时间后回顾，也是一个关键的里程碑，成长的路径。