代码随想录Day9 栈与队列 LeetCodeT20 有效的括号 T1047 删除字符串中所有相邻重复项 T150 逆波兰表达式求值

题目详细思路和解法来自于:代码随想录 (programmercarl.com)

LeetCode T20 有效的括号

题目思路

这道题分为三种情况

1.左括号多了         ([{}]()

2.括号不匹配         [{(]}]

3.右括号多了         []{}())))

处理思路:我们在遇到左括号的时候,直接入栈其对应的右括号即可,然后在遇到右括号的时候直接与栈顶元素比较,注意一点,如果在遇到右括号时栈为空,那么就是不符合题意的,如果栈顶元素还和目前右括号不同,也是错误的,但是如果相同我们就进行弹栈,遍历完字符串之后查看栈是否为空,为空则已经完成.

题目代码

class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();
        Stack stack = new Stack<>();
        for(int i = 0;i
        {
            if(chars[i] == '(')
            {
                stack.push(')');
            }
            else if(chars[i] == '{')
            {
                stack.push('}');
            }
            else if(chars[i] == '[')
            {
                stack.push(']');
            }
            else if(stack.isEmpty() || stack.peek() != chars[i])
            {
                return false;
            }
 
            else
            {
                stack.pop();
            }
        }
        return stack.isEmpty();
 
    }
}

LeetCode T1047 删除字符串中所有相邻重复项

题目思路

使用栈结构,遍历该字符串,如果是空栈就进行压栈操作,如果不是空栈就用当前元素和栈顶元素进行比较,如果相同就进行弹栈操作,不同则继续压栈,遍历完将栈的元素放入字符串后进行一次反转字符串即可.(由于从栈冲取出元素顺序时反的)

优化:可以使用字符串来模拟栈的结构,可以节省栈来转字符串操作.

思路2:双指针 

定义快慢指针,快指针负责遍历整个字符串,慢指针负责寻找不重复位置的结束位置,利用覆盖来保证原地修改而不用创建新的字符串,处理过程如下

1.while循环快指针到字符串末尾为结束条件,首先将快指针指向的元素赋给慢指针的元素

2.判断慢指针是否大于0,大于0则和前面的一个元素作比较,相等就回退,其实也是意义上消除了一对相同的字母

3.如果不相同就继续向前走,循环往复,最后从0到slow指针的位置形成的字符串就是题目所求

题目代码

//利用栈操作
class Solution {
    public String removeDuplicates(String s) {
        char[] chars = s.toCharArray();
        Stack stack = new Stack<>();
        for(int i = 0;i
        {
            if(stack.isEmpty())
            {
                stack.push(chars[i]);
            }
            else if(chars[i] == stack.peek())
            {
                stack.pop();
            }
            else if(chars[i] != stack.peek())
            {
                stack.push(chars[i]);
            }
        }
        StringBuilder sb = new StringBuilder();  
        while (!stack.isEmpty()) {  
            sb.append(stack.pop());  
        }  
        return sb.reverse().toString();  
        
 
 
    }
}
 
 
 
 
 
 
 
//利用双指针写法
class Solution {
    public String removeDuplicates(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while(fast < s.length()){
            // 直接用fast指针覆盖slow指针的值
            ch[slow] = ch[fast];
            // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if(slow > 0 && ch[slow] == ch[slow - 1]){
                slow--;
            }else{
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
}

LeetCode T150 逆波兰表达式求值

逆波兰表达式解释

是一种后缀表达式，所谓后缀就是指运算符写在后面,这样方便计算机的读取

比如我们平常使用的算式就是中缀表达式,需要考虑优先级

有人到这里还不理解,我们这里举个例子

中缀表达式  ( 1 + 2 ) * ( 3 + 4 ) 

转换为后缀表达式

( ( 1 2 + ) ( 3 4 + ) * )

优点:

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果.

• 适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中.

• 本质:二叉树的中序遍历转换成了后序遍历

题目思路 

这里我们遇到数字就直接入栈,遇到+-*/等操作符就从栈中取出两个元素做操作,然后重新入栈,依次往复,最后答案就在栈中.(注:本题不考虑异常情况,所有的逆波兰表达式均合法)

注:栈中取出元素的时候记得对减法和除法处理,因为减法和除法的两个操作数顺序与答案所求顺序相反.

题目代码

class Solution {
    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        int num1,num2;
        for(String s:tokens)
        {
            if(s.equals("+"))
            {
               stack.push(stack.pop()+stack.pop());
            }
            else if(s.equals("-"))
            {
                stack.push(-stack.pop()+stack.pop());
            }
            else if(s.equals("*"))
            {
                stack.push(stack.pop()*stack.pop());
            }
            else if(s.equals("/"))
            {
                int tmp1 = stack.pop();
                int tmp2 = stack.pop();
                stack.push(tmp2/tmp1);   
            }
            else
            {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
 
 
    }
}