大厂算法面试之 leetcode 精讲 17. 栈

  42/2 42%2=0  21/2 21%2=1  10/2 10%2=0  5/2   5%2=1  2/2   2%2=0  1/2   1%2=1  stack: [0,1,0,1,0,1]  res:    1 0 1 0 1 0    fn1(){    fn2()  }  fn2(){      fn3()    }  fn3(){}  fn1()    stack:[fn1,fn2,fn3]

var isValid = function(s) {    const n = s.length;    if (n % 2 === 1) {//如果字符串能组成有效的括号，则长度一定是偶数        return false;    }    const pairs = new Map([//用栈存储括号对        [')', '('],        [']', '['],        ['}', '{']    ]);    const stk = [];    for (let ch of s){//循环字符串        if (pairs.has(ch)) {            //遇到右括号则判断右括号是否能和栈顶元素匹配            if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {                return false;            }            stk.pop();        } else {            stk.push(ch);//如果遇到左括号入栈        }    };    return !stk.length;//循环结束的时候还要判断栈是否为空};

class Solution {    public boolean isValid(String s) {        int n = s.length();        if (n % 2 == 1) {            return false;        }
        Map<Character, Character> pairs = new HashMap<Character, Character>() {{            put(')', '(');            put(']', '[');            put('}', '{');        }};        Deque<Character> stack = new LinkedList<Character>();        for (int i = 0; i < n; i++) {            char ch = s.charAt(i);            if (pairs.containsKey(ch)) {                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {                    return false;                }                stack.pop();            } else {                stack.push(ch);            }        }        return stack.isEmpty();    }}

var MyQueue = function() {  //准备两个栈   this.stack1 = [];   this.stack2 = [];};
MyQueue.prototype.push = function(x) {//push的时候加入输入栈   this.stack1.push(x);};
MyQueue.prototype.pop = function() {   const size = this.stack2.length;   if(size) {//push的时候判断输出栈是否为空       return this.stack2.pop();//不为空则输出栈出栈   }   while(this.stack1.length) {//输出栈为空，则把输入栈所有的元素加入输出栈       this.stack2.push(this.stack1.pop());   }   return this.stack2.pop();};
MyQueue.prototype.peek = function() {   const x = this.pop();//查看队头的元素 复用pop方法，然后在让元素push进输出栈   this.stack2.push(x);   return x;};
MyQueue.prototype.empty = function() {   return !this.stack1.length && !this.stack2.length};

class MyQueue {
    Stack<Integer> stack1;    Stack<Integer> stack2;
    public MyQueue() {        stack1 = new Stack<>();        stack2 = new Stack<>();    }        public void push(int x) {        stack1.push(x);    }        public int pop() {            dumpStack1();        return stack2.pop();    }        public int peek() {        dumpStack1();        return stack2.peek();    }        public boolean empty() {        return stack1.isEmpty() && stack2.isEmpty();    }
    private void dumpStack1(){        if (stack2.isEmpty()){            while (!stack1.isEmpty()){                stack2.push(stack1.pop());            }        }    }}

var MinStack = function () {    this.stack = [];    this.min_stack = [Infinity];};
//stack正常push，min_stack只会push需要入栈和栈顶中较小的元素MinStack.prototype.push = function (x) {    this.stack.push(x);    this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));};
//stack正常pop，min_stack正常popMinStack.prototype.pop = function () {    this.stack.pop();    this.min_stack.pop();};
//返回stack栈顶元素MinStack.prototype.top = function () {    return this.stack[this.stack.length - 1];};
//返回min_stack栈顶元素MinStack.prototype.getMin = function () {    return this.min_stack[this.min_stack.length - 1];};

class MinStack {  Deque<Integer> stack;  Deque<Integer> minStack;
  public MinStack() {      stack = new LinkedList<Integer>();      minStack = new LinkedList<Integer>();      minStack.push(Integer.MAX_VALUE);  }    public void push(int x) {      stack.push(x);      minStack.push(Math.min(minStack.peek(), x));  }    public void pop() {      stack.pop();      minStack.pop();  }    public int top() {      return stack.peek();  }    public int getMin() {      return minStack.peek();  }}

const validateStackSequences = (pushed, popped) => {    const stack = [];//用栈模拟出栈入栈的过程    let index = 0;    const len = pushed.length;    for (let i = 0; i < len; i++) {        stack.push(pushed[i]);        //当popped中index指向的位置的元素和stack栈顶的元素一致时，出栈 并且 index++        while (popped[index] !== undefined && popped[index] === stack[stack.length - 1]) {            stack.pop();            index++;        }    }    return !stack.length;//最后判断stack是否为空};

class Solution {    public boolean validateStackSequences(int[] pushed, int[] popped) {        if(pushed == null){            return true;        }        Stack<Integer> stack = new Stack<>();        int index = 0;        for(int i=0;i<pushed.length;i++){            stack.push(pushed[i]);            while(!stack.isEmpty() && index < popped.length && popped[index] == stack.peek()){                int pop = stack.pop();                index++;            }        }        return stack.isEmpty();    }}

var addTwoNumbers = function(l1, l2) {    const stack1 = [];    const stack2 = [];    while (l1 || l2) {//两链表入栈        if (l1) {            stack1.push(l1.val);            l1 = l1.next;        }        if (l2) {            stack2.push(l2.val);            l2 = l2.next;        }    }    let carry = 0;    let ansList = null;    while (stack1.length || stack2.length || carry !== 0) {//不断出栈        const s1 = stack1.length ? stack1.pop() : 0;        const s2 = stack2.length ? stack2.pop() : 0;        let val = s1 + s2 + carry;        carry = parseInt(val / 10);//计算进位        val = val % 10;//计算当前节点的值        const curNode = new ListNode(val);        curNode.next = ansList;//向链表前插入新节点        ansList = curNode;//重新赋值ansList    }    return ansList;};

class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        Deque<Integer> stack1 = new LinkedList<Integer>();        Deque<Integer> stack2 = new LinkedList<Integer>();        while (l1 != null) {            stack1.push(l1.val);            l1 = l1.next;        }        while (l2 != null) {            stack2.push(l2.val);            l2 = l2.next;        }        int carry = 0;        ListNode ansList = null;        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {            int s1 = stack1.isEmpty() ? 0 : stack1.pop();            int s2 = stack2.isEmpty() ? 0 : stack2.pop();            int val = s1 + s2 + carry;            carry = val / 10;            val %= 10;            ListNode curNode = new ListNode(val);            curNode.next = ansList;            ansList = curNode;        }        return ansList;    }}

let calPoints = function(ops) {    let res = [];    for(let i = 0; i < ops.length; i++){        switch(ops[i]){            case "C":                res.pop();                break;            case "D":                res.push(+res[res.length - 1] * 2);                break;            case "+":                res.push(+res[res.length - 1] + +res[res.length - 2]);                break;            default:                res.push(+ops[i]);        }    }    return res.reduce((i, j) => i + j);};

class Solution {    public int calPoints(String[] ops) {        Stack<Integer> stack = new Stack();
        for(String op : ops) {            if (op.equals("+")) {                int top = stack.pop();                int newtop = top + stack.peek();                stack.push(top);                stack.push(newtop);            } else if (op.equals("C")) {                stack.pop();            } else if (op.equals("D")) {                stack.push(2 * stack.peek());            } else {                stack.push(Integer.valueOf(op));            }        }
        int ans = 0;        for(int score : stack) ans += score;        return ans;    }}