[每日两题系列]刷算法题咯~~

        本系列所选题目均来自力扣或者牛客网站. 所选题目主要是以其中的简单题为主, 中等题为辅, 包含少数困难题(原因是: 本人目前能力还不够~ ). 开展这个系列的目的是督促自己, 在暑假的时间里也要保持有一定的刷题量, 拒绝摆烂~
        话不多说, 直接开刷~~

最小栈

        题目描述: 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
        实现 MinStack 类:
        1. MinStack() 初始化堆栈对象。
        2. void push(int val) 将元素val推入堆栈。
        3. void pop() 删除堆栈顶部的元素。
        4. int top() 获取堆栈顶部的元素。
        5. int getMin() 获取堆栈中的最小元素。

解题思路:
        (1) 这是一种经典设计类的题目, 在这道题中, 我们需要同时维护两个栈 — 普通栈 & 最小栈.
        (2) 添加元素: 直接都先加到普通栈中(对于第一个元素也直接加入最小栈即可), 从第二个元素开始, 如果新添加的元素的值小于最小栈中栈顶元素的值, 那么可以将这个元素压到最小栈的栈顶, 否则不做任何处理.
        (3) 删除元素: 直接将普通栈的栈顶元素删除, 判断该元素的值是否是最小栈栈顶元素的值, 如果是则将最小栈的栈顶元素也删除, 否则不做任何操作.

实现代码:

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minstack;

    public MinStack() {
        stack=new Stack<>();
        minstack=new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minstack.empty()){
            minstack.push(val);
        }else{
            if(minstack.peek()>=val){
                minstack.push(val);
            }
        }
    }
    
    public void pop() {
        int x=stack.pop();
        if(x==minstack.peek()){
            minstack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minstack.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

有效的括号

        题目描述: 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
        有效字符串需满足：
        1. 左括号必须用相同类型的右括号闭合。
        2. 左括号必须以正确的顺序闭合。

解题思路:
        (1) 总体的思路是: 遍历这个字符串, 当遍历到一个字符是左括号的时候, 就将这个字符入栈; 反之, 当这个字符是一个有括号, 就将这个字符出栈.
        (2) 如果是如栈, 我们并不需要做出任何的判断; 如果是出栈, 则需要找到有与出栈括号类型对应的左括号, 如果没找到匹配的左括号或者是栈是空的, 那么可以说明这个字符串是无效的.
        (3) 直到将字符串遍历完, 这时候判断栈是否是空的, 如果是, 则说明这个字符串是有效的; 否则是无效的.

实现代码:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        int len=s.length();
        for(int i=0;i<len;i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='{'||ch=='['){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char c=stack.peek();
                if(c=='('&&ch==')'||c=='{'&&ch=='}'||c=='['&&ch==']'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        if(stack.empty()){
            return true;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26