算法日记day 13（删除字符串中的所有重复元素）

一、删除字符串中的所有重复元素

题目：

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

 思路：

初始化栈，将字符串中的元素分别加入栈中，每个元素加入栈时都与栈顶元素进行比较，如果相同则说明元素重复，栈顶元素弹出，继续遍历下一个元素，直到所有元素遍历完毕，此时栈中剩下的元素即为不重复的元素，但此时栈中元素的顺序与题目要求顺序相反，因此需要弹出栈中元素的同时赋给一个新的字符串。

代码：

public String removeDuplicates(String s) {
    // 使用双端队列来存储处理后的字符序列
    Deque<Character> deque = new LinkedList<>();
    char ch;
    
    // 遍历输入的字符串 s
    for (int i = 0; i < s.length(); i++) {
        ch = s.charAt(i);
        // 如果双端队列为空或者栈顶元素不等于当前字符，则将当前字符压入栈中
        if (deque.isEmpty() || deque.peek() != ch) {
            deque.push(ch);
        } else {
            // 如果栈顶元素等于当前字符，则移除栈顶元素，表示移除相邻重复的字符
            deque.pop();
        }
    }
    
    // 将双端队列中的字符转换为最终的字符串结果
    String str = "";
    while (!deque.isEmpty()) {
        str = deque.pop() + str;
    }
    
    // 返回去重后的字符串
    return str;
}

二、逆波兰表达式求值

什么是逆波兰表达式？

逆波兰表达式（Reverse Polish Notation，RPN）是一种用于表示数学表达式的格式，它与传统的中缀表达式有所不同。在逆波兰表达式中，运算符在操作数的后面而不是中间，这样可以避免使用括号来指定运算符的优先级。相当于二叉树的后序遍历。

特点和优点：

1. 无需括号：逆波兰表达式不需要括号来指定运算符的优先级，因为操作符与操作数的顺序已经明确。

2. 后缀表达式：逆波兰表达式也被称为后缀表达式，因为操作符跟在操作数的后面。

3. 易于计算：逆波兰表达式可以直接由计算机执行，而无需像中缀表达式那样进行优先级和结合性的复杂处理。

举例说明：

考虑一个简单的数学表达式 (3 + 4) * 5，其对应的逆波兰表达式为 3 4 + 5 *。

• 在逆波兰表达式中：
  • 3 和 4 是操作数。
  • + 是加法操作符，作用于前面的两个操作数。
  • 5 是另一个操作数。
  • * 是乘法操作符，作用于前面的结果和最后一个操作数。

实现逆波兰表达式的计算：

使用栈来实现逆波兰表达式的计算是常见的方法：

1. 遍历逆波兰表达式：

   • 遇到操作数时，压入栈中。
   • 遇到操作符时，从栈中弹出对应数量的操作数，进行计算，并将结果压入栈中。

2. 计算最终结果：

   • 遍历结束后，栈中唯一的元素即为整个表达式的计算结果。

题目：

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

思路：可利用栈结构进行操作

代码：

public int evalRPN(String[] tokens) {
    // 使用双端队列实现栈
    Deque<Integer> deque = new LinkedList<>();
    
    // 遍历逆波兰表达式的每个元素
    for (String s : tokens) {
        // 如果是加法操作符
        if ("+".equals(s)) {
            // 弹出栈顶两个元素相加，结果压入栈中
            deque.push(deque.pop() + deque.pop());
        } 
        // 如果是减法操作符
        else if ("-".equals(s)) {
            // 弹出栈顶两个元素，做减法运算，结果压入栈中
            deque.push(-deque.pop() + deque.pop());
        } 
        // 如果是乘法操作符
        else if ("*".equals(s)) {
            // 弹出栈顶两个元素相乘，结果压入栈中
            deque.push(deque.pop() * deque.pop());
        } 
        // 如果是除法操作符
        else if ("/".equals(s)) {
            // 弹出栈顶两个元素，做除法运算，结果压入栈中
            int num1 = deque.pop();
            int num2 = deque.pop();
            deque.push(num2 / num1);
        } 
        // 如果是操作数（数字）
        else {
            // 将操作数转换为整数并压入栈中
            deque.push(Integer.valueOf(s));
        }
    }
    
    // 返回栈中剩余的唯一元素，即为计算结果
    return deque.pop();
}