LeetCode刷题：栈、队列和递归

关于栈、队列和递归的几个必知必会的代码实现

栈

• 用数组实现一个顺序栈

• 用链表实现一个链式栈

• 编程模拟实现一个浏览器的前进、后退功能

队列

• 用数组实现一个顺序队列

• 用链表实现一个链式队列

• 实现一个循环队列

递归

• 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)

• 编程实现求阶乘 n!

• 编程实现一组数据集合的全排列

栈题目

Valid Parentheses（有效的括号）

题目：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true

思路：

初始化栈 S。
依次处理表达式的每个括号。
如果遇到开括号，入栈上即可。
如果遇到一个闭括号，那么检查栈顶的元素。如果栈顶的元素是一个相同类型的左括号，那么将它从栈中弹出并继续处理。
如果到最后剩下的栈中仍然有元素，那么这意味着表达式无效。

代码如下：

public boolean isValid(String s) {
    char[] sChar = s.toCharArray();
    Stack<Character> s1 = new Stack<>();
    int i = 0;
    while (i < sChar.length){
        if (!s1.isEmpty()) {
            if (sChar[i] == ')') {
                if (s1.peek() == '(')
                    s1.pop();
                else
                    return false;
            } else if (sChar[i] == '}') {
                if (s1.peek() == '{')
                    s1.pop();
                else
                    return false;
            } else if (sChar[i] == ']') {
                if (s1.peek() == '[')
                    s1.pop();
                else
                    return false;
            }
            else
                s1.push(sChar[i]);
        }
        else
            s1.push(sChar[i]);
        i++;
    }
    return s1.isEmpty();
}

Longest Valid Parentheses（最长有效的括号）

题目：

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

思路：

本人没有太好的思路，就去偷瞄官方题解了。。。官方题解

代码如下：

public int longestValidParentheses(String s) {
    int maxans = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.empty()) {
                stack.push(i);
            } else {
                maxans = Math.max(maxans, i - stack.peek());
            }
        }
    }
    return maxans;
}

Evaluate Reverse Polish Notatio（逆波兰表达式求值）

题目：

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

思路：

定义一个栈辅助计算;
当遇到运算符”+”、”-“、”*”、”/“时,从栈中 pop 出两个数字计算，否则将数字入栈;

代码如下：

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String s : tokens) {
        if (s.equals("+")) {
            stack.push(stack.pop() + stack.pop());
        } else if (s.equals("-")) {
            stack.push(-stack.pop() + stack.pop());
        } else if (s.equals("*")) {
            stack.push(stack.pop() * stack.pop());
        } else if (s.equals("/")) {
            int num1 = stack.pop();
            stack.push(stack.pop() / num1);
        } else {
            stack.push(Integer.parseInt(s));
        }
    }
    return stack.pop();
}

队列题目

Design Circular Deque（设计一个双端队列）

题目：

设计实现双端队列。
你的实现需要支持以下操作：

• MyCircularDeque(k)：构造函数,双端队列的大小为 k。
• insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
• insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
• deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
• deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
• getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
• getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
• isEmpty()：检查双端队列是否为空。
• isFull()：检查双端队列是否满了。

思路：

使用循环数组来实现避免数据迁移，这里直接记录size来做判断队列空还是满，需要注意的是在插入头部时，头部指针回退一位的处理；和删除尾部时，尾部指针回退一位的处理

代码如下：

public static final int DEFAULT_CAPACITY = 10;

    private int size;
    private int capacity;
    private int[] elementData;
    private int head;
    private int tail;

    public MyCircularDeque(int k) {
        if (k <= 0) {
            k = DEFAULT_CAPACITY;
        }
        elementData = new int[k];
        capacity = k;
        head = 0;
        tail = 0;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        if (head - 1 < 0) {
            head = capacity - 1;
        } else {
            head--;
        }
        elementData[head] = value;
        size++;
        return true;
    }

    // 插入到队列尾部
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        elementData[tail] = value;
        tail = (tail + 1) % capacity;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        head = (head + 1) % capacity;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        if (tail - 1 < 0) {
            tail = capacity - 1;
        } else {
            tail--;
        }
        size--;
        return true;
    }

    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return elementData[head];
    }

    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        // 特别注意！！！！
        if (tail - 1 < 0) {
            return elementData[capacity - 1];
        }
        return elementData[tail - 1];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

Sliding Window Maximum（滑动窗口最大值）

题目：

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。
提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

进阶：

你能在线性时间复杂度内解决此题吗？

思路：

暴力法可以做，但是太慢了，给上官方题解

代码如下：

public int[] maxSlidingWindow(int[] nums, int k) {
  int n = nums.length;
  if (n * k == 0) return new int[0];
  if (k == 1) return nums;

  int [] left = new int[n];
  left[0] = nums[0];
  int [] right = new int[n];
  right[n - 1] = nums[n - 1];
  for (int i = 1; i < n; i++) {
    // from left to right
    if (i % k == 0) left[i] = nums[i];  // block_start
    else left[i] = Math.max(left[i - 1], nums[i]);

    // from right to left
    int j = n - i - 1;
    if ((j + 1) % k == 0) right[j] = nums[j];  // block_end
    else right[j] = Math.max(right[j + 1], nums[j]);
  }

  int [] output = new int[n - k + 1];
  for (int i = 0; i < n - k + 1; i++)
    output[i] = Math.max(left[i + k - 1], right[i]);

  return output;
}

递归题目

Climbing Stairs（爬楼梯）

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

思路：

暴力递归可以通过，但是有没有更好的方案呢，思考一下发现其实就是斐波那契数列 $Fib(n) = Fib(n−1) + Fib(n−2)$

代码如下：

public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    int first = 1;
    int second = 2;
    for (int i = 3; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }
    return second;
}

好了，就刷到这里了，有问题欢迎和我留言😉。