两周总结

• JS 基于对象
• 执行上下文
• 栈
• • 字符串解码算法
• 尾调用
• 递归
• • 尾递归
  • 二叉树中序遍历

JS 基于对象

JS是基于对象设计和开发出来的语言。

**注意：**基于对象和面向对象是有区别的！

面向对象：

• 三大特点：封装，继承，多态
• 支持两种继承方式：接口继承，实现继承

基于对象：

• 基于对象是使用对象，所以无法用现有对象模板创造新的对象类型。
• ECMAscript是JS的核心，它无法去实现接口继承，所以JS只支持实现继承，而不能实现接口继承，实现继承主要依靠原型链去实现。

proto 与 prototype：

1. 所有的引用类型（数组，函数，对象）可以自由的扩展属性（null除外）
2. 所有的引用类型都有一个 _proto_属性（隐形原型，实质上也是一个普通的对象）
3. 所有的函数都有一个 prototype属性（显式原型，实质也是一个普通的对象）
4. 所有的引用类型，他的 _proto_属性指向它的构造函数的 prototype属性
5. 当视图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的 _proto_属性中去寻找（去它的构造函数的 prototype属性)中去寻找。当调用这个对象本身并不存在的属性或者是方法时，它会一层层地往上找，一直找到null为止，null表示空的对象{}

执行上下文

通俗来说就是JS运行环境，有三种执行上下文：

1. 全局上下文

2. 函数上下文

3. Eval

栈

是一种受限制的线性表，遵循后进先出的规则（LIFO）。

只能从栈顶压入数据（压栈/入栈），也只能从栈顶弹出数据（出栈）。

字符串解码算法

用栈去解：

var decodeString = function(s) {
    // 声明一个栈
    let stack = []
    // 结果字符串
    let result = ''
    let num 
    // 遍历加密字符串
    for (let i = 0;i < s.length; i++) {
        // 没遇到']'就压栈，反之就出栈计算出重复了几次[]包住的内容并重新压栈
        if (!Number.isNaN(s[i])) {
            num = s[i] + num
        } else if (s[i] !== ']') {
            stack.push(s[i])
        } else {
            // 重复次数
            let num = ''
            // 重复后的字符串
            let resultStr = ''
            // 需要重复的字符串
            let str = ''
            while (stack[stack.length -1] !== '[') {
                const val = stack.pop()
                str = val + str
            }
            // 去掉处理掉的[
            stack.pop()
            // 获取重复次数
            while (reg.test(stack[stack.length -1])) {
                num = stack.pop() + num
            }
            // 重复字符串
            for (let i = 0; i < num; i++) {
                resultStr += str
            }
            stack.push(resultStr)
        }
    }
    // 将栈存储的内容一一弹出即可
    while (stack.length) {
         result = stack.pop() + result
    }
    return result
};

尾调用

一个函数执行时的最后一个步骤是调用另一个函数，这就叫做尾调用。

例如：

function fun1() {
    return fun2() // 最后一句代码中调用另一个函数
}

尾调用优化原理：

​ 由于尾调用是函数的最后一步操作，所以不需要保留外层函数的调用记录，我们只要在外层函数最后一句代码中调用内层函数就可以直接用内层函数的调用记录取代外层函数的调用记录，调用栈中始终只保持了一条调用帧，从而节省下部分不必要的内存开销。

递归

递归会产生很多调用帧，每次调用自身函数时均会创建一个新的调用帧压入执行栈中，所以可能会导致栈溢出，而且耗时较长。我们可以通过将之改为尾递归来进行优化。

尾递归

一个函数尾调用自身，就叫做尾递归。

例如：

// 递归算阶乘
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)

// 尾递归算阶乘
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)

二叉树中序遍历

用递归解：

const preorderTraversal = (root) => {
    // 1. 设置结果集
  const result = [];

  // 2. 递归遍历
  const recursion = (root) => {
    // 2.1 判断终止条件
    if (!root) {
      return;
    }

    // 2.2 前序遍历：根、左、右
    result.push(root.val);
    recursion(root.left);
    recursion(root.right);
  };
  recursion(root);

  // 3. 返回结果
  return result;
};