Weekly Algorithm Summary II -Stack 算法周记-栈

Swift 实现栈 Stack
Leecode 相关的题

本周，重温算法中关于单链表的内容，主要涉及：

用Swift实现了单/双链表
用C实现单链表的一些常见操作
刷 Leecode

Swift 实现栈 Stack

栈是很常见的数据结构，下面是Swift实现的 class版：

class ZZHStack<T> {

    private var array = [T]()
    var size: Int {
        get {
            return self.array.count
        }
    }

    var isEmpty: Bool {
        get {
            return self.array.count == 0
        }
    }
    func push(value: T) {
        self.array.append(value)
    }

    func pop() -> T? {
        let last = self.array.removeLast()
        return last
    }
    func peek() -> T? {
        return array.last
    }

}

Leecode 相关的题

844 Backspace String Compare

比较含退格的字符串，难度：简单。
思路：使用栈，当遇到”#”将栈 pop即可。

20 Valid Parentheses

有效的括号，难度：简单。
本题使用了 C 解答

bool isValid(char *s){

    if(s == NULL){
        return false;
    }
    int length = strlen(s);
    if (length == 0) {
        return true;
    }
    if (length % 2 != 0 ) {
        return false;
    }
    char *stack = (char *)malloc(sizeof(char) * length);
    memset(stack, 0, length/2);
    char current;
    int index = 0;
    for (int i = 0; i < length; i++) {
        current = s[i];
        if (current == '('
            ||current == '{'
            ||current == '['){
                stack[index] = current;
                index ++;
            }else {
                if (strlen(stack) == 0) {
                    return false;
                }
                char last = stack[index - 1];
                if ((last == '(' && current == ')')
                    ||(last == '[' && current == ']')
                    ||(last == '{' && current == '}')) {
                    stack[index - 1] = '\0';
                    index --;
                }
            }//end if
    }//end for
    return strlen(stack) == 0;
}

155 Min Stack

最小栈，难度：简单。
思路：因为获取最小元素时要 O(1)，内部要使用两个数组，一个用于存放栈的实际元素，一个用于存放当前情况下的最小元素。需要在 push 和 pop 的时候，思考最小元素的数组如何更新。

class MinStack {
    private var array = [Int]()
    private var minArray = [Int]()
    /** initialize your data structure here. */
    init() {

    }

    func push(_ x: Int) {
        array.append(x)
        if minArray.last == nil || minArray.last! >= x {
            minArray.append(x)
        }

        //print("push:\(array)\n \(minArray)")
    }

    func pop() {
        let poped = array.removeLast()
        if poped == minArray.last {
            minArray.removeLast()
        }
        //print("pop:\(array)\n \(minArray)")
    }

    func top() -> Int {
        if array.count == 0 {
            return 0
        }
        return array.last!
        return array.last ?? 0
    }

    func getMin() -> Int {
        if minArray.count == 0 {
            return 0
        }
        return minArray.last!
        return minArray.last ?? 0
    }
}

232 Implement Queue using Stacks

用栈实现队列，难度：简单。
因为栈和队列的元素进出顺序不同，因此需要使用辅助栈来实现队列。

class ZZHStack {
    private var array: [Int] = [Int]()
    /** initialize your data structure here. */
    init() {
    }

    func push(_ x: Int) {
        array.append(x)
    }

    func pop() -> Int {
        return array.removeLast() 
    }

    func top() -> Int {
        return array.last ?? 0
    }
    func isEmpty() -> Bool {
        return array.isEmpty
    }
}
extension ZZHStack: CustomStringConvertible {
    var description: String {
        if array.count > 0 {
            return "stack: \(array.description)"
        }else {
            return "stack empty"
        }
    }

}
class MyQueue {
    private var mainStack = ZZHStack()
    private var helperStack = ZZHStack()
    private var firstObj = 0
    /** Initialize your data structure here. */
    init() {

    }

    /** Push element x to the back of queue. */
    func push(_ x: Int) {
        if mainStack.isEmpty() == true {
            firstObj = x
        }
        mainStack.push(x)
        //print("after push \(x) mainStack:\(mainStack.description)")

    }

    /** Removes the element from in front of queue and returns that element. */
    func pop() -> Int {
        if helperStack.isEmpty() == true {
            while mainStack.isEmpty() == false {
                helperStack.push(mainStack.pop())
            }
            return helperStack.pop()
        }else {
         return helperStack.pop()
        }
        return 0
    }

    /** Get the front element. */
    func peek() -> Int {
        //print("before peek mainStack:\(mainStack.description)")
        if helperStack.isEmpty() == false {
            return helperStack.top()
        }
        return firstObj
    }

    /** Returns whether the queue is empty. */
    func empty() -> Bool {
        //print("before empty mainStack:\(mainStack.description)")
        return mainStack.isEmpty() && helperStack.isEmpty()
    }
}

496 Next Greater Element I

下一个更大元素 I，难度：简单。
一开始想的方法是先找到第一个数组中元素在第二个数组中的位置，然后再寻找。这样的话，效率差，需要O(m*n)。后来意识到，数组1是数组2的子集，可以先把数组2中各个元素对应的下一个元素找出来，存储在一个Dictionary中。

class Solution {
    func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var result = [Int]()
        var array = [Int]()//as stack
        var dic = [Int: Int]()
        for num in nums2 {
            if array.isEmpty == true {
                array.append(num)
            }else {

                while  array.isEmpty == false && num > (array.last)! {
                    dic[(array.popLast())!] = num
                }

                array.append(num)

            }
        }
        while array.isEmpty == false {
            dic[(array.popLast())!] = -1
        }
        for num in nums1 {
            result.append(dic[num]!)
        }
        return result
    }
}

224 Basic Calculator

基本计算器，难度：困难。
基本计算器中只有加减运算和括号，使用两个栈，一个存操作数，一个存操作符。

class ZZHStack<T> {
    private var array = [T]()
    var size: Int {
        get {
            return self.array.count
        }
    }
    var isEmpty: Bool {
        get {
            return self.array.count == 0
        }
    }
    func push(value: T) {
        self.array.append(value)
    }
    func pop() -> T? {
        let last = self.array.removeLast()
        return last
    }
    func peek() -> T? {
        return array.last
    }  
}
class Solution {
    func calculate(_ s: String) -> Int {
        let operatorStack = ZZHStack<Character>()
        let numStack = ZZHStack<Int>()
        var isPreNum = false
        for ch in s {
            switch ch {
            case "(":
                isPreNum = false
                operatorStack.push(value: ch)
            case ")":
                isPreNum = false
                var ope = (operatorStack.pop())!
                while ope != "(" && operatorStack.isEmpty == false {
                    let lastNum = numStack.pop()!
                    let lastSecond = numStack.pop()!
                    if ope == "-" {
                        numStack.push(value: lastSecond - lastNum)
                    }else {
                        numStack.push(value: lastSecond + lastNum)
                    }
                    ope = operatorStack.pop()!
                }
            case "+", "-":
                isPreNum = false
                if operatorStack.isEmpty == true || operatorStack.peek()! == "(" {
                    operatorStack.push(value: ch)
                }else {
                    while operatorStack.isEmpty == false && operatorStack.peek()! != "(" {
                        let ope = operatorStack.pop()!
                        let lastNum = numStack.pop()!
                        let lastSecond = numStack.pop()!
                        let result = ope == "+" ? (lastSecond + lastNum) : (lastSecond - lastNum)
                        numStack.push(value: result)
                    }
                    operatorStack.push(value: ch)
                }
            case " ":
                isPreNum = false
                continue
            default:
                if isPreNum {
                    numStack.push(value: ch.wholeNumberValue! + numStack.pop()! * 10)
                }else {
                    numStack.push(value: ch.wholeNumberValue!)
                }
                isPreNum = true
            }
        }
        while operatorStack.isEmpty == false {
            let ope = (operatorStack.pop())!
            let lastNum = numStack.pop()!
            let lastSecond = numStack.pop()!
            if ope == "-" {
                numStack.push(value: lastSecond - lastNum)
            }else {
                numStack.push(value: lastSecond + lastNum)
            }
        }
        return (numStack.peek())!
    }
}

这样做效率不高，Leecode-cn 上显示执行用时在后10%，也太对不起该题的难度。这种解法存在太多的出入栈，考虑到式子只包含加减和括号，可以有新的思路：把减号当作后一个数字的符号，这样整个运算就变成了加法运算。
以不包含括号的情形为例：

遇到数字，赋给操作数num，作为操作数–这里需要注意连续数字的情况处理
遇到+/-，先把当前的num和符号位sign运算后，加到结果result上；保存sign并置num为0

如果存在括号，那么就要去括号，求出下一个数字的符号，比如：

1-(2-3) => 1-2+3

而要做到这一点，需要用到一个栈，遇到左括号时，把当前的符号为入栈，括号内的数字通过栈顶和当前符号位来确定正负。完整的流程：

遇到左括号，将当前sign压栈
遇到右括号，弹出栈
遇到数字，赋给num–同样注意连续数字的情况处理
遇到+/-，先把当前的num和sign运算后，加到result上；保存sign：当前的sign为下一个操作数准备，需要当前操作符和栈顶操作符共同确定sign值，并置num为0

代码实现：

class Solution {
    func calculate(_ s: String) -> Int {
        let operatorStack = ZZHStack<Int>()
        var result = 0
        var operands = 0
        var sign = 1
        operatorStack.push(value: sign)
        for ch in s {
            switch ch {
            case "(":
                operatorStack.push(value: sign)
            case ")":
                operatorStack.pop()
            case "+", "-":
                result = result + sign * operands
                sign = ((ch == "+") ? 1 : -1) * operatorStack.peek()!
                operands = 0
            case " ":
                continue
            default:
                operands = operands * 10 + ch.wholeNumberValue!

            }
        } 
        return result + sign * operands
    }
}

Out of Comfort Zone

算法周记-栈