preface

Yesterday because of illness, no update, should be the majority of fans to urge more requirements, today you want to force buckle brush.

Stack of preexistence this life

What is a stack:

  • Is aLast in, first outData structures can only be added and removed at one end (the top of the stack)
  • pushInto the stack,popOut of the stack
// Array simulation stack
const stack = [];
stack.push(1);
stack.push(2);
const item = stack.pop()
const item1 = stack.pop()
//1, 2 in turn into the stack, and then 2 first out of the stack, the typical first in and then out
Copy the code
  • Array push, pop methods
// Push: add one or more elements to the end of the array, returning the new length
// Can accept any number of arguments
// Return value: returns the modified length of the arraySource code implementation:var arr =[1.2.3.4]
Array.prototype.myPush =function(){
    for(var i =0; i<arguments.length; i++){this[this.length]=arguments[i]
    }
    return this.length
}
myPush(arr)
//pop: removes the last item from the end of the array, reduces the length of the array, and returns the removed item
// Return value: the deleted element from the array (return undefined if the array is empty)Source code implementation:var arr1 =[1.2.3.4]
Array.prototype.myPop=function (){
    var result =null;
    if(this.length===0) {return undefined;
    }
    result = this[this.length-1];
    this.length=this.length-1;
    return result;
}
Copy the code

Application scenarios of stacks

  • Last in, first out scenarios are required
    • Conversion from decimal to binary, validation of string parentheses, function call stack

LeetCode20, bracket match

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

The opening parenthesis must be closed with a closing parenthesis of the same type. The opening brackets must be closed in the correct order.

Example 1: Input: s = "()" Output: trueCopy the code
Example 2: Input: s = "()[]{}" Output: trueCopy the code
Example 3: Input: s = "(]" Output: falseCopy the code

答 案 :

  • For an open parenthesis that is not closed, the lower the open parenthesis, the higher the corresponding open parenthesis
  • Last in, first out, you can use the stack
  • Ideas:
    • Create a new stack
    • The string is scanned, the open bracket is pushed into the stack, the close bracket is pushed out of the stack if it matches the type of the top bracket (the last bracket in the stack), and the type is not matched.
    • It is valid if the stack is empty at the end, otherwise it is not
/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function (s) {
    if (s.length % 2= = =1) {// If it is odd, it must be false
        return false;
    }
    const stack = [];
    for (let i = 0; i < s.length; i += 1) {
        // Iterate over the string and assign it to c
        const c = s[i];
        if (c === '{' || c === '(' || c === '[') {
            // Push the stack as long as there is an open parenthesis
            stack.push(c);
        }
        else {
            // The top bracket (the rightmost open bracket, which is the last bracket to push into the stack)
            const t = stack[stack.length - 1]
            if (
                (t === '[' && c === '] ') ||
                (t === '(' && c === ') ') ||
                (t === '{' && c === '} ')
            ) {
                stack.pop()
            } else {
                return false}}}return stack.length === 0;Return true if the stack is empty
};
// Time and space are both O (n)
Copy the code

conclusion

Brush the question punch the fifth day, choose force button the 20th question, learned the stack and stack implementation and stack API source code implementation, refueling together wow ~

❤️ Thank you all

If you think this content is very helpful to you: like support, let more people can also see this content (collection does not like, is playing rogue – -) follow the public number to NPY front secret, we learn together progress. If you like it, you can also read other articles (thanks to friends for their encouragement and support 🌹🌹🌹)

Start the LeetCode tour

Double pointer to LeetCode

Leet27, remove element

Classic sorting algorithms that front-end engineers must learn