NC76 用两个栈实现队列

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： n\le1000n≤1000

要求：存储n个元素的空间复杂度为 O(n)O(n) ，插入与删除的时间复杂度都是 O(1)O(1)

示例1

输入：

1
["PSH1","PSH2","POP","POP"]

返回值：

1
1,2

说明：

1
2
3
4
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2

示例2

输入：

1
["PSH2","POP","PSH1","POP"]

返回值：

1
2,1

思路：

  • push操作就直接往stack1中push
  • pop操作需要分类一下：如果stack2为空，那么需要将stack1中的数据全部转移到stack2中，然后在对stack2进行pop，如果stack2不为空，直接pop就ok。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack1.empty() && stack2.empty()) {
            return 0;
        }
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop())
            }
        }
        return stack2.pop();
    }
}

NC52 有效括号序列

描述

给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。

数据范围：字符串长度 0\le n \le 100000≤n≤10000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例1

输入：

1
"["

返回值：

1
false

示例2

输入：

1
"[]"

返回值：

1
true

思路：

  • 先进后出的话hashMap不好解决
  • 利用栈的先后进先出
  • 每次匹配左半边括号push右半边
  • 匹配右半边括号pop
  • 为空或者匹配不等于最近push进去的值则退出

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        Stack<Character> stack = new Stack<Character>();
        for(char c : s.toCharArray()){
            if(c == '(') 
                stack.push(')');
            else if(c == '{') 
                stack.push('}');
            else if(c == '[') 
                stack.push(']');
            else if(stack.isEmpty() || stack.pop() != c)
                return false;
        }
        return stack.isEmpty();
    }
}