每日的知识积累，包括 五个 Leetcode 算法题，十个前端八股文题，四个英语表达积累。从今天开始倒计时 100 天，到时候换个工作。

1. 五道算法题第一题： 71. 简化路径 /problems/si…

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下：
一个点 '.' 表示当前目录本身。
此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式：
始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
 
示例 1：
输入：path = "/home/"
输出："/home"
解释：
应删除尾随斜杠。
示例 2：
输入：path = "/home//foo/"
输出："/home/foo"
解释：
多个连续的斜杠被单个斜杠替换。
示例 3：
输入：path = "/home/user/Documents/../Pictures"
输出："/home/user/Pictures"
解释：
两个点 ".." 表示上一级目录（父目录）。
示例 4：
输入：path = "/../"
输出："/"
解释：
不可能从根目录上升一级目录。
示例 5：
输入：path = "/.../a/../b/c/../d/./"
输出："/.../b/d"
解释：
"..." 在这个问题中是一个合法的目录名。
 
提示：
1 <= path.length <= 3000
path 由英文字母，数字，'.'，'/' 或 '_' 组成。
path 是一个有效的 Unix 风格绝对路径。

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
  if(path.endsWith('/')) path=path.slice(0,-1);
  const arr = path.split('/').filter(v=>(v!=='' && v!=='/'));
  const rst = [];
  for(let i = 0; i < arr.length; i++){
    const cur = arr[i];
    switch(cur) {
      case '.':
      break;
      case '..':
        rst.pop();
      break;
      default:
        rst.push(cur);
      break;
    }
  }
  return "/"+rst.join("/");
};

得分情况：86.70% 28.30%总结提升使用下面的方式去掉多个分隔符，针对分隔符本身连续出现的情况:

const arr = path.split('/').filter(v=>(v!=='' && v!=='/'));

第二题： 388 文件的最长绝对路径 /problems/lo…

假设有一个同时存储文件和目录的文件系统。下图展示了文件系统的一个示例：
这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。subdir1 包含文件 file1.ext 和子目录 subsubdir1；subdir2 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。
在文本格式中，如下所示(⟶表示制表符)：
dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext
如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。'\n' 和 '\t' 分别是换行符和制表符。
文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。上面例子中，指向 file2.ext 的 绝对路径 是 "dir/subdir2/subsubdir2/file2.ext" 。每个目录名由字母、数字和/或空格组成，每个文件名遵循 name.extension 的格式，其中 name 和 extension由字母、数字和/或空格组成。
给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向 文件 的 最长绝对路径 的长度 。 如果系统中没有文件，返回 0。
 
示例 1：
输入：input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
输出：20
解释：只有一个文件，绝对路径为 "dir/subdir2/file.ext" ，路径长度 20
示例 2：
输入：input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
输出：32
解释：存在两个文件：
"dir/subdir1/file1.ext" ，路径长度 21
"dir/subdir2/subsubdir2/file2.ext" ，路径长度 32
返回 32 ，因为这是最长的路径
示例 3：
输入：input = "a"
输出：0
解释：不存在任何文件
示例 4：
输入：input = "file1.txt\nfile2.txt\nlongfile.txt"
输出：12
解释：根目录下有 3 个文件。
因为根目录中任何东西的绝对路径只是名称本身，所以答案是 "longfile.txt" ，路径长度为 12
 
提示：
1 <= input.length <= 104
input 可能包含小写或大写的英文字母，一个换行符 '\n'，一个制表符 '\t'，一个点 '.'，一个空格 ' '，和数字。

/**
 * @param {string} input
 * @return {number}
 */
var lengthLongestPath = function(input) {
  const arr = input.split('\n');
  let rst = 0;
  function findTheLast(layer, position) {
    // console.log(arr, position)
    while(position) {
      position--;
      const _cur = arr[position];
      if(_cur.layer === layer - 1) {
        if(_cur.value < 0) {
          return -_cur.value;
        }
      }
    }
    return 0;
  }
  function format(str){
    let count = 0;
    while(str.startsWith('\t')) {
      count++;
      str = str.slice(1);
    }
    return {
      count,
      str,
    }
  }
  for(let i = 0; i < arr.length; i++) {
    const cur = arr[i];
    const {count, str} = format(cur);
    if(!cur.includes('.')) {
      arr[i] = {
        layer: count,
        value: -str.length-findTheLast(count, i),
      };
    } else {
      arr[i] = {
        layer: count,
        value: str.length+findTheLast(count, i)+count,
      };
      rst = Math.max(str.length+findTheLast(count, i)+count, rst);
    }
  }
  return rst;
};

得分情况：11.11% 55.56%第三题： 150 逆波兰表达式求值 /problems/ev…

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
 
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
 
提示：
1 <= tokens.length <= 104
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数
 
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
  const stack = [];
  for(let i = 0; i < tokens.length; i++){
    const cur = tokens[i];
    if(cur!=='+' && cur!=='-' && cur!=='*' && cur!=='/') {
      stack.push(parseFloat(cur));
    } else {
      const a = stack.pop();
      const b = stack.pop();
      let rst;
      switch(cur) {
        case '+':
          rst = b + a;
        break;
        case '-':
          rst = b - a;
        break;
        case '*':
          rst = b * a;
        break;
        case '/':
          rst = ~~(b / a);
        break;
      }
      stack.push(rst);
    }
  }
  return stack[0];
};

得分情况：25.51% 62.48% 没做出来，尴尬总结提升~~a 可以完成与 Math.floor(a) 不一样的负数取整策略。第四题： 227 基本计算器 /problems/ba…

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
 
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
 
提示：
1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
  let arr = [];
  let _tmp = "";
  for (let i = 0; i < s.length; i++) {
    const cur = s[i];
    if (cur !== "+" && cur !== "-" && cur !== "*" && cur !== "/") {
      _tmp += cur;
    } else {
      arr.push(_tmp - 0);
      arr.push(cur);
      _tmp = "";
    }
  }
  if (_tmp.length) arr.push(_tmp - 0);
  for (let i = 0; i < arr.length; i++) {
    const cur = arr[i];
    if (cur === "*" || cur === "/") {
      const b = arr[i - 1];
      const a = arr[i + 1];
      let rst;
      switch (cur) {
        case "*":
          rst = b * a;
          break;
        case "/":
          rst = ~~(b / a);
          break;
      }
      arr[i - 1] = null;
      arr[i] = null;
      arr[i + 1] = rst;
    }
  }
  arr = arr.filter((v) => v !== null);
  for (let i = 0; i < arr.length; i++) {
    const cur = arr[i];
    if (cur === "+" || cur === "-") {
      const b = arr[i - 1];
      const a = arr[i + 1];
      let rst;
      switch (cur) {
        case "+":
          rst = b + a;
          break;
        case "-":
          rst = b - a;
          break;
      }
      arr[i - 1] = null;
      arr[i] = null;
      arr[i + 1] = rst;
    }
  }
  return arr[arr.length - 1];
};

我使用了三遍循环，第一遍将字符串整理成能够计算的数组；第二遍处理乘除法，第三遍处理加减法。注意解答中如何处理加减乘除的方法，是技巧。

下面是使用栈来做：

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
  const arr = s
    .replace(/[\+\-\*\/ ]{1}/g, function (v, i, a) {
      if (v === " ") return "";
      return ` ${v} `;
    })
    .split(" ");
  function isOper(s) {
    return /[\+\-\*\/]{1}/.test(s);
  }
  
  const stack = [];
  for (let i = 0; i < arr.length; i++) {
    const cur = arr[i];
    const prev = arr[i - 1];
    if (!isOper(prev)) {
      stack.push(cur);
    } else {
      if (prev === "*") {
        stack.pop(); // 弹出符号位
        const a = stack.pop(); // 弹出数据位
        stack.push(a * cur);
      } else if (prev === "/") {
        stack.pop();
        const a = stack.pop();
        stack.push(~~(a / cur));
      } else {
        stack.push(cur);
      }
    }
  }
  let rst = parseFloat(stack[0]);
  stack.forEach((v, i) => {
    if (stack[i - 1] === "-") {
      rst += -parseFloat(v);
    } else if (stack[i - 1] === "+") {
      rst += parseFloat(v);
    }
  });
  return rst;
};

用一些正则表达式来处理原始数据：

  const arr = s
    .replace(/[\+\-\*\/ ]{1}/g, function (v, i, a) {
      if (v === " ") return "";
      return ` ${v} `;
    })
    .split(" ").filter(Boolean);
  function isOper(s) {
    return /[\+\-\*\/]{1}/.test(s);
  }
  
  const stack = [];

得分情况：51.78% 5.59%224 基本计算器Ⅱ /problems/ba…

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
 
示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
 
提示：
1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位 整数

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
  const arr = `(${s})`
    .replace(/[\+\-\*\/\(\) ]{1}/g, function (v, i, a) {
      if (v === " ") return "";
      return ` ${v} `;
    })
    .split(" ")
    .filter(Boolean);
  function isOper(s) {
    return /[\+\-\*\/]{1}/.test(s);
  }
  const stack = [];
  function calc(arr) {
    if(arr.length === 1) return arr[0]-0;
    const stack = [];
    for (let i = 0; i < arr.length; i++) {
      const cur = arr[i];
      const prev = arr[i - 1];
      if (!isOper(prev)) {
        stack.push(cur);
      } else {
        if (prev === "*") {
          stack.pop(); // 弹出符号位
          const a = stack.pop(); // 弹出数据位
          stack.push(a * cur);
        } else if (prev === "/") {
          stack.pop();
          const a = stack.pop();
          stack.push(~~(a / cur));
        } else {
          stack.push(cur);
        }
      }
    }
    let rst = isOper(stack[0])? 0: parseFloat(stack[0]);
    stack.forEach((v, i) => {
      if (stack[i - 1] === "-") {
        rst += -parseFloat(v);
      } else if (stack[i - 1] === "+") {
        rst += parseFloat(v);
      }
    });
    return rst;
  }
  for (let i = 0; i < arr.length; i++) {
    const cur = arr[i];
    stack.push(cur);
    if (cur === ")") {
      stack.pop();
      const _arr = [];
      while (stack[stack.length - 1] !== "(") {
        let a = stack.pop();
        _arr.unshift(a);
      }
      stack.pop();
      stack.push(calc(_arr));
    }
  }
  return stack[0];
};

得分情况：11.87% 5.00%总结提升

就是多了括号，除了使用出栈入栈的方式之外，更为重要的是需要考虑一些极端情况，例如( -2) (5) 这种。

2. 十道面试题2.1 keep-alive 常见属性及实现原理2.2 next Tick的作用是什么，实现原理是什么

在下次 DOM 更新循环结束之后执行延迟回调。nextTick主要使用了宏任务和微任务。根据执行环境分别尝试采用；就是在 DOM 更新之后清空异步队列。

定义了一个异步方法，多次调用nextTick会将方法存入队列中，通过这个异步方法清空当前队列。

2.3 Vue SSR 的实现原理

SSR也就是服务端渲染，也就是将Vue在客户端把标签渲染成HTML的工作放在服务端完成，然后再把html直接返回给客户端。

SSR有着更好的SEO、并且首屏加载速度更快等优点。不过它也有一些缺点，比如我们的开发条件会受到限制，服务器端渲染只支持beforeCreate和created两个钩子，当我们需要一些外部扩展库时需要特殊处理，服务端渲染应用程序也需要处于Node.js的运行环境。还有就是服务器会有更大的负载需求。

2.4 Vue 组件的 data 为什么必须是函数 -- 因为每次调用的函数对象都是不同的

一个组件被复用多次的话，也就会创建多个实例。本质上，这些实例用的都是同一个构造函数。如果data是对象的话，对象属于引用类型，会影响到所有的实例。所以为了保证组件不同的实例之间data不冲突，data必须是一个函数。

2.5 Computed 的实现原理

当组件实例触发生命周期函数 beforeCreate 后，它会做一系列事情，其中就包括对 computed 的处理。

它会遍历 computed 配置中的所有属性，为每一个属性创建一个 Watcher 对象，并传入一个函数，该函数的本质其实就是 computed 配置中的 getter，这样一来，getter 运行过程中就会收集依赖

但是和渲染函数不同，为计算属性创建的 Watcher 不会立即执行，因为要考虑到该计算属性是否会被渲染函数使用，如果没有使用，就不会得到执行。因此，在创建 Watcher 的时候，它使用了 lazy 配置，lazy 配置可以让 Watcher 不会立即执行。

收到 lazy 的影响，Watcher 内部会保存两个关键属性来实现缓存，一个是 value，一个是 dirty value 属性用于保存 Watcher 运行的结果，受 lazy 的影响，该值在最开始是 undefined

dirty 属性用于指示当前的 value 是否已经过时了，即是否为脏值，受 lazy 的影响，该值在最开始是 true

Watcher 创建好后，vue 会使用代理模式，将计算属性挂载到组件实例中

当读取计算属性时，vue 检查其对应的 Watcher 是否是脏值，如果是，则运行函数，计算依赖，并得到对应的值，保存在 Watcher 的 value 中，然后设置 dirty 为 false，然后返回。

如果 dirty 为 false，则直接返回 watcher 的 value

巧妙的是，在依赖收集时，被依赖的数据不仅会收集到计算属性的 Watcher，还会收集到组件的 Watcher

当计算属性的依赖变化时，会先触发计算属性的 Watcher 执行，此时，它只需设置 dirty 为 true 即可，不做任何处理。

由于依赖同时会收集到组件的 Watcher，因此组件会重新渲染，而重新渲染时又读取到了计算属性，由于计算属性目前已为 dirty，因此会重新运行 getter 进行运算而对于计算属性的 setter，则极其简单，当设置计算属性时，直接运行 setter 即可。

2.6 Compiler 的实现原理

在使用 vue 的时候，我们有两种方式来创建我们的 HTML 页面，第一种情况，也是大多情况下，我们会使用模板 template 的方式，因为这更易读易懂也是官方推荐的方法；第二种情况是使用 render 函数来生成 HTML，它比 template 更接近最终结果。complier 的主要作用是解析模板，生成渲染模板的 render， 而 render 的作用主要是为了生成 VNode

complier 主要分为 3 大块：

2.7 Vue 与其他两个框架的比较

React 和 Vue 有许多相似之处，它们都有：

由于有着众多的相似处，我们会用更多的时间在这一块进行比较。这里我们不只保证技术内容的准确性，同时也兼顾了平衡的考量。我们需要承认 React 比 Vue 更好的地方，比如更丰富的生态系统。

AngularJS (Angular 1)

Vue 的一些语法和 AngularJS 的很相似 (例如 v-if vs ng-if)。因为 AngularJS 是 Vue 早期开发的灵感来源。然而，AngularJS 中存在的许多问题，在 Vue 中已经得到解决。

2.8 watch 和 computed 的比较区别：

都是观察数据变化的（相同）

计算属性将会混入到 vue 的实例中，所以需要监听自定义变量；watch 监听 data 、props 里面数据的变化；

computed 有缓存，它依赖的值变了才会重新计算，watch 没有；

watch 支持异步，computed 不支持；

watch 是一对多（监听某一个值变化，执行对应操作）；computed 是多对一（监听属性依赖于其他属性）

watch 监听函数接收两个参数，第一个是最新值，第二个是输入之前的值；

computed 属性是函数时，都有 get 和 set 方法，默认走 get 方法，get 必须有返回值（return）

watch 的 参数：

computed 缓存原理：conputed本质是一个惰性的观察者；当计算数据存在于 data 或者 props里时会被警告；

vue 初次运行会对 computed 属性做初始化处理（initComputed），初始化的时候会对每一个 computed 属性用 watcher 包装起来 ，这里面会生成一个 dirty 属性值为 true；然后执行 defineComputed 函数来计算，计算之后会将 dirty 值变为 false，这里会根据 dirty 值来判断是否需要重新计算；如果属性依赖的数据发生变化，computed 的 watcher 会把 dirty 变为 true，这样就会重新计算 computed 属性的值。

2.9 系统化的说下 Vue 的修饰符

在 vue 中修饰符可以分为 3 类：

常见的事件修饰符如下：

表单修饰符vue 同样也为表单控件也提供了修饰符，常见的有 .lazy、 .number 和 .trim。

2.10 Vue 优化首屏加载速度

优化首屏加载可以从这几个方面开始：

3. 五句英语积累do you have enough money?how are you paying?how many people are there in Tokyo?how much are these earings?how much does it cost per day?