栈和队列编程题集合（leetcode)

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

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

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

输入：”abbaca”

输出：”ca”

解释：

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

public  String removeDuplicates(String s) {
        LinkedList<Character> queue=new LinkedList<>();
        for(int i=0;i<s.length();i++){
            if(queue.isEmpty()){
                queue.add(s.charAt(i));
            }
            else{
                if(queue.peekLast()!=s.charAt(i))
                    queue.addLast(s.charAt(i));
                else
                queue.removeLast();
            }
        }
        String result="";
        while (!queue.isEmpty()){
            result=result+queue.removeFirst();
        }
        return result;
    }

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

输入：s = “()[]{}” 输出：true

public boolean isValid(String s) {        int n = s.length();        if (n % 2 == 1) {            return false;        }        Map<Character, Character> pairs = new HashMap<Character, Character>() {{            put(')', '(');            put(']', '[');            put('}', '{');        }};        Deque<Character> stack = new LinkedList<Character>();        for (int i = 0; i < n; i++) {            char ch = s.charAt(i);            if (pairs.containsKey(ch)) {                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {                    return false;                }                stack.pop();            } else {                stack.push(ch);            }        }        return stack.isEmpty();    }作者：LeetCode-Solution链接：https://leetcode.cn/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/来源：力扣（LeetCode）

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

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

注意：

有效的算符为 ‘+’、’-‘、’*’ 和 ‘/’ 。

每个操作数（运算对象）都可以是一个整数或者另一个表达式。

两个整数之间的除法总是向零截断。

表达式中不含除零运算。

输入是一个根据逆波兰表示法表示的算术表达式。

答案及所有中间计算结果可以用 32 位整数表示。

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

public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }

    public boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/143055.html

栈和队列编程题集合（leetcode)

相关推荐

发表回复