摸鱼日志

• JavaScript作用域和闭包
  Q：解释 JavaScript 中的词法作用域（Lexical Scoping）和闭包（Closure）。闭包是如何工作的，它们在实际开发中有哪些用途？
  A：词法作用域是指一个函数的内部作用域，闭包是函数以及其周围的此法环境，它通常是一个函数，这个函数能访问外部的变量，因此这个变量一直存续在函数存续期间；在实际开发过程中，闭包可以用于将函数和他词法环境绑定，比如计算长方形的面积，当他的宽固定时，就可以写作：

  function calcArea(width){
      return (height)=>{
          return width*height;
      }
  }
  const area = calcArea(10);
  area(20);
  

  另外，闭包也用于节流、防抖等，但要注意错误的使用闭包会造成内存泄漏。
  C：实际应用：数据封装（模拟私有变量）、函数柯里化、事件处理器和回调函数

• 异步编程
  Q：解释 Promise 和 async/await 在 JavaScript 中的作用。如何使用它们处理异步操作？请给出一个使用 async/await 处理 HTTP 请求并捕获错误的示例代码。
  A：由于js是单线程的，所以一些网络请求等需求需要异步实现，最早使用的方式是回调函数，但是当一个回调函数依赖于另一个回调函数的时候，就会造成回调地狱，promise为了解决这一问题出现，promise的构造函数接受resolve和reject两个参数；async/await是promise的语法糖，实现了用同步的写法实现异步请求。
  C：promise是一个代表了异步操作最终完成或失败的对象。

  示例代码：

  async function getData(){
      try{
          const res = await axios.get("xx");
          console.log(res);
      }catch(err){
          console.log(err);
      }
  }
  getData();
  

• CSS布局
  Q：描述 Flexbox 和 Grid 布局的主要区别。你更倾向于在什么情况下使用 Flexbox，什么情况下使用 Grid？
  A：flex是弹性盒子，gird是栅格布局，flex较为灵活。
  C：flexbox是一种布局方法，意味着它能够处理元素在一个方向上的空间分配，flex设计的初衷是为了提供一种有效的方式来布局、对齐和分配在容器中的项目空间，即使大小是未知或动态变化的。 一维布局；
  grid是二维布局。

• 前端性能优化
  Q：列举至少五种你可以用来提高网页性能的方法或技术。请解释为什么这些方法会影响性能，并且你是如何决定哪些方法最适合当前项目的。
  A：1. 使用精灵图，当前端使用较多小尺寸icon的时候，可以考虑把这些合并成一个较大的精灵图，避免多次请求服务器资源；2. 首屏加载优化，可以使用服务端渲染（ssr），加载首屏时直接渲染服务端返回的html，避免因计算样式或加载js脚本影响加载速度； 3. 减少页面的重排和重绘，尽量避免使用table，因为table中一个小的变化会引起整个页面的重排； 4. 使用缓存，当资源未发生改变时，使用本地缓存可以提高用户体验； 5. 开启gzip加速，前端资源通过gzip打包放在服务器上，减少文件体积，加快获取速度。
  C：决定使用什么优化技术：分析网站或应用的性能瓶颈。

• Web安全
  Q：解释跨站脚本攻击（XSS）和跨站请求伪造（CSRF）的区别。你会如何防御这两种攻击？
  A： XSS是通过在url、文本字段中注入script脚本实现的，比如在访问页面网址时携带参数，参数内包含script脚本，页面通过参数解析，执行恶意脚本；或者在评论区内提交一段script脚本，看到的用户都会遭受攻击；
  CSRF是利用用户的授权信息去伪造请求，比如引导用户点击危险网站，恶意脚本会利用用户的身份认证去伪造危险行为。
  为了防范XSS，可以对js代码进行转义、过滤用户输入等；防范CSRF可以防止页面注入iframe、使用csrf token验证等。

---

1. 实现一个 Promise.all

题目：请手写实现一个 Promise.all 函数，该函数接收一个 Promise 对象的数组作为参数，并返回一个新的 Promise 实例。新的 Promise 实例在所有输入 Promise 都成功解决时解决，返回值是一个包含所有输入 Promise 解决值的数组。如果任何一个输入 Promise 被拒绝，新的 Promise 立即拒绝，拒绝的原因是第一个拒绝的 Promise 的原因。

function promiseAll(promises) {
  let result = new Array(promises.length);
  let success = 0;
  return new Promise((resolve, reject) => {
    promises.forEach((promise, index) => {
      promise
        .then((res) => {
          result[index] = res;
          success++;
          if (success === promises.length) {
            resolve(result);
          }
        })
        .catch((e) => {
          reject(e);
        });
    });
  });
}
function promiseAllSettled(promises) {
  let result = new Array(promises.length);
  let count = 0;
  return new Promise((resolve, reject) => {
    promises.forEach((promise, index) => {
      promise
        .then((res) => {
          result[index] = { state: "fulfilled", value: res };
          count++;
          if (count === promises.length) {
            resolve(result);
          }
        })
        .catch((err) => {
          result[index] = { state: "rejected", err };
          count++;
          if (count === promises.length) {
            resolve(result);
          }
        });
    });
  });
}

let p1 = new Promise((resolve, reject) => {
  setTimeout(() => {
    resolve("p1");
  }, 1000);
});
let p2 = new Promise((resolve, reject) => {
  setTimeout(() => {
    resolve("p2");
  }, 2000);
});
let p3 = new Promise((resolve, reject) => {
  setTimeout(() => {
    reject("p3");
  }, 3000);
});
promiseAll([p1, p2, p3])
  .then((res) => {
    console.log(res);
  })
  .catch((err) => {
    console.log(err);
  });
promiseAllSettled([p1, p2, p3])
  .then((res) => {
    console.log(res);
  })
  .catch((err) => {
    console.log(err);
  });

2. 实现一个简单的路由

题目：在不使用任何前端路由库的情况下，如何实现一个简单的前端路由（SPA）功能？请描述你的思路，并给出基本的实现代码。

3. 实现防抖（Debounce）函数

题目：请实现一个防抖（Debounce）函数。防抖函数接收一个函数和等待时间作为参数，并返回一个新的函数。返回的新函数在被连续调用时，只有在等待时间过去后才会执行原函数，如果在等待时间内再次被调用，则重新计时。

function debounce(func, wait) {
  let timeout = null;
  return function () {
    clearTimeout(timeout);
    let arg = arguments;
    let _this = this;
    timeout = setTimeout(() => {
      func.apply(_this, arg);
    }, wait);
  };
}

let add = (a, b) => {
  console.log(a + b);
};
const debounceAdd = debounce(add, 1000);
setTimeout(() => {
  debounceAdd(1, 2);
}, 200);
setTimeout(() => {
  debounceAdd(1, 2);
}, 200);

4. 实现一个简单的模板引擎

题目：实现一个简单的模板引擎，它能够将类似于 "Hello, {{name}}!" 的模板字符串和一个对象如 {name: "World"} 作为输入，并输出 "Hello, World!"。请描述你的实现思路，并给出代码。

5. CSS 垂直居中的方法

题目：请列举至少三种使得一个元素在其父元素中垂直居中的方法，并简要描述每种方法的原理和使用场景。

• 深拷贝

const deepClone = (obj) => {
  if (obj === null || typeof obj !== "object") return obj;
  let result = Array.isArray(obj) ? [] : {};
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      if (obj[key] && typeof obj[key] === "object") {
        result[key] = deepClone(obj[key]);
      } else {
        result[key] = obj[key];
      }
    }
  }
};

• 手写instanceOf

const myInstance = (left, right) => {
  if (left !== "object" || left === null) return false;
  let proto = Object.getPrototypeOf(left);
  while (proto) {
    if (proto === right.prototype) return true;
    proto = Object.getPrototypeOf(proto);
  }
  return false;
};

• 手写new

function myNew(fn, ...args) {
  const obj = {};
  obj.__proto__ = fn.prototype;
  let result = fn.apply(fn, args);
  return result instanceof Object ? result : obj;
}

• 实现简单ajax

function ajax(options) {
  const xhr = new XMLHttpRequest();
  options = options || {};
  options.type = (options.type || "GET").toUpperCase();
  options.dataType = options.dataType || "json";
  const params = options.data;

  if (options.type === "GET") {
    xhr.open("GET", options.url + "?" + params, true);
    xhr.send(null);
  } else if (options.type === "POST") {
    xhr.open("POST", options.url, true);
    xhr.send(params);
  }

  xhr.onreadystatechange = function () {
    if (xhr.readyState === 4) {
      const status = xhr.status;
      if (status >= 200 && status < 300) {
        options.success && options.success(xhr.responseText, xhr.responseXML);
      } else {
        options.fail && options.fail(status);
      }
    }
  };
}

ajax({
  url: "http://localhost:3000/api",
  type: "GET",
  data: {
    name: "zhangsan",
    age: 18,
  },
  dataType: "json",
  success: function (response, xml) {
    console.log(response);
  },
  fail: function (status) {
    console.log(status);
  },
});

• 函数柯里化

const curry = function (fn) {
  return function curried(...args) {
    if (args.length > fn.length) {
      return function () {
        return curried(...args.concat([...arguments]));
      };
    }
    return fn(...args);
  };
};

• 节流和防抖

function debounce(func, wait) {
  let timeout = null;
  return function () {
    let args = arguments;
    let _this = this;
    if (timeout) clearTimeout(timeout);
    timeout = setTimeout(() => {
      func.apply(_this, args);
    }, wait);
  };
}

function throttle(func, wait) {
  let timeout = null;
  return function () {
    let args = arguments;
    let _this = this;
    if (!timeout) {
      timeout = setTimeout(() => {
        func.apply(_this, args);
        timeout = null;
      }, wait);
    }
  };
}

function throttle(func, wait) {
  let oldtime = Date.now();
  return function () {
    let args = arguments;
    let _this = this;
    let newtime = Date.now();
    if (newtime - oldtime >= wait) {
      func.apply(_this, args);
      oldtime = Date.now();
    }
  };
}

• 并查集

function createUnionFind(size) {
  const parent = new Array(size).fill(0).map((_, i) => i);

  function find(x) {
    if (parent[x] === x) {
      return x;
    }
    parent[x] = find(parent[x]);
    return parent[x];
  }

  function union(x, y) {
    let rootX = find(x);
    let rootY = find(y);
    if (rootX !== rootY) {
      parent[rootX] = rootY;
    }
  }

  function connected(x, y) {
    return find(x) === find(y);
  }

  return {
    find,
    union,
    connected,
  };
}

哈希

• 两数之和

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    map.set(nums[i], i);
  }
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i]) && map.get(target - nums[i]) !== i) {
      return [i, map.get(target - nums[i])];
    }
  }
};

• 字母异位词

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  let map = new Map();
  for (let str of strs) {
    if (map.has(str.split("").sort().join(""))) {
      map.get(str.split("").sort().join("")).push(str);
    } else {
      map.set(str.split("").sort().join(""), [str]);
    }
  }
  return Array.from(map.values());
};

• 最长连续序列(使用set和动态规划)

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  let set = new Set(nums);
  let result = 0;
  for (let num of nums) {
    if (!set.has(num - 1)) {
      let current = num;
      let count = 1;
      while (set.has(current + 1)) {
        current++;
        count++;
      }
      result = Math.max(result, count);
    }
  }
  return result;
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  if (nums.length == 0) {
    return 0;
  }
  let dp = [];
  let result = 1;
  dp[0] = 1;
  nums.sort((a, b) => a - b);
  for (let i = 1; i < nums.length; i++) {
    dp[i] = 1;
    if (nums[i] == nums[i - 1]) {
      dp[i] = dp[i - 1];
    }
    if (nums[i] == nums[i - 1] + 1) {
      dp[i] = dp[i - 1] + 1;
    }
    result = Math.max(result, dp[i]);
  }
  return result;
};

双指针

• 移动零

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let a = 0;
  let b = 0;
  while (a < nums.length) {
    if (nums[a] !== 0) {
      nums[b] = nums[a];
      b++;
    }
    a++;
  }
  while (b < nums.length) {
    nums[b] = 0;
    b++;
  }
};

• 盛最多水的容器(从两端往中间移动短板，因为多少水是由短板决定的，移动长板并不能改善)

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let result = 0;
  let left = 0;
  let right = height.length - 1;
  while (left < right) {
    result = Math.max(
      result,
      (right - left) * Math.min(height[left], height[right])
    );
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return result;
};

• 三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  let result = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length - 2; i++) {
    if (i === 0 || nums[i] !== nums[i - 1]) {
      let sum = 0 - nums[i];
      let left = i + 1;
      let right = nums.length - 1;
      while (left < right) {
        if (nums[left] + nums[right] === sum) {
          result.push([nums[i], nums[left], nums[right]]);
          left++;
          right--;
          while (left < right && nums[left] === nums[left - 1]) left++; // 跳过重复元素
          while (left < right && nums[right] === nums[right + 1]) right--; // 跳过重复元素
        } else if (nums[left] + nums[right] < sum) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return result;
};

• 接雨水(双指针，类似于打擂，永远是强者在台上)

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let result = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        result += leftMax - height[left];
      }
      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        result += rightMax - height[right];
      }
      right--;
    }
  }
  return result;
};

滑动窗口

• 无重复字符的最长字串

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let max = 0;
  let start = 0;
  let map = new Map();
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      start = Math.max(start, map.get(s[i]) + 1);
    }
    max = Math.max(max, i - start + 1);
    map.set(s[i], i);
  }
  return max;
};

• 找到字符串中所有的字母异位词

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  if (s.length < p.length) return [];
  let result = [];
  let pMap = new Array(26).fill(0);
  let sMap = new Array(26).fill(0);
  for (let i = 0; i < p.length; i++) {
    sMap[s.charCodeAt(i) - 97]++;
    pMap[p.charCodeAt(i) - 97]++;
  }
  for (let i = 0; i <= s.length - p.length; i++) {
    if (sMap.join("") === pMap.join("")) result.push(i);
    sMap[s.charCodeAt(i) - 97]--;
    sMap[s.charCodeAt(i + p.length) - 97]++;
  }
  return result;
};

子串

• 和为k的子数组(前缀和优化)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  let result = 0;
  let sum = 0;
  let map = new Map();
  map.set(0, 1);
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    result += map.get(sum - k) || 0;
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return result;
};

• 滑动窗口最大值(单调队列-双端队列)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  const q = [];
  const result = [];
  for (let i = 0; i < k; i++) {
    while (q.length && nums[q[q.length - 1]] <= nums[i]) {
      q.pop();
    }
    q.push(i);
  }
  result.push(nums[q[0]]);

  for (let i = k; i < nums.length; i++) {
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }
    q.push(i);
    while (q[0] <= i - k) {
      q.shift();
    }
    result.push(nums[q[0]]);
  }
  return result;
};

普通数组

• 最大子数组和(类似于dp，当和小于0的时候就丢弃)

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = nums[0];
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    if (sum < 0) {
      sum = 0;
    }
    sum += nums[i];
    max = Math.max(max, sum);
  }
  return max;
};

• 合并区间（排序）

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  for (let i = 0; i < intervals.length - 1; i++) {
    if (intervals[i][1] >= intervals[i + 1][0]) {
      intervals[i][1] = Math.max(intervals[i][1], intervals[i + 1][1]);
      intervals.splice(i + 1, 1);
      i--;
    }
  }
  return intervals;
};

• 轮转数组(注意处理k大于数组长度的情况)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  k = k % nums.length;
  nums.unshift(...nums.slice(nums.length - k));
  nums.splice(nums.length - k, k);
};

• 除自身以外数组的乘积(前缀乘积和后缀乘积)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let pre = new Array(nums.length).fill(1);
  let post = new Array(nums.length).fill(1);
  let result = [];
  pre[0] = nums[0];
  for (let i = 1; i < nums.length; i++) {
    pre[i] = pre[i - 1] * nums[i];
  }
  post[nums.length - 1] = nums[nums.length - 1];
  for (let i = nums.length - 2; i >= 0; i--) {
    post[i] = post[i + 1] * nums[i];
  }
  for (let i = 0; i < nums.length; i++) {
    result.push(
      i === 0
        ? post[i + 1]
        : i === nums.length - 1
        ? pre[i - 1]
        : pre[i - 1] * post[i + 1]
    );
  }
  return result;
};

• 空间复杂度为o(1) ，利用输出数组作为后缀乘积

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
  let post = new Array(nums.length).fill(1);
  post[nums.length - 1] = nums[nums.length - 1];
  for (let i = nums.length - 2; i >= 0; i--) {
    post[i] = post[i + 1] * nums[i];
  }
  let pre = 1;
  for (let i = 0; i < nums.length - 1; i++) {
    post[i] = post[i + 1] * pre;
    pre *= nums[i];
  }
  post[nums.length - 1] = pre;
  return post;
};

• 缺失的第一个正数(将现有数组想办法当成hash表)

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 1 || nums[i] > nums.length) {
      nums[i] = Infinity;
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (
      nums[i] < Infinity &&
      nums[i] > -Infinity &&
      nums[Math.abs(nums[i]) - 1] > 0
    ) {
      nums[Math.abs(nums[i]) - 1] = -nums[Math.abs(nums[i]) - 1];
    }
  }
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  return nums.length + 1;
};

矩阵

• 矩阵置零

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var setZeroes = function (matrix) {
  let m = matrix.length;
  let n = matrix[0].length;
  for (let i = 0; i < m; i++) {
    if (matrix[i].includes(0)) {
      for (let j = 0; j < n; j++) {
        if (matrix[i][j] !== 0) {
          matrix[i][j] = "x";
        } else {
          for (let k = 0; k < m; k++) {
            if (matrix[k][j] !== 0) {
              matrix[k][j] = "x";
            }
          }
        }
      }
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === "x") {
        matrix[i][j] = 0;
      }
    }
  }
};

• 旋转图像(先镜像再反转等同于旋转90°)

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {
  let n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n / 2; j++) {
      [matrix[i][j], matrix[i][n - 1 - j]] = [
        matrix[i][n - 1 - j],
        matrix[i][j],
      ];
    }
  }
};

• 搜索二维矩阵(对行进行二分)

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  let m = matrix.length;
  let n = matrix[0].length;
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] <= target && matrix[i][n - 1] >= target) {
      let left = 0;
      let right = n - 1;
      while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (matrix[i][mid] === target) {
          return true;
        } else if (matrix[i][mid] < target) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
    }
  }
  return false;
};

链表

• 相交链表(先记录两个链表的长度)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  let lengthA = 0;
  let lengthB = 0;
  let p1 = headA;
  while (p1) {
    lengthA++;
    p1 = p1.next;
  }
  let p2 = headB;
  while (p2) {
    lengthB++;
    p2 = p2.next;
  }
  if (lengthA > lengthB) {
    [headA, headB] = [headB, headA];
    [lengthA, lengthB] = [lengthB, lengthA];
  }
  let diff = lengthB - lengthA;
  while (diff) {
    headB = headB.next;
    diff--;
  }
  while (headA !== headB) {
    headA = headA.next;
    headB = headB.next;
  }
  return headA;
};

• 反转链表(prev current next 一开始current指向头，三个一起移动)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let prev = null;
  let current = head;
  while (current) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
};

• 回文链表（双指针找到中点，然后把后半部分反转）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  let p1 = head;
  let p2 = head;
  while (p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
  }
  let prev = null;
  let current = p1;
  while (current) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  while (prev) {
    if (prev.val !== head.val) return false;
    prev = prev.next;
    head = head.next;
  }
  return true;
};

• 环形链表(快慢指针)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let p1 = head;
  let p2 = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) return true;
  }
  return false;
};

• 环形链表II(关键是知道当快慢指针相遇时，再有一个指针从头开始走，会和慢指针相遇在pos处)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let p1 = head;
  let p2 = head;
  let pos = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) {
      while (pos !== p1) {
        pos = pos.next;
        p1 = p1.next;
      }
      return pos;
    }
  }
  return null;
};

• 合并两个有序列表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  let p1 = list1;
  let p2 = list2;
  let newList = new ListNode(0);
  let head = newList;
  while (p1 && p2) {
    if (p1.val < p2.val) {
      head.next = p1;
      p1 = p1.next;
    } else {
      head.next = p2;
      p2 = p2.next;
    }
    head = head.next;
  }
  while (p1) {
    head.next = p1;
    p1 = p1.next;
    head = head.next;
  }
  while (p2) {
    head.next = p2;
    p2 = p2.next;
    head = head.next;
  }
  return newList.next;
};

• 两数相加

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let newList = new ListNode(0);
  let head = newList;
  let cnt = 0;
  while (l1 && l2) {
    let sum = l1.val + l2.val + cnt;
    cnt = Math.floor(sum / 10);
    sum = sum % 10;
    head.next = new ListNode(sum);
    head = head.next;
    l1 = l1.next;
    l2 = l2.next;
  }
  while (l1) {
    let sum = l1.val + cnt;
    cnt = Math.floor(sum / 10);
    sum = sum % 10;
    head.next = new ListNode(sum);
    head = head.next;
    l1 = l1.next;
  }
  while (l2) {
    let sum = l2.val + cnt;
    cnt = Math.floor(sum / 10);
    sum = sum % 10;
    head.next = new ListNode(sum);
    head = head.next;
    l2 = l2.next;
  }
  if (cnt) {
    head.next = new ListNode(cnt);
  }
  return newList.next;
};

• 删除链表的倒数第N个节点(双指针，第二个指针先走n步)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let p1 = head;
  let p2 = head;
  while (n > 0) {
    p1 = p1.next;
    n--;
  }
  while (p1 && p1.next) {
    p1 = p1.next;
    p2 = p2.next;
  }
  if (p1) {
    p2.next = p2.next.next;
  } else {
    head = head.next;
  }
  return head;
};

• 两两交换链表中的节点(设置一个前驱节点)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  if (!head || !head.next) return head;
  let newList = new ListNode(0);
  newList.next = head;
  let prev = newList;
  let p1 = head;
  let p2 = head.next;
  while (p1 && p2) {
    prev.next = p2;
    p1.next = p2.next;
    p2.next = p1;
    prev = p1;
    p1 = p1.next;
    p2 = p1 ? p1.next : null;
  }
  return newList.next;
};

• 随机链表的复制（使用递归 题解）

var copyRandomList = function(head, cachedNode = new Map()) {
    if (head === null) {
        return null;
    }
    if (!cachedNode.has(head)) {
        cachedNode.set(head, {val: head.val}), Object.assign(cachedNode.get(head), {next: copyRandomList(head.next, cachedNode), random: copyRandomList(head.random, cachedNode)})
    }
    return cachedNode.get(head);
}

• 排序链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  let p1 = head;
  let arr = [];
  while (p1) {
    arr.push(p1.val);
    p1 = p1.next;
  }
  arr.sort((a, b) => a - b);
  let ans = new ListNode(0);
  let p2 = ans;
  while (arr.length) {
    p2.next = new ListNode(arr.shift());
    p2 = p2.next;
  }
  return ans.next;
};

• LRU缓存（双向链表+哈希表）

function ListNode(key, val) {
  this.key = key;
  this.val = val;
  this.next = null;
  this.prev = null;
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.cache = new Map();
  this.head = new ListNode(null, null);
  this.tail = new ListNode(null, null);
  this.head.next = this.tail;
  this.tail.prev = this.head;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    const node = this.cache.get(key);
    this.moveToFront(node);
    this.cache.set(key, node);
    return node.val;
  } else {
    return -1;
  }
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    const node = this.cache.get(key);
    node.val = value;
    this.moveToFront(node);
    this.cache.set(key, node);
  } else {
    if (this.cache.size === this.capacity) {
      this.cache.delete(this.tail.prev.key);
      this.removeLast();
    }
    const node = new ListNode(key, value);
    this.addToFront(node);
    this.cache.set(key, node);
  }
};

LRUCache.prototype.addToFront = function (node) {
  node.next = this.head.next;
  this.head.next.prev = node;
  this.head.next = node;
  node.prev = this.head;
};
LRUCache.prototype.moveToFront = function (node) {
  this.removeNode(node);
  this.addToFront(node);
};
LRUCache.prototype.removeNode = function (node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
};
LRUCache.prototype.removeLast = function () {
  this.removeNode(this.tail.prev);
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

二叉树

• 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
  let result = [];
  inOrder(root, result);
  return result;
};
const inOrder = function (node, result) {
  if (!node) return;
  inOrder(node.left, result);
  result.push(node.val);
  inOrder(node.right, result);
};

• 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) return 0;
  let left = maxDepth(root.left);
  let right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

• 翻转二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function (root) {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
};

• 对称二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  if (!root) return true;
  return isMirror(root.left, root.right);
};
var isMirror = function (t1, t2) {
  if (!t1 && !t2) return true;
  if (!t1 || !t2) return false;
  return (
    t1.val === t2.val &&
    isMirror(t1.left, t2.right) &&
    isMirror(t1.right, t2.left)
  );
};

• 二叉树的直径（在求深度的过程中维护一个左+右的最大值）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  let ans = 0;
  const maxDepth = (root) => {
    if (!root) return 0;
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);
    ans = Math.max(ans, left + right);
    return Math.max(left, right) + 1;
  };
  maxDepth(root);
  return ans;
};

• 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  if (!root) return [];
  let result = [];
  let queue = [root];
  while (queue.length) {
    let currentQueue = [];
    let currentLevel = queue.length;
    for (let i = 0; i < currentLevel; i++) {
      let current = queue.shift();
      currentQueue.push(current.val);
      if (current.left) queue.push(current.left);
      if (current.right) queue.push(current.right);
    }
    result.push(currentQueue);
  }
  return result;
};

• 将有序数组转换为二叉搜索树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  if (nums.length === 0) return null;
  const mid = Math.floor(nums.length / 2);
  const root = new TreeNode(nums[mid]);
  root.left = sortedArrayToBST(nums.slice(0, mid));
  root.right = sortedArrayToBST(nums.slice(mid + 1));
  return root;
};

• 验证二叉搜索树（注意左边所有数字都要小于根）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  const helper = (node, min, max) => {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return (
      helper(node.left, min, node.val) && helper(node.right, node.val, max)
    );
  };
  return helper(root, -Infinity, Infinity);
};

• 二叉搜索树中第K小的元素

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  let arr = [];
  function inOrder(node) {
    if (!node) return null;
    inOrder(node.left);
    arr.push(node.val);
    inOrder(node.right);
  }
  inOrder(root);
  arr.sort((a, b) => a - b);
  return arr[k - 1];
};

//使用非递归方式进行中序遍历
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function (root, k) {
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    k--;
    if (k === 0) return root.val;
    root = root.right;
  }
};

• 二叉树的右视图(先层次遍历，然后取每一个的最后一位)

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function (root) {
  const arr = levelOrder(root);
  let ans = [];
  arr.map((item) => {
    ans.push(item[item.length - 1]);
  });
  return ans;
};

var levelOrder = function (root) {
  if (!root) return [];
  const res = [];
  const queue = [root];
  let currentLevel = [];
  while (queue.length) {
    let length = queue.length;
    for (let i = 0; i < length; i++) {
      let node = queue.shift();
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(currentLevel);
    currentLevel = [];
  }
  return res;
};

• 二叉树展开为链表（前序的顺序展开为链表，使用递归后序遍历）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function (root) {
  let prev = null;
  let preOrder = (node) => {
    if (!node) return;
    preOrder(node.right);
    preOrder(node.left);
    node.right = prev;
    node.left = null;
    prev = node;
  };
  preOrder(root);
};

• 从前序与中序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  if (preorder.length === 0) return null;
  let mid = inorder.indexOf(preorder[0]);
  let root = new TreeNode(preorder[0]);
  root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
  root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
  return root;
};

• 二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  if (!root || root === p || root === q) {
    return root;
  }
  let left = lowestCommonAncestor(root.left, p, q);
  let right = lowestCommonAncestor(root.right, p, q);
  if (!left) return right;
  if (!right) return left;
  return root;
};

图论

• 岛屿数量（dfs次数）

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let m = grid.length;
  let n = grid[0].length;
  let count = 0;
  let xx = [-1, 0, 1, 0];
  let yy = [0, 1, 0, -1];
  const dfs = (grid, i, j) => {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] !== "1") {
      return;
    }
    grid[i][j] = "2";
    for (let k = 0; k < 4; k++) {
      dfs(grid, i + xx[k], j + yy[k]);
    }
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === "1") {
        count++;
        dfs(grid, i, j);
      }
    }
  }

  return count;
};

• 腐烂的橘子

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
  let queue = [];
  let fresh = 0;
  let time = 0;
  let m = grid.length;
  let n = grid[0].length;
  let move = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
      if (grid[i][j] === 1) fresh++;
    }
  }
  while (queue.length) {
    let size = queue.length;
    for (i = 0; i < size; i++) {
      let [x, y] = queue.shift();
      for (let [dx, dy] of move) {
        let xx = x + dx;
        let yy = y + dy;
        if (xx >= 0 && xx < m && yy >= 0 && yy < n && grid[xx][yy] === 1) {
          grid[xx][yy] = 2;
          fresh--;
          queue.push([xx, yy]);
        }
      }
    }
    time++;
  }
  return fresh ? -1 : Math.max(0, time - 1);
};

• 课程表（bfs，记录入度和每个课程的后续课程）

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  let inDegree = new Array(numCourses).fill(0);
  let map = new Map();
  let count = 0;
  for (let i = 0; i < prerequisites.length; i++) {
    if (map.has(prerequisites[i][1])) {
      map.get(prerequisites[i][1]).push(prerequisites[i][0]);
    } else {
      map.set(prerequisites[i][1], [prerequisites[i][0]]);
    }
    inDegree[prerequisites[i][0]]++;
  }
  let queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }
  while (queue.length) {
    let current = queue.shift();
    count++;
    let children = map.get(current);
    children &&
      children.map((child) => {
        inDegree[child]--;
        if (inDegree[child] === 0) {
          queue.push(child);
        }
      });
  }
  return count === numCourses;
};

回溯

• 全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  let res = [];
  if (!nums.length) return res;
  const dfs = (path) => {
    if (path.length === nums.length) {
      res.push(path);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (!path.includes(nums[i])) {
        dfs(path.concat(nums[i]));
      }
    }
  };
  dfs([]);
  return res;
};

• 子集（重做）

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  let result = [];
  let dfs = (start, path) => {
    result.push(path);
    for (let i = start; i < nums.length; i++) {
      dfs(i + 1, [...path, nums[i]]);
    }
  };
  dfs(0, []);
  return result;
};

• 电话号码的字母组合

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length === 0) return [];
  let map = {
    2: "abc",
    3: "def",
    4: "ghi",
    5: "jkl",
    6: "mno",
    7: "pqrs",
    8: "tuv",
    9: "wxyz",
  };
  let result = [];

  const dfs = (index, str) => {
    if (index === digits.length) {
      result.push(str);
      return;
    }
    for (let i = 0; i < map[digits[index]].length; i++) {
      dfs(index + 1, str + map[digits[index]][i]);
    }
  };
  dfs(0, "");
  return result;
};

• 组合总和（先找数再去重）

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  let set = new Set();
  let result = [];
  const dfs = (path, sum) => {
    if (sum > target) return;
    if (sum === target) {
      path.sort((a, b) => a - b);
      set.add(JSON.stringify(path));
      return;
    }
    for (let i = 0; i < candidates.length; i++) {
      dfs(path.concat(candidates[i]), sum + candidates[i]);
    }
  };
  dfs([], 0);
  result = Array.from(set).map((item) => JSON.parse(item));
  return result;
};

• 括号生成(左右括号数量)

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  if (n <= 0) return [];
  let result = [];
  const dfs = (left, right, str) => {
    if (!left && !right) {
      result.push(str);
      return;
    }
    if (left === right) {
      dfs(left - 1, right, str + "(");
    } else if (left < right) {
      if (left > 0) dfs(left - 1, right, str + "(");
      dfs(left, right - 1, str + ")");
    }
  };
  dfs(n, n, "");
  return result;
};

• 单词搜索

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let m = board.length;
  let n = board[0].length;
  let move = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  let ans = false;
  let visited = Array(m)
    .fill(0)
    .map(() => Array(n).fill(false));

  const dfs = (x, y, word) => {
    if (board[x][y] !== word[0]) return;
    if (word.length === 1) {
      ans = true;
      return;
    }
    visited[x][y] = true;
    for (let i = 0; i < 4; i++) {
      let xx = x + move[i][0];
      let yy = y + move[i][1];
      if (xx >= 0 && yy >= 0 && xx < m && yy < n && !visited[xx][yy]) {
        dfs(xx, yy, word.substring(1));
        visited[xx][yy] = false;
      }
    }
  };
  for (let i = 0; i < m; i++) {
    let index = board[i].indexOf(word[0]);
    while (index !== -1 && !ans) {
      dfs(i, index, word);
      visited[i][index] = false;
      index = board[i].indexOf(word[0], index + 1);
    }
  }
  return ans;
};

二分

• 搜索插入位置

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
};

• 搜索二维矩阵（二维二分，注意 边界）

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) {
    return false;
  }
  if (
    target < matrix[0][0] ||
    target > matrix[matrix.length - 1][matrix[0].length - 1]
  )
    return false;
  let m = matrix.length;
  let n = matrix[0].length;

  const getRow = () => {
    let l = 0;
    let r = m - 1;
    while (l <= r) {
      let mid = Math.floor((l + r) / 2);
      if (matrix[mid][0] <= target && matrix[mid][n - 1] >= target) {
        return mid;
      } else if (matrix[mid][0] > target) {
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  const row = getRow();
  let l = 0;
  let r = n - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (matrix[row][mid] === target) {
      return true;
    } else if (matrix[row][mid] < target) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return matrix[row][l] === target;
};

• 在排序数组中查找元素的第一个和最后一个位置(取巧，找target+0.5和-0.5)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  let target1 = target - 0.5;
  let target2 = target + 0.5;

  const find = (target) => {
    let l = 0,
      r = nums.length - 1;
    while (l <= r) {
      let mid = Math.floor((l + r) / 2);
      if (nums[mid] < target) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return l;
  };
  let left = find(target1);
  let right = find(target2);
  if (nums[left] === target && nums[right - 1] === target) {
    return [left, right - 1];
  } else {
    return [-1, -1];
  }
};

• 搜索旋转排序数组

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let l = 0,
    r = nums.length - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (nums[mid] === target) return mid;
    if (nums[l] <= nums[mid]) {
      if (nums[l] <= target && target < nums[mid]) r = mid - 1;
      else l = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[r]) l = mid + 1;
      else r = mid - 1;
    }
  }
  return -1;
};

• 寻找旋转排序数组中的最小值

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function (nums) {
  let l = 0;
  let r = nums.length - 1;
  while (l <= r) {
    if (l === r) {
      return nums[l];
    }
    let mid = Math.floor((l + r) / 2);
    if (nums[mid] < nums[r]) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return nums[l];
};

栈

• 括号匹配

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  let stack = [];
  let map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(" || s[i] === "{" || s[i] === "[") {
      stack.push(s[i]);
    } else {
      let last = stack.pop();
      if (s[i] !== map[last]) {
        return false;
      }
    }
  }
  return stack.length === 0;
};

• 最小栈

var MinStack = function () {
  this.stack = [];
  this.minStack = [];
};

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  this.stack.push(val);
  if (
    this.minStack.length === 0 ||
    val <= this.minStack[this.minStack.length - 1]
  ) {
    this.minStack.push(val);
  } else {
    this.minStack.push(this.minStack[this.minStack.length - 1]);
  }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.stack.pop();
  this.minStack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  return this.minStack[this.minStack.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

• 字符串编码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  let queue = [];
  let ans = "";
  for (let i = 0; i < s.length; i++) {
    if (s[i] !== "]") {
      queue.push(s[i]);
    } else {
      let current = queue.pop();
      let temp = "";
      let count = 0;
      let times = 0;
      while (current !== "[") {
        temp = current + temp;
        current = queue.pop();
      }
      while (queue.length > 0 && !isNaN(queue[queue.length - 1])) {
        count = count + Math.pow(10, times) * parseInt(queue.pop());
        times++;
      }
      queue.push(temp.repeat(count));
    }
  }
  return queue.join("");
};

• 每日温度

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  let ans = new Array(temperatures.length).fill(0);
  let queue = [];
  for (let i = 0; i < temperatures.length; i++) {
    if (!queue.length) {
      queue.push({ index: i, value: temperatures[i] });
    } else {
      let top = queue[queue.length - 1];
      if (temperatures[i] < top.value) {
        queue.push({ index: i, value: temperatures[i] });
      } else {
        while (
          queue.length &&
          temperatures[i] > queue[queue.length - 1].value
        ) {
          let top = queue.pop();
          ans[top.index] = i - top.index;
        }
        queue.push({ index: i, value: temperatures[i] });
      }
    }
  }
  return ans;
};

贪心

• 买卖股票的最佳时机

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let min = Infinity;
    let max = 0;
    for(let i=0;i<prices.length;i++){
        if(prices[i]<min){
            min = prices[i];
        }
        max = Math.max(max,prices[i]-min);
    }
    return max;
};

• 跳跃游戏（倒序遍历）

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if(nums.length<=1) return true;
    let len = 1;
    for(let i = nums.length-2;i>0;i--){
        if(nums[i]>=len){
            len = 1;
        }else{
            len++;
        }
    }
    if(nums[0]>=len) return true;
    return false;
};

• 跳跃游戏II

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    let ans = 0;
    let maxPos = 0;
    let end = 0;
    for(let i=0;i<nums.length-1;i++){
        maxPos = Math.max(maxPos,i+nums[i]);
        if(end===i){
            end = maxPos; 
            ans++;
        }
    }
    return ans;
};

• 划分字母区间

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
    let start = 0;
    let end = 0;
    let ans = [];
    let last = [];
    for(let i = 0;i<s.length;i++){
        last[s[i]] = i;
    }
    for(let i=0;i<s.length;i++){
        end = Math.max(end,last[s[i]]);
        if(i===end){
            ans.push(end-start+1);
            start = end+1;
        }
    }
    return ans;
};

• 爬楼梯

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  let dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

• 杨辉三角

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  const result = [];
  for (let i = 0; i < numRows; i++) {
    const row = [];
    for (let j = 0; j <= i; j++) {
      if (j === 0 || j === i) {
        row.push(1);
      } else {
        row.push(result[i - 1][j - 1] + result[i - 1][j]);
      }
    }
    result.push(row);
  }
  return result;
};

• 打家劫舍

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  if (nums.length < 2) {
    return nums[0];
  }
  let dp = new Array(nums.length).fill(0);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[nums.length - 1];
};

• 完全平方数

/**
 * @param {number} n
 * @return {number}
 */
var numSquares = function (n) {
  let dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    let min = Infinity;
    for (let j = 1; j * j <= i; j++) {
      min = Math.min(min, dp[i - j * j]);
    }
    dp[i] = min + 1;
  }
  return dp[n];
};

技巧

• 只出现一次的数字

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let ans = nums[0];
  for (let i = 1; i < nums.length; i++) {
    ans ^= nums[i];
  }
  return ans;
};

• 多数元素

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let ans = 0;
    let count = 0;
    for(let i=0;i<nums.length;i++){
        if(count===0){
            ans = nums[i];
        }
        if(ans===nums[i]){
            count++;
        }else{
            count--;
        }
    }
    return ans;
};

每当项目即将验收时，都需要写一份详细的接口文档，太累啦！那么，既然已经有了现成的yaml文件，能不能让程序帮我们写呢？答案是可以！

项目部署完毕后，若要对项目进行修改，须重新对项目进行打包、将打包后的文件上传到服务器、刷新nginx，比较繁琐，gitlab ci/cd可以将流程自动化，我们只需将修改后的代码推到gitlab上便自动部署。

在项目部署之后，难免会遇到虚拟机重启的情况，虚拟机重启后要重启nginx服务，比较麻烦，那么将nginx设置为系统服务并开机启动即可。

• 下载winsw包，地址：https://github.com/winsw/winsw/releases

什么是Webpack

Webpack是一个现代化的打包工具，它能够将前端项目中的各种资源，如JS、CSS、图片等，打包成一个或多个静态文件。Webpack最初是用于打包JavaScript模块，但是他也可以用于处理其他类型的资源。

发布订阅是一种常见的设计模式，也成为观察者模式。它基于事件处理机制，允许多个观察者订阅某个事件，当时间被触发时，所有订阅该事件的观察者都会收到通知。

FC

FC(Formatting Contexts，格式化上下文)，他是W3C规范中的一个概念。简单来说，它是页面中的一块渲染区域，并且拥有自己的一套渲染规则，它决定了子元素如何定位，以及和其他元素的关系和相互作用，他并不会影响区域外的元素。

闭包是一种特殊的对象/特殊的机制。

闭包由两部分组成：执行上下文(A)和在该执行上下文中创建的函数(B)；

当B执行时访问了A中变量对象中的值，就产生了闭包；

另一个解释：闭包是一项技术或者一个特性，函数作用域中的变量在函数执行完之后就会被垃圾回收，一般情况下访问一个函数作用域中的变量是无法访问的，只能通过特殊的技术或者特性来实现，就是在函数作用域中创建内部函数来实现，这样就不会使得函数执行完成变量被回收，这种技术或特性被称为闭包。像是把变量包裹了起来，形象的称为闭包。

什么是BFC

BFC(Block Formatting Context，块级格式化上下文)，一个BFC区域包含创建该上下文元素的所有子元素，但是不包括创建了新的BFC的子元素的内部元素，BFC是是一块独立的渲染区域，可以将BFC看成是元素的一种属性，拥有了这种属性的元素就会使它的子元素与世隔绝，不会影响到外部其他元素。