算法day24

2024-06-07 08:20

文章标签 算法 day24

本文主要是介绍算法day24，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第一题

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

解法：利用数组来模拟一下栈

对于上述字符串转换为字符数组，通过模拟栈的操作来解决这道题，当栈为空时下一位字符直接进行入栈操作，当当前数组中要入栈的字符和栈顶的字符相同时，进行出栈操作，同时字符数组进行向后移动一位的操作，一直这样进行，直到循环完整个字符串；

总综上所述，代码如下：解法：利用数组来模拟一下栈
class Solution {public String removeDuplicates(String s) {StringBuffer ret = new StringBuffer();char[] s1 = s.toCharArray();for(char ch : s1){if(ret.length() >0 && ch ==ret.charAt(ret.length() - 1)){//出栈ret.deleteCharAt(ret.length() - 1);}else{//进栈ret.append(ch);}}return ret.toString();}
}

第二题

844. 比较含退格的字符串

解法：利用数组来模拟一下栈

对于上述字符串转换为字符数组，通过模拟栈的操作来解决这道题，当入栈的字符不是#时，直接进行入栈操作，当当前数组中要入栈的是#也栈顶的字符相同是，进行出栈操作，同时字符数组进行向后移动一位的操作，一直这样进行，直到循环完整个字符串；

总综上所述，代码如下：
class Solution {public boolean backspaceCompare(String s, String t) {return backret(s).equals(backret(t));}public String backret(String s1){StringBuffer ret = new StringBuffer();char[] s2 = s1.toCharArray();for(char ch: s2 ){if(ch != '#') ret.append(ch);elseif(ret.length() > 0) {ret.deleteCharAt(ret.length()-1);}}return ret.toString();}
}

第三题

227. 基本计算器 II

本题的类型：表达式求值；

方法：利用栈来模拟计算过程

步骤如下：

步骤一：将原始字符串转换为字符数组

我们开始进行遍历数组，当遇到操作符时，要进行更新操作符变量op；

步骤二：

遇到数字，首先使用tmp变量方便完整的记录数字；

步骤三：

根据遇到的符号，处理不停的逻辑：

如果遇到的是“+”符号，将tmp直接进行入栈操作；

         如果遇到的是“-”符号，将-tmp直接进行入栈操作；

        如果遇到的是“*”符号，将tmp直接乘到栈顶的元素上；

         如果遇到的是“/”符号，将tmp直接除到栈顶的元素上；

步骤四：

将栈里面的所有数进行相加操作，得到结果并返回；

综上诉述，代码如下：
class Solution {public int calculate(String s) {Deque<Integer> st = new ArrayDeque<>();char op = '+';int i = 0,n = s.length();char[] s1 = s.toCharArray();while(i < n){if(s1[i] == ' ') i++;else if(s1[i] >='0' && s1[i] <= '9'){int tmp = 0;while(i < n && s1[i] >='0' && s1[i] <= '9'){tmp = tmp * 10 + (s1[i] - '0');i++;}if(op == '+') st.push(tmp);else if(op == '-') st.push(-tmp);else if(op == '*') st.push( st.pop() * tmp);else st.push(st.pop() / tmp);}else{op = s1[i];i++;}}int ret = 0;while(!st.isEmpty()){ret += st.pop();}return ret;}
}