This is the 27th day of my participation in the August Genwen Challenge.More challenges in August

Before writing JavaScript linked list brush questions, JavaScript linked list brush questions (2), JavaScript linked list brush questions (3), JavaScript linked list brush questions (4), JavaScript linked list brush questions (5), interested children can be washed, next brush two recursion and stack questions ~~

Stack to queue

Interview question 03.04. Turn stacks into queues

Implement a MyQueue class that uses two stacks to implement a queue.

Example:

MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // Return 1 queue.pop(); // Return 1 queue.empty(); / / returns falseCopy the code

Description:

  • You can only use standard stack operations — only push to Top, peek/ Pop from Top, size and is empty are legal.
  • Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it’s standard stack operations.
  • Assume that all operations are valid (for example, an empty queue does not call pop or PEEK).

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Set up two stacks S1 and S2 to simulate a queue, S2 is responsible for joining the queue, S1 is responsible for leaving the queue;

When S1 is empty, if S2 is not empty, the contents of S2 are pushed off the stack and then pushed onto S1.

​

Code implementation

// Implement a stack
class Stack {
    constructor() {
        this.stack = []
    }
    push(x) {
        this.stack.push(x);
    }
    pop() {
        if(this.empty()) return;
        let top = this.top();
        this.stack.pop()
        return top;
    }
    top() {
        return this.stack[this.size()-1]}empty() {
        return this.stack.length == 0;
    }
    size() {
        return this.stack.length; }}// Two stacks implement a queue
var MyQueue = function() {
    // Create two stacks
    this.s1 = new Stack();
    this.s2 = new Stack();
};
// If s1 is empty, press s2 into s1
MyQueue.prototype.transfer = function() {
    if(!this.s1.empty()) return;
    while(!this.s2.empty()) {
        this.s1.push(this.s2.pop())
    }
}

MyQueue.prototype.push = function(x) {
    this.s2.push(x);
};

MyQueue.prototype.pop = function() {
    this.transfer();
    let top = this.s1.top();
    this.s1.pop();
    return top;
};

MyQueue.prototype.peek = function() {
    this.transfer();
    return this.s1.top();
};

MyQueue.prototype.empty = function() {
    return this.s1.empty() && this.s2.empty();
};
Copy the code

Two, on and off the stack

682. The baseball game

You are the recorder of a special baseball game. This match is made up of a number of rounds, and points scored in past rounds may affect points scored in future rounds.

At the start of the game, the record was blank. You get a list of strings to record operations ops, where OPS [I] is the ith operation you need to record. Ops follows the following rules:

The integer x – represents the number of points gained for the turn x “+” – represents the number of points gained for the turn is the sum of the previous two scores. The question data ensures that this operation is always preceded by two valid scores. “D” – Indicates that the new score scored in this turn is twice the previous score. The question data ensures that this operation is always preceded by a valid score when recording it. “C” – indicates that the previous score is invalid and removed from the record. The question data ensures that this operation is always preceded by a valid score when recording it. Return the sum of all the scores in the record.

Example 1:

  • Input: ops = [“5″,”2″,”C”,”D”,”+”]
  • Output: 30
  • Explanation:
  • “5” – Record plus 5, record is now [5]
  • “2” – Record plus 2, record is now [5, 2]
  • “C” – invalidates and removes the record of the previous score, which is now [5].
  • “D” – record plus 2 * 5 = 10, record is now [5, 10].
  • “+” – Record plus 5 + 10 = 15, record is now [5, 10, 15].
  • The sum of all points 5 + 10 + 15 = 30

Example 2:

  • Input: ops = [“5″,”-2″,”4″,”C”,”D”,”9″,”+”,”+”]
  • Output: 27
  • Explanation:
  • “5” – Record plus 5, record is now [5]
  • “-2” – Record plus -2, record is now [5, -2]
  • “4” – Record plus 4, record is now [5, -2, 4]
  • “C” – invalidates the previous score and removes it, the record is now [5, -2]
  • “D” – record plus 2 * -2 = -4, record is now [5, -2, -4]
  • “9” – Record plus 9, record is now [5, -2, -4, 9]
  • “+” – record plus -4 + 9 = 5, record is now [5, -2, -4, 9, 5]
  • “+” – Record plus 9 + 5 = 14, record is now [5, -2, -4, 9, 5, 14]
  • The sum of all points 5 + -2 + -4 + 9 + 5 + 14 = 27

Example 3:

  • Input: ops = [“1”]
  • Output: 1.

Tip:

  • 1 <= ops.length <= 1000
  • Ops [I] is “C”, “D”, “+”, or a string representing an integer. Integer range is [-3 * 104, 3 * 104]
  • For the “+” operation, the question data ensures that the operation is always preceded by two valid scores
  • For “C” and “D” operations, the question data ensures that the operation is always preceded by a valid score when recorded

Source: LeetCode link: leetcode-cn.com/problems/ba… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

  • When encountering numbers: push;
  • When a plus sign is encountered: Take the top value of the stack, push the stack off the stack, take the top value of the stack and add top, put top back on the stack, and add the added value to the stack.
  • When D: is encountered, multiply the top value of the stack by 2 and place the resulting value on the stack;
  • When C: is encountered, the top value is pushed off the stack.

Finally, when the stack is not empty, the stack is traversed, the top value of the stack is removed and added, and the added value is returned.

Code implementation

// Implement a stack
class Stack {
    constructor() {
        this.stack = []
    }
    push(x) {
        this.stack.push(x);
    }
    pop() {
        if(this.empty()) return; 
        let top = this.top();
        this.stack.pop()
        return top;
    }
    top() {
        return this.stack[this.size()-1]}empty() {
        return this.stack.length == 0;
    }
    size() {
        return this.stack.length; }}/ * * *@param {string[]} ops
 * @return {number}* /
var calPoints = function(ops) {
    let stack = new Stack();
    let sumScore = 0;
    for(let i = 0; i < ops.length; i++) {
        if(ops[i] == '+') {
            let sum = 0;
            let top1 = 0;
            if(! stack.empty()) { top1 = stack.pop(); sum += top1;console.log(stack)
            }
            if(! stack.empty()) { sum += stack.top();; } stack.push(top1); stack.push(sum); }else if(ops[i] == 'D') {
            let score = 0;
            if(! stack.empty()) { score = stack.top(); } stack.push(score *2);

        } else if(ops[i] == 'C') {
            if(!stack.empty()) {
                stack.pop();
            }
        } else {
            stack.push(ops[i] * 1)}}while(! stack.empty()) { sumScore += stack.pop(); }return sumScore;
};
Copy the code