课程中提到的一个时间/算法复杂度的统计表

https://www.bigocheatsheet.com/

前置知识：栈：FILO 先入后出。队列：FIFO 先入先出

232. 用栈实现队列

解决办法：使用两个栈，一个输入栈，一个输出栈。规则：

1. 先全部进入输入栈（先进入的在输入栈栈顶），输出时，先从输入栈一个个 pop 岀来进入输出栈（先进入的在输出栈栈顶）。接着从输出栈输出即可。
2. 新加入元素时，需要先判断输出栈是否为空，不为空则先从输出栈输出，为空则重复步骤1。

class MyQueue() {

    /** Initialize your data structure here. */
    val inS = Stack<Int>()
    val outS = Stack<Int>()

    /** Push element x to the back of queue. */
    fun push(x: Int) {
        inS.push(x)
    }

    /** Removes the element from in front of queue and returns that element. */
    fun pop(): Int {
        if (outS.isNotEmpty()) {
            return outS.pop()
        }
        while (inS.isNotEmpty()) {
            outS.push(inS.pop())
        }
        return outS.pop()
    }

    /** Get the front element. */
    fun peek(): Int {
        if (outS.isNotEmpty()) {
            return outS.peek()
        }
        while (inS.isNotEmpty()) {
            outS.push(inS.pop())
        }
        return outS.peek()
    }

    /** Returns whether the queue is empty. */
    fun empty(): Boolean {
        return outS.empty() && inS.empty()
    }

}

225. 用队列实现栈

解决方法一：使用双端队列，一个就可以。（头进头出）

class MyStack() {

    /** Initialize your data structure here. */
    val deque = LinkedList<Int>()

    /** Push element x onto stack. */
    fun push(x: Int) {
        deque.push(x)
    }

    /** Removes the element on top of the stack and returns that element. */
    fun pop(): Int {
        return deque.removeFirst()
    }

    /** Get the top element. */
    fun top(): Int {
        return deque.peekFirst()
    }

    /** Returns whether the stack is empty. */
    fun empty(): Boolean {
        return deque.isEmpty()
    }

}

解决方法二：使用单端队列（Jvm系 都是一个类），步骤：

1. push 时：每次入队都需要循环调整，比如入队 1，2；循环调整 2，1；入队3，循环调整3，2，1。每次需要移动size-1 个元素。
2. pop 时：尾出即可，
3. top 时：使用 peek()即可

class MyStack() {

    /** Initialize your data structure here. */
    val deque = LinkedList<Int>()

    /** Push element x onto stack. */
    fun push(x: Int) {
        deque.push(x)
        for (i in 0 until deque.size - 1) {
            deque.push(deque.removeLast())
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    fun pop(): Int {
        return deque.removeLast()
    }

    /** Get the top element. */
    fun top(): Int {
        return deque.peekLast()
    }

    /** Returns whether the stack is empty. */
    fun empty(): Boolean {
        return deque.isEmpty()
    }

}

20. 有效的括号

解决方案一：使用栈进行匹配判断，规则如下：

1. 如果是左括号，则入栈。
2. 如果是右括号，则判断栈顶元素是否与其匹配。匹配则弹出栈顶元素，不匹配则直接无效。( Tips：匹配时可使用 map 进行键值配对)
3. 全部匹配完成后，判断栈是否为空，不为空则无效。

Kotlin 代码：

class SomeSolution {
    fun isValid(s: String): Boolean {
        //optimization
        if (s.length % 2 != 0) return false
        
        val chars = s.toCharArray()
        val stack = Stack<Char>()
        val map = mapOf('(' to ')', '{' to '}', '[' to ']')
        chars.forEach {
            if (map.containsKey(it)) {
                stack.push(it)
            } else {
                if (stack.isEmpty()) return false
                if (map[stack.peek()] != it) {
                    return false
                } else {
                    stack.pop()
                }
            }
        }
        return stack.isEmpty()
    }
}

解决方案二：开心消消乐（效率低，不推荐）

class Solution {
    fun isValid(s: String): Boolean {
        var str = s
        if (s.length % 2 != 0) return false
        while (str.contains("()") || str.contains("{}") || str.contains("[]")) {
            str = str.replace("()", "").replace("{}", "").replace("[]", "")
        }
        return str.isEmpty()
    }
}