JS object based

JS is a language designed and developed based on objects.

**Note: * * there is a difference between object-based and object-oriented!

object-oriented:

• Three characteristics: encapsulation, inheritance and polymorphism
• There are two methods of interface inheritance: Inheritance and implementation

Object based:

• Object based is the use of objects, so you cannot create new object types with existing object templates.
• ECMAscript is the core of JS. It cannot implement interface inheritance, so JS only supports implementation inheritance, but cannot implement interface inheritance. Implementation inheritance mainly depends on prototype chain.

proto and prototype:

1. All reference types (arrays, functions, objects) can freely extend attributes (except null)
2. All reference types have one_ proto_ Attribute (invisible prototype, which is essentially an ordinary object)
3. All functions have a prototype attribute (explicit prototype, which is also an ordinary object in essence)
4. All reference types, his_ proto_ Property points to the prototype property of its constructor
5. When the view gets the attribute of an object, if the attribute does not exist in the object itself, it will be deleted_ proto_ Property (go to the prototype property of its constructor). When calling a property or method that does not exist in the object itself, it will look up layer by layer until it finds null. Null represents an empty object {}

Execution context

Generally speaking, it is the JS running environment, which has three execution contexts:

1. Global Context

2. Function context

3. Eval

Stack

Is a restricted linear table that follows the last in first out rule (LIFO).

Data can only be pushed in from the top of the stack (push stack / push stack), and data can only be popped out from the top of the stack (out of the stack).

String decoding algorithm

Solve with stack:

var decodeString = function(s) {
    // Declare a stack
    let stack = []
    // Result string
    let result = ''
    let num 
    // Traverse encrypted string
    for (let i = 0;i < s.length; i++) {
        // If you don't encounter ']', press the stack. On the contrary, get out of the stack, calculate the contents wrapped by [] repeated several times, and press the stack again
        if (!Number.isNaN(s[i])) {
            num = s[i] + num
        } else if (s[i] !== ']') {
            stack.push(s[i])
        } else {
            // Number of repetitions
            let num = ''
            // Repeated string
            let resultStr = ''
            // A duplicate string is required
            let str = ''
            while (stack[stack.length -1] !== '[') {
                const val = stack.pop()
                str = val + str
            }
            // Remove the disposed[
            stack.pop()
            // Get repetitions
            while (reg.test(stack[stack.length -1])) {
                num = stack.pop() + num
            }
            // Duplicate string
            for (let i = 0; i < num; i++) {
                resultStr += str
            }
            stack.push(resultStr)
        }
    }
    // Pop up the contents stored in the stack one by one
    while (stack.length) {
         result = stack.pop() + result
    }
    return result
};

Tail call

The last step in the execution of a function is to call another function, which is called tail call.

For example:

function fun1() {
    return fun2() // Another function is called in the last code.
}

Tail call optimization principle:

Since the tail call is the last step of the function, there is no need to retain the calling record of the outer function. As long as we call the inner layer function in the last sentence of the outer function, we can replace the calling record of the outer function directly with the calling record of the inner function.

recursion

Recursion will generate many call frames. Each time you call your own function, a new call frame will be created and pushed into the execution stack, so it may lead to stack overflow and take a long time. We can optimize it by changing it to tail recursion.

Tail recursion

The tail call itself of a function is called tail recursion.

For example:

// Recursive factorial
function jieCheng(n) {
    if (n <= 1 ) {
        return 1
    }
    return n * jieCheng(n - 1)
}
let start = new Date().getTime()
console.log(jieCheng(20))
let end = new Date().getTime()
console.log(end - start)

// Tail recursive factorial
function jieCheng1(n, result) {
    if (n <= 1 ) {
        return result
    }
    return jieCheng1(n - 1, n * result)
}
let start = new Date().getTime()
console.log(jieCheng1(20, 1))
let end = new Date().getTime()
console.log(end - start)

Order traversal in binary tree

Recursive solution:

const preorderTraversal = (root) => {
    // 1. Set result set
  const result = [];

  // 2. Recursive traversal
  const recursion = (root) => {
    // 2.1 judging termination conditions
    if (!root) {
      return;
    }

    // Traversal: left and right 2.2
    result.push(root.val);
    recursion(root.left);
    recursion(root.right);
  };
  recursion(root);

  // 3. Return results
  return result;
};