栈相关算法

ゝ一世哀愁。 2022-04-22 06:18 188阅读 0赞

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

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

class Solution {
        public boolean isValid(String s) {
            if (s == null || s.length() == 0) {
                return true;
            }
            final char[] charArray = s.toCharArray();
            final Stack<Character> stack = new Stack<Character>();
            for (char c : charArray) {
                if (c == '(' || c == '{' || c == '[') {
                    stack.add(c);
                } else if (c == ')' || c == '}' || c == ']') {
                    if (stack.isEmpty()) {
                        return false;
                    }
                    if (c == ')' && stack.peek() == '(') {
                        stack.pop();
                    } else if (c == '}' && stack.peek() == '{') {
                        stack.pop();
                    } else if (c == ']' && stack.peek() == '[') {
                        stack.pop();
                    } else {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

*  push(x) -- 将元素 x 推入栈中。
 *  pop() -- 删除栈顶的元素。
 *  top() -- 获取栈顶元素。
 *  getMin() -- 检索栈中的最小元素。

**示例:**

MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin();   --> 返回 -3.
    minStack.pop();
    minStack.top();      --> 返回 0.
    minStack.getMin();   --> 返回 -2.

class MinStack {
    
        /** initialize your data structure here. */
        Stack<Integer> stack;
        Stack<Integer> minStack;
        /** initialize your data structure here. */
        public MinStack() {
            stack = new Stack<Integer>();
            minStack = new Stack<Integer>();
        }
        
        public void push(int x) {
            if (minStack.isEmpty() || getMin() > x) {
                minStack.push(x);
            } else {
                minStack.push(getMin());
            }
            stack.push(x);
        }
        
        public void pop() {
            if (!stack.isEmpty()) {
                stack.pop();
                minStack.pop();
            }
        }
        
        public int top() {
            return stack.peek();
        }
        
        public int getMin() {
            return minStack.peek();
    }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 `(` ，右括号 `)`，加号 `+` ，减号 `-`，**非负**整数和空格 ` `。

**示例 1:**

输入: "1 + 1"
    输出: 2

**示例 2:**

输入: " 2-1 + 2 "
    输出: 3

**示例 3:**

输入: "(1+(4+5+2)-3)+(6+8)"
    输出: 23

**说明：**

*  你可以假设所给定的表达式都是有效的。
 *  请**不要**使用内置的库函数 `eval`。

public class Solution {
        public int calculate(String s) {
            if(s == null || s.length() == 0)
                return 0;
            s = "(" + s + ")";
            Stack<Character> cstack = new Stack<Character>();
            Stack<Integer> istack = new Stack<Integer>();
            
            boolean isNum = false;
            int sum = 0;
            
            for(int i = 0 ; i < s.length() ; i++){
                if(s.charAt(i) == ' ')
                    continue;
                if(Character.isDigit(s.charAt(i))){
                    sum = sum *10 + s.charAt(i) - '0';
                    isNum = true;
                    continue;
                }else if(isNum){  //考虑到会有 (( 连续的非数字情况 只需压入一次数字
                    istack.push(sum);
                    sum = 0;
                    isNum = false;
                }
                
                if(s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '('){
                    cstack.push(s.charAt(i));
                }else if(s.charAt(i) == ')'){
                    int temp = 0;  // 每一次括号里的值
                    while(cstack.peek() != '('){  //直到可以匹配的左括号
                        int a = istack.pop();
                        int c = cstack.pop();
                        if(c == '+'){
                            temp += a;
                        }else if(c == '-'){
                            temp -= a;
                        }
                    }
                    temp += istack.pop(); // 加上左括号后面的数字
                    istack.push(temp);
                    cstack.pop();
                }
            }
            
            return istack.pop();
        }
    }

使用栈实现队列的下列操作：

*  push(x) -- 将一个元素放入队列的尾部。
 *  pop() -- 从队列首部移除元素。
 *  peek() -- 返回队列首部的元素。
 *  empty() -- 返回队列是否为空。

**示例:**

MyQueue queue = new MyQueue();
    
    queue.push(1);
    queue.push(2);  
    queue.peek();  // 返回 1
    queue.pop();   // 返回 1
    queue.empty(); // 返回 false

**说明:**

*  你只能使用标准的栈操作 -- 也就是只有 `push to top`, `peek/pop from top`, `size`, 和 `is empty` 操作是合法的。
 *  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 *  假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

class MyQueue {
    
        Stack<Integer> stack;
        Stack<Integer> reverseStack;
        /** Initialize your data structure here. */
        public MyQueue() {
            stack = new Stack<>();
            reverseStack = new Stack<>();
        }
        
        /** Push element x to the back of queue. */
        public void push(int x) {
            while (!reverseStack.isEmpty()) {
                stack.push(pop());
            }
            stack.push(x);
    
            // Pure back
            while (!stack.isEmpty()) {
                reverseStack.push(stack.pop());
            }
        }
        
        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            return reverseStack.pop();
        }
        
        /** Get the front element. */
        public int peek() {
            return reverseStack.peek();
        }
        
        /** Returns whether the queue is empty. */
        public boolean empty() {
            return reverseStack.isEmpty();
        }
    }
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue obj = new MyQueue();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.peek();
     * boolean param_4 = obj.empty();
     */

给定两个**没有重复元素**的数组 `nums1` 和 `nums2` ，其中`nums1` 是 `nums2` 的子集。找到 `nums1` 中每个元素在 `nums2` 中的下一个比其大的值。

`nums1` 中数字 **x** 的下一个更大元素是指 **x** 在 `nums2` 中对应位置的右边的第一个比 **x **大的元素。如果不存在，对应位置输出-1。

**示例 1:**

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
    输出: [-1,3,-1]
    解释:
        对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
        对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
        对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

**示例 2:**

输入: nums1 = [2,4], nums2 = [1,2,3,4].
    输出: [3,-1]
    解释:
        对于num1中的数字2，第二个数组中的下一个较大数字是3。
        对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。

**注意:**

1.  `nums1`和`nums2`中所有元素是唯一的。
2.  `nums1`和`nums2` 的数组大小都不超过1000。

class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int m = nums1.length, n = nums2.length;
            int[] result = new int[m];
            Map<Integer, Integer> pos = new HashMap<>();
            for (int i = 0; i < n; i++) {
                pos.put(nums2[i], i);
            }
            for (int i = 0; i < m; i++) {
                result[i] = check(nums2, pos.get(nums1[i]), nums1[i]);
            }
            return result;
        }
        
        private int check(int[] nums, int index, int val) {
            for (int i = index; i < nums.length; i++) {
                if (nums[i] > val) return nums[i];
            }
            return -1;
        }
    }

给定 `S` 和 `T` 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 `#` 代表退格字符。

**示例 1：**

输入：S = "ab#c", T = "ad#c"
    输出：true
    解释：S 和 T 都会变成 “ac”。

**示例 2：**

输入：S = "ab##", T = "c#d#"
    输出：true
    解释：S 和 T 都会变成 “”。

**示例 3：**

输入：S = "a##c", T = "#a#c"
    输出：true
    解释：S 和 T 都会变成 “c”。

**示例 4：**

输入：S = "a#c", T = "b"
    输出：false
    解释：S 会变成 “c”，但 T 仍然是 “b”。

**提示：**

1.  `1 <= S.length <= 200`
2.  `1 <= T.length <= 200`
3.  `S` 和 `T` 只含有小写字母以及字符 `'#'`。

class Solution {
        public boolean backspaceCompare(String S, String T) {
            if (S == null || T == null) return false;
            
            return type(S).equals(type(T));
        }
        
        private String type(String s) {
            Stack<Character> stack = new Stack<>();
            for (char c : s.toCharArray()) {
                if (c == '#') {
                    if (!stack.isEmpty()) stack.pop();
                } else {
                    stack.push(c);
                }
            }
            StringBuffer sb = new StringBuffer();
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }
            return sb.toString();
        }
    }