算法日记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）是一种用于表示数学表达式的格式，它与传统的中缀表达式有所不同。在逆波兰表达式中，运算符在操作数的后面而不是中间，这样可以避免使用括号来指定运算符的优先级。相当于二叉树的后序遍历。
特点和优点：
-
无需括号：逆波兰表达式不需要括号来指定运算符的优先级，因为操作符与操作数的顺序已经明确。
-
后缀表达式：逆波兰表达式也被称为后缀表达式，因为操作符跟在操作数的后面。
-
易于计算：逆波兰表达式可以直接由计算机执行，而无需像中缀表达式那样进行优先级和结合性的复杂处理。
举例说明：
考虑一个简单的数学表达式 (3 + 4) * 5，其对应的逆波兰表达式为 3 4 + 5 *。
- 在逆波兰表达式中：
3和4是操作数。+是加法操作符，作用于前面的两个操作数。5是另一个操作数。*是乘法操作符，作用于前面的结果和最后一个操作数。
实现逆波兰表达式的计算：
使用栈来实现逆波兰表达式的计算是常见的方法：
-
遍历逆波兰表达式：
- 遇到操作数时，压入栈中。
- 遇到操作符时，从栈中弹出对应数量的操作数，进行计算，并将结果压入栈中。
-
计算最终结果：
- 遍历结束后，栈中唯一的元素即为整个表达式的计算结果。
题目：
给你一个字符串数组 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();
}
原文地址：https://blog.csdn.net/m0_74980681/article/details/140527751
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！