当前位置：首页 > article >正文

【算法】栈

article 2024/12/22 5:21:14

阿华代码，不是逆风，就是我疯

你们的点赞收藏是我前进最大的动力！！

希望本文内容能够帮助到你！！

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

二：比较含退格的字符串

三：基本计算器

四：字符串解码

五：验证栈序列

牛客网

一：有效括号序列

一：删除字符串中的所有相邻重复项

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

模拟重力消消乐

class Solution {
    public String removeDuplicates(String ss) {
        //用数组模拟栈
        StringBuffer buffer = new StringBuffer();
        //先把字符串转化为字符数组，在进行遍历
        char[] s = ss.toCharArray();
        //在进行条件判断
        
        for(char ch : s){
            //如果栈不为空，并且ch == 栈顶元素，那就出栈
            if(buffer.length() > 0  && ch == buffer.charAt(buffer.length()-1)){
                buffer.deleteCharAt(buffer.length()-1);
            }else{ // 栈为空 或者 ch ！= 栈顶元素那就进栈
                buffer.append(ch);
            }
        }
        return buffer.toString();
        
    }
}

二：比较含退格的字符串

844. 比较含退格的字符串 - 力扣（LeetCode）

太赖皮了，还能优化，可以写成函数的形式，代码优化复用

传统栈的解法

用完StringBuffer后记得转换成String类型才能使用equals()方法

class Solution {
    public boolean backspaceCompare(String ss, String tt) {
        Stack<Character> s1 = new Stack<>();
        Stack<Character> t1 = new Stack<>();


        char[] s = ss.toCharArray();
        for(char ch : s){
            if(!s1.isEmpty() && ch == '#'){
                s1.pop();
            }else if(ch != '#'){
                s1.push(ch);
            }
        }

        char[] t = tt.toCharArray();
        for(char ch : t){
            if(!t1.isEmpty() && ch == '#'){
                t1.pop();
            }else if(ch != '#'){
                t1.push(ch);
            }
        }

        if(s1.isEmpty() && t1.isEmpty()){
            return true;
        }
        
        StringBuffer str1  = new StringBuffer();
        while(!s1.isEmpty()){
            str1.append(s1.pop());
        }

        StringBuffer str2  = new StringBuffer();
        while(!t1.isEmpty()){
            str2.append(t1.pop());
        }
        String x = str1.toString();
        String y = str2.toString();

        return x.equals(y);
    }
}

解法二：数组模拟栈

class Solution {
    public boolean backspaceCompare(String ss, String tt) {
        return changeStr(ss).equals(changeStr(tt));
    }

    // 这个方法是用来模拟栈的出和进
    public String changeStr(String str){
        StringBuffer ret = new StringBuffer();

        for(int i = 0 ; i < str.length() ; i++){
            char ch = str.charAt(i);
            if(ch != '#'){
                ret.append(ch);
            }else if(!ret.isEmpty() && ch == '#'){//ret非空才能删除元素
                int len = ret.length();
                ret.deleteCharAt(len-1);
            }
        }
        return ret.toString();
    }
}

三：基本计算器

227. 基本计算器 II

class Solution {
    public int calculate(String ss) {
        // 1：new 一个栈
        Stack<Integer> stack = new Stack<>();
        // 2：遍历字符串
        char[] s = ss.toCharArray();
        int i = 0 , n = s.length;
        char op = '+';
        while(i < n){
            // 3：分情况讨论，重点是确定tem和字符的情况
            if(s[i] == ' ') i++;
             // 4：利用字符的ASCII码值进行字符和整型之间的转换
            else if(s[i] >= '0' && s[i] <= '9'){
                int tem = 0;
                while( (i < n) && (s[i] >= '0' && s[i] <= '9') ){
                    tem = 10 * tem + (s[i] - '0');
                    i++;//这里的if判断条件太巧妙了利用ASCII值,并且i++后的处理真是绝了
                }
                if(op == '+') stack.push(tem);
                else if(op == '-') stack.push(-tem);
                else if(op == '*') stack.push(stack.pop() * tem);
                else if(op == '/') stack.push(stack.pop() / tem);
            }else{
                op = s[i];
                i++;
            }
        }

        int ret = 0;
        while(!stack.isEmpty()){
            ret += stack.pop();
        }
       return ret;

        
    }
        
}

四：字符串解码

394. 字符串解码

class Solution {
    public String decodeString(String ss) {
        // 准备工作
        Stack<StringBuffer> str = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        char[] s = ss.toCharArray();
        int n = s.length, i = 0;
        str.push(new StringBuffer());//放一个空串

        // 遍历字符数组并分情况讨论
        while (i < n) {
            // 处理数字的情况
            if (s[i] >= '0' && s[i] <= '9') {
                int tem = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    tem = 10 * tem + (s[i] - '0');
                    i++;
                }
                // 处理完放入栈中
                nums.push(tem);
            }else if(s[i] == '['){//处理[]中的字符串,需要拼接一下字符
                i++;
                StringBuffer buffer = new StringBuffer();
                while(i < n && s[i] >= 'a' && s[i] <= 'z'){  //while(s[i] != ']')不能过
                    buffer.append(s[i]);
                    i++;
                }
                str.push(buffer);
            }else if(s[i] == ']'){
                StringBuffer s1 = str.pop();
                int num1 = nums.pop();
                StringBuffer tem = new StringBuffer();
                while(num1 != 0){
                    tem.append(s1);
                    num1--;
                }
                // 这里追加字符要考虑到栈顶为空的情况
                str.peek().append(tem);
                i++;
            }else{//这种情况是字符单独存在，需要直接追加到栈顶元素
                StringBuffer buffer = new StringBuffer();
                while(i < n && s[i] >= 'a' && s[i] <= 'z'){
                    buffer.append(s[i]);
                    i++;
                }
                str.peek().append(buffer);
            }

        }
        return str.pop().toString();
    }
}

五：验证栈序列

946. 验证栈序列

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //定义两个指针
        int i = 0 , j = 0 , n = pushed.length;
        Stack<Integer> stack = new Stack<>();
        while(i < n){
            if(i < n && pushed[i] != popped[j]){
                stack.push(pushed[i]);
                i++;
            }else{
                //不相等的时候，先进栈
                stack.push(pushed[i]);
                // 出栈
                while(i < n && !stack.isEmpty() && stack.peek() == popped[j]){
                    stack.pop();
                    j++;
                }
                i++;
            }
        }
        return stack.isEmpty();
    }
}

牛客网

一：有效括号序列

有效括号序列_牛客题霸_牛客网

压弹策略

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String ss) {
        // write code here
        Stack<Character> stack = new Stack<>();
        char[] s = ss.toCharArray();
        
        for(char ch : s){
            if(ch == '('){
                stack.push(')');
            }else if(ch == '{'){
                stack.push('}');
            }else if(ch == '['){
                stack.push(']');
            }else if(stack.isEmpty() || ch != stack.pop()){
                return false;
            }else{
                // 这里的条件已经是出栈了，所以不用再写pop方法了
            }
        }
        return stack.isEmpty();
    }
}

查看全文

http://www.kler.cn/a/446060.html