博客

"hexo": "^7.3.0",
"hexo-deployer-git": "^4.0.0",
"hexo-generator-archive": "^2.0.0",
"hexo-generator-category": "^2.0.0",
"hexo-generator-index": "^4.0.0",
"hexo-generator-searchdb": "^1.4.1",
"hexo-generator-tag": "^2.0.0",
"hexo-renderer-ejs": "^2.0.0",
"hexo-renderer-marked": "^6.3.0",
"hexo-renderer-stylus": "^3.0.1",
"hexo-server": "^3.0.0",
"hexo-theme-landscape": "^1.0.0",
"hexo-theme-next": "^8.20.0"

摄像技术/
 摄影技术.md
 拍照技术.md
 assets/
  摄影技术/
   1.png
   2.png
  拍照技术/
   1.png

 +-----------------------------------------------+
 |                 Length (24)                   |
 +---------------+---------------+---------------+
 |   Type (8)    |   Flags (8)   |
 +-+-------------+---------------+-------------------------------+
 |R|                 Stream Identifier (31)                      |
 +=+=============================================================+
 |                   Frame Payload (0...)                      ...
 +---------------------------------------------------------------+
复制代码

Function.prototype.selfCall = function(context) {
  const ctx = context || window;
  // 去除第一个参数
  const arg = [...arguments].slice(1);
  // const arg = Array.slice.call(arguments, 1);
  // 将函数赋值给ctx.fnc 
  ctx.fnc = this;
  // 执行函数
  const res = ctx.fnc(...arg);
  Reflect.deleteProperty(ctx, "fnc")
  return res
}

Function.prototype.call2 = function (context) {
    var context = context || window;
    context.fn = this;

    var args = [];
    for(var i = 1, len = arguments.length; i < len; i++) {
        args.push('arguments[' + i + ']');
    }

    var result = eval('context.fn(' + args +')');

    delete context.fn
    return result;
}

Function.prototype.selfApply = function (context) {
  const ctx = context || window;
  ctx.fnc = this;
  const arg = [...arguments].slice(1)[0];
  // const arg = Array.slice.call(arguments, 1)[0];
  const res = ctx.fnc(...arg)
  Reflect.deleteProperty(ctx, "fnc")
  return res
}

Function.prototype.apply = function (context, arr) {
    var context = Object(context) || window;
    context.fn = this;

    var result;
    if (!arr) {
        result = context.fn();
    } else {
        var args = [];
        for (var i = 0, len = arr.length; i < len; i++) {
            args.push('arr[' + i + ']');
        }
        result = eval('context.fn(' + args + ')')
    }

    delete context.fn
    return result;
}

Function.prototype.myBind = function (ctx) {
  const args = [...arguments].slice(1)
  const self = this
  return function () {
    return self.apply(ctx, [...args, ...arguments])   
  }
}

function Student(name, age) {
  this.name = name
  this.age = age
}
Student.prototype.say = function () {
  console.log(this.name);
}
var jojo = new Student("jsd", 23);

function createClass(_Class, ...rest) {
  const obj = {}
  const res = _Class.apply(obj, rest)
  obj.__proto__ = _Class.prototype
  return typeof res === "object" ? res : obj
}

function newFactorSimple(ctor) {
  const arg = [...arguments].slice(1);
  // 生成一个__proto__指向ctor.prototype的对象
  var obj = Object.create(ctor.prototype);
  ctor.call(obj, ...arg);
  return obj;
}

// 例子4
function Student(name){
    this.name = name;
    // Null（空） null
    // Undefined（未定义） undefined
    // Number（数字） 1
    // String（字符串）'1'
    // Boolean（布尔） true
    // Symbol（符号）（第六版新增） symbol
    
    // Object（对象） {}
        // Function（函数） function(){}
        // Array（数组） []
        // Date（日期） new Date()
        // RegExp（正则表达式）/a/
        // Error （错误） new Error() 
    // return /a/;
}
var student = new Student('若川');
console.log(student); {name: '若川'}

/**
 * 模拟实现 new 操作符
 * @param  {Function} ctor [构造函数]
 * @return {Object|Function|Regex|Date|Error}      [返回结果]
 */
function newOperator(ctor){
    if(typeof ctor !== 'function'){
      throw 'newOperator function the first param must be a function';
    }
    // ES6 new.target 是指向构造函数
    newOperator.target = ctor;
    var newObj = Object.create(ctor.prototype);
    // ES5 arguments转成数组 当然也可以用ES6 [...arguments], Aarry.from(arguments);
    // 除去ctor构造函数的其余参数
    var argsArr = [].slice.call(arguments, 1);
    // 3.生成的新对象会绑定到函数调用的`this`。
    // 获取到ctor函数返回结果
    var ctorReturnResult = ctor.apply(newObj, argsArr);
    // 小结4 中这些类型中合并起来只有Object和Function两种类型 typeof null 也是'object'所以要不等于null，排除null
    var isObject = typeof ctorReturnResult === 'object' && ctorReturnResult !== null;
    var isFunction = typeof ctorReturnResult === 'function';
    if(isObject || isFunction){
      return ctorReturnResult;
    }
    // 5.如果函数没有返回对象类型`Object`(包含`Functoin`, `Array`, `Date`, `RegExg`, `Error`)，那么`new`表达式中的函数调用会自动返回这个新的对象。
    return newObj;
}

function ObjCreate(proto, properties) {
  // 判断类型，第一个参数传入的必须是 object, function
  if (typeof proto !== "object" && typeof proto !== "function") {
    throw new TypeError("Object prototype may only be an Object: " + proto);
  } 
  // 简单的实现的过程，忽略了properties
  var func = function() {};
  func.prototype = proto; // 将fn的原型指向传入的proto
  return new func();  // 返回创建的新对象，这里思考下，new func() 又做了什么事情呢？且往下看！
};

function MyPromise(executor) {
  var _this = this;
  this._status = "pending";
  this._successCallBack = null;
  this._errorCallBack = null;
  var resolve = function (res) {
    if (_this._status === "pending") {
      _this._status = "fulfilled";
      // 运行then函数传递过来的成功函数
      // 并将结果作为参数回传
      _this._successCallBack(res);
    }
  }
  var reject = function (res) {
    if (_this._status === "pending") {
      _this._status = "rejected";
      // 运行then函数传递过来的错误函数
      // 并将结果作为参数回传
      _this._errorCallBack(res);
    }
  }
  // 把内部函数resolve, reject作为参数，把传进来的函数执行一遍
  setTimeout(() => { // 使用setTimeout 是让resolve晚于then方法赋值
    executor(resolve, reject)
  }, 0)
}
MyPromise.prototype.then = function (sucess, error) {
  this._successCallBack = sucess;
  this._errorCallBack = error;
}

class MyPromise {
  PromiseResult = null; // 终值
  PromiseState = "pending"; // 状态
  toDoFulFilled = null;
  toDoRejected = null;
  // 构造方法
  constructor(executor) {
    const resolve = (value) => {
      setTimeout(() => {
        console.log("resolve");
        if (this.PromiseState !== "pending") return;
        this.PromiseState = "fulfilled";
        this.PromiseResult = value;

        if (this.toDoFulFilled) {
          this.toDoFulFilled(this.PromiseResult);
        }
      }, 0);
    };
    const reject = (reason) => {
      setTimeout(() => {
        if (this.PromiseState !== "pending") return;
        this.PromiseState = "rejected";
        this.PromiseResult = reason;

        if (this.toDoRejected) {
          this.toDoRejected(this.PromiseResult);
        }
      }, 0);
    };
    // 执行传进来的函数
    try {
      executor(resolve, reject);
    } catch (error) {
      reject(error);
    }
  }

  then(onFulfilled, onRejected) {
    return new MyPromise((resolve, reject) => {
      const resolvePromise = (cb) => {
        try {
          // 这个prevRes 就是本次then的返回值
          // cb 就是 onFulfilled  onRejected
          const prevRes = cb(this.PromiseResult);
          // TODO
          if (prevRes instanceof MyPromise) {
            prevRes.then(resolve, reject);
          } else {
            resolve(prevRes);
          }
        } catch (err) {
          reject(err);
          throw new Error(err);
        }
      };

      this.toDoFulFilled = resolvePromise.bind(this, onFulfilled);
      this.toDoRejected = resolvePromise.bind(this, onRejected);
    });
  }
}

/* const test1 = new MyPromise((resolve, reject) => {
  resolve("成功");
}).then(
  (res) => {
    console.log(res);
  },
  (error) => {
    console.log(error);
  }
); */

const test2 = new MyPromise((resolve, reject) => {
  setTimeout(() => {
    resolve("定时器");
  }, 2000);
})
  .then(
    (res) => {
      console.log(res);
      return res + "链式调用";
    },
    (error) => {
      console.log(error);
    }
  )
  .then(
    (res) => {
      console.log(res);
    },
    (error) => {
      console.log(error);
    }
  );

class MaxDuty{
  used = 0
  tasks = []
  constructor(max) {
    this.max = max
  }
  addTask(task) {
    this.tasks.push(task)
  }
  walk() {
    if (this.tasks.length && this.used < this.max) {
      this.used++
      const task = this.tasks.shift()
      task().then(res => {
        console.log(res);
        this.used--
        this.walk()
      })
    }
  }
  start() {
    // 需要塞满
    while (this.used < this.max) {
      this.walk()
    }
  }
}
// 返回一个待启动的promise
function createTask(time, order) {
  return () => {
    return new Promise(resolve => {
      setTimeout(() => {
        resolve(order)
      }, time);
    })
  }
}

const maxDuty = new MaxDuty(2)

maxDuty.addTask(createTask(1000, 1))
maxDuty.addTask(createTask(500, 2))
maxDuty.addTask(createTask(300, 3))
maxDuty.addTask(createTask(400, 4))

maxDuty.start()

var curry = function (fn) {
  // 取到fn之后的参数
  var args = [].slice.call(arguments, 1);
  // 返回一个待使用的新函数
  return function () {
    // 将新函数的参数 和 之前生成珂里化函数的参数合并
    var newArgs = args.concat([].slice.call(arguments));
    // 不改变this，使用所有参数进行调用
    return fn.apply(this, newArgs);
  };
};

function add(a, b) {
  return a + b;
}

var addCurry = curry(add, 1, 2);
addCurry() // 3
//或者
var addCurry = curry(add, 1);
addCurry(2) // 3
//或者
var addCurry = curry(add);
addCurry(1, 2) // 3

var fn = curry(function (a, b, c) {
  console.log([a, b, c]);
});

fn("a", "b", "c"); // ["a", "b", "c"]
fn("a", "b")("c"); // ["a", "b", "c"]
fn("a")("b")("c"); // ["a", "b", "c"]
fn("a")("b", "c"); // ["a", "b", "c"]

// fn(a,b,c) = fn(a)(b)(c)
function curry(fn) {
    return function core(...args) {
        let params = []
        params = params.concat(args)
        let inner = function(...args2) {
            params = params.concat(args2)
            return core.apply(this, params)
        }
        inner.toString = ()=>{
            return fn.apply(null, params)
        }
        return inner
    }
}

function add(...args) {
    return args.reduce((prev,curr)=>prev + curr, 0)
}
let curriedAdd = curry(add)
alert(curriedAdd(1,2,3))

alert(curriedAdd(1, 2)(1, 2, 3))
curriedAdd(1)(2)(3)(4)(5)

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <style>
    html, body {
      height: 100%;
      width: 100%;
    }
  </style>
</head>
<body>
  <script>
    var count = 1
    function handle(event) {
      console.log(this);
    }
    document.onmousemove = debounce(handle, 400)

    function debounce(fn, wait) {
      var timer = null
      return function () {
        clearTimeout(timer)
        timer = setTimeout(
         // 这么写 实际上没有效果
          fn.apply(this, arguments),
          // 下面的写法均有效果
          fn.bind(this, arguments),
     fn,
          wait
        )
      }
    }
  </script>
</body>
</html>

 function debounce(fn, wait) {
      var timer = null
      return function () {
        clearTimeout(timer)
        timer = setTimeout(
          fn.bind(this, ...arguments),
          wait
        )
      }
    }
 // 不使用es6
function debounce(func, wait) {
    var timeout;

    return function () {
        var context = this;
        var args = arguments;

        clearTimeout(timeout)
        timeout = setTimeout(function(){
            func.apply(context, args)
        }, wait);
    }
}

function immedia(fn, wait) {
      var flag = true
      var timer = null
      return function () {
        clearTimeout(timer)
        // 保证不在触发后wait时间后，可以再次被触发
        timer = setTimeout(
          function () {
            flag = true
          },
          wait
        )
        if(flag){
         // 触发后 开启保护
          flag = false
          fn.apply(this, arguments)
        }
      }
    }

function debounce(fn, wait, immediate) {
     var timer = null
     if(immediate){
       var flag = true
       return function () {
         clearTimeout(timer)
         timer = setTimeout(
           function () {
             flag = true
           },
           wait
         )
         if(flag){
           flag = false
           fn.apply(this, arguments)
         }
       }
     }else{
       return function () {
         clearTimeout(timer)
         timer = setTimeout(
           fn.bind(this, ...arguments),
           wait
         )
       }
     }
   }

function throttle(fn, wait) {
  const previous = 0;
  return function () {
    const now = new Date().getTime()
    if (now - previous > wait) {
      previous = now
    }
    fn.apply(this, arguments)
  }
}

function throttle(fn, wait) {
     let flag = true
     return function () {
       if (flag) {
         flag = false
         fn.apply(this, arguments)
         setTimeouto=(function () {
           flag = true
         },wait)
       }
     }
   }

function deepClone(obj) {
  if (obj === 'null') return null
  if (typeof obj !== 'object') return obj
  if (obj instanceof RegExp) return new RegExp(obj)
  if (obj instanceof Date) return new Date(obj)
  let result = new obj.constructor
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
     result[key] = deepClone(obj[key]) 
    }
  }
  // 上面的for循环可以改成
  // Reflect.ownKeys(key => result[key] = deepClone(obj[key])
  return result
}

function deepClone(target) {
  if (typeof target !== "object") {
    return target
  } else {
    const copy = Array.isArray(target) ? [] : {}
    for (const key in target) {
      copy[key] = deepClone(target[key])
    }
    return copy
  }
}

function deepClone(target) {
  const map = new Map();
  return (function _clone(target) {
    if (typeof target !== "object") {
      return target
    } else {
      if (map.has(target)) {
        return target
      }
      map.set(target, null)
      const copy = Array.isArray(target) ? [] : {}
      for (const key in target) {
        copy[key] = _clone(target[key])
      }
      return copy
    }
  })(target)
}

const target = {
  field1: 1,
  field2: undefined,
  field3: {
      child: 'child'
  },
  field4: [2, 4, 8]
};
target.target = target
console.log(deepClone(target));

{
  field1: 1,
  field2: undefined,
  field3: { child: 'child' },
  field4: [ 2, 4, 8 ],
  target: <ref *1> {
    field1: 1,
    field2: undefined,
    field3: { child: 'child' },
    field4: [ 2, 4, 8 ],
    target: [Circular *1]
  }
}

var preorderTraversal = function(root, res = []) {
  if(!root){
    return res
  }
  res.push(root.val)
  preorderTraversal(root.left, res)
  preorderTraversal(root.right, res)
  return res
};

var preorderTraversal = function(root) {
 var res = []
  if(!root){
    return res
  }
  res.push(root.val)
  preorderTraversal(root.left, res)
  preorderTraversal(root.right, res)
  return res
};
function handle(root) {

}

var preorderTraversal = function(root, res = []) {
  if(!root){
    return res
  }
  preorderTraversal(root.left, res)
  res.push(root.val)
  preorderTraversal(root.right, res)
  return res
};

var preorderTraversal = function(root, res = []) {
  if(!root){
    return res
  }
  preorderTraversal(root.left, res)
  preorderTraversal(root.right, res)
  res.push(root.val)
  return res
};

var preorderTraversal = function(root) {
  if(!root){
    return []
  }
  const stack = [];
  const res = []
  stack.push(root)
  while(stack.length){
    const popNode = stack.pop()
    res.push(popNode.val)
    if(popNode.right){
      stack.push(popNode.right)
    }
    if(popNode.left){
      stack.push(popNode.left)
    }
  }
  return res
};

var preorderTraversal = function(root) {
  const res = []
  let cur = root
  const stack = []
  while (stack.length || cur) {
    while (cur) {
      res.push(cur.val)
      stack.push(cur)
      cur = cur.left
    }
    const popNode = stack.pop()
    if(popNode.right){
      cur = popNode.right
    }
  }
  return res
};

var inorderTraversal = (root) => {
  const res = []
  let cur = root
  const stack = []
  while (stack.length || cur) {
    // 找到最左侧的节点，并把沿路的节点全部推入栈中
    while(cur){
      stack.push(cur)
      cur = cur.left
    }
    // 取出栈顶元素
    const popNode = stack.pop()
    // 记录出栈元素
    res.push(popNode.val)
    // 存在右节点 即为父节点 而且左节点已经处理过了
    if(popNode.right){
      cur = popNode.right
    }
  }
  return res
};

const postorderTraversal = function(root) {
  const res = []
  if(!root){
    return res
  }
  const stack = []
  stack.push(root)
  while(stack.length){
    const popRoot = stack.pop()
    res.push(popRoot.val)
    // 左右换一下顺序
    if(popRoot.left){
      stack.push(popRoot.left)
    }
    if(popRoot.right){
      stack.push(popRoot.right)
    }
  }
  // 倒着输出
  return res.reverse()
};

const postorderTraversal = function(root) {
  const res = []
  let cur = root
  const stack = []
  while (stack.length || cur) {
    while (cur) {
      res.push(cur.val)
      stack.push(cur)
      cur = cur.right
    }
    const popNode = stack.pop()
    if(popNode.left){
      cur = popNode.left
    }
  }
  // 把上边的push 换成unshift 这边就不用倒着了 但是时间复杂度更高了，不好
  return res.reverse()
};

const postorderTraversal = function(root) {
  if (!root) {
    return []
  }
  const stack = []
  const res = []
  stack.push({
    node: root,
    flag: 0
  })
  while (stack.length) {
    const {node, flag} = stack.pop()
    if (!node) {
      continue
    }
    if (flag === 1) {
      res.push(node.val)
    } else {
      stack.push({
        node: node,
        flag: 1
      })
      stack.push({
        node: node.right,
        flag: 0
      })
      stack.push({
        node: node.left,
        flag: 0
      })
    }
  }
  return res
};

var preorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right); // 右
        if (node.left) stack.push(node.left); // 左
        stack.push(node); // 中
        stack.push(null);
    };
    return res;
};

var inorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right); // 右
        stack.push(node); // 中
        stack.push(null);
        if (node.left) stack.push(node.left); // 左
    };
    return res;
};

var postorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        stack.push(node); // 中
        stack.push(null);
        if (node.right) stack.push(node.right); // 右
        if (node.left) stack.push(node.left); // 左
    };
    return res;
};

  3
 / \
9  20
  /  \
 15   7

[
  [3],
  [9,20],
  [15,7]
]

var levelOrder = function(root) {
  const levelArr = []
  handle(root,0,levelArr)
  return levelArr
};
function handle(root, level, levelArr){
  if(!root){
    return
  }
  Array.isArray(levelArr[level]) ? levelArr[level].push(root.val) : levelArr[level] = [root.val]
  level++
  handle(root.left, level, levelArr)
  handle(root.right, level, levelArr)
}

var levelOrder = function(root) {
  const res = []
  if(!root){
    return res
  }
  const queue = [root]
  let index = 0
  while (queue.length) { // 关键点
    // 每一层的新开始
    // 记录当前层的节点个数，防止shift多了
    const l = queue.length // 关键点
    res.push([])
    // 把该层推入结果，顺便把该层的下一层推入q中
    for(var i=0;i<l;i++){ // 关键点
      const head = queue.shift()
      res[index].push(head.val)
      if(head.left){
        queue.push(head.left)
      }
      if(head.right){
        queue.push(head.right)
      }
    }
    index++
  }
  return res
};

输入：root = [3,1,4,null,2], k = 1
输出：1

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

var kthSmallest = function(root, k) {
  let res
  function handle(root, count, k){
    if(!root){
      return
    }
    handle(root.left, count, k)
    if(count === k){
      res = root.val
      return
    }
    count++
    handle(root.right, count, k)
  }
  handle(root, 1, k)
  return res
};

var kthSmallest = function(root, k) {
  let count = 1
  function handle(root, k){
    if(!root){
      return
    }
    handle(root.left, k)
    if(count === k){
      res = root.val
      // 如果没有这个count++ 会一直指向下一个节点
      count++
      return
    }
    count++
    handle(root.right, k)
  }
  handle(root, k)
  return res
};

var insertIntoBST = function(root, val) {
  if(!root){
    return new TreeNode(val)
  }
  if(val > root.val){
    if(!root.right){
      root.right = new TreeNode(val)
    }else{
      insertIntoBST(root.right, val)
    }
  }else{
    if(!root.left){
      root.left = new TreeNode(val)
    }else{
      insertIntoBST(root.left, val)
    }
  }
  return root
};

var insertIntoBST = function(root, val) {
  if(!root){
    return new TreeNode(val)
  }
  if(val > root.val){
    root.right = insertIntoBST(root.right, val)
  }else{
    root.left = insertIntoBST(root.left, val)
  }
  // 对return之外情况的兜底 找不到原样返回
  // root.right = root.right
  return root
};

var deleteNode = function(root, key) {
  if(!root){
    return root
  }
  if(root.val === key){
    if(!root.left){
      // 如果root.right 也不存在 就是null
      return root.right
    }
    if(!root.right){
      return root.left
    }
    const minVal = getRightMin(root.right)
    root.val = minVal.val
    root.right = deleteNode(root.right, minVal.val)
  }else if(key < root.val){
    root.left = deleteNode(root.left, key)
  }else{
    root.right = deleteNode(root.right, key)
  }
  return root
};
function getRightMin(root){
  while(root.left){
    root = root.left
  }
  return root
}

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：

输入：n = 1
输出：[[1]]

var generateTrees = function(n) {
  if(n===0){
    return []
  }
  return build(1, n)
};
function build(l, r){
  const res = []
  if(l>r){
    res.push(null)
    return res
  }
  for(var i=l;i<=r;i++){
    const leftTree = build(l, i-1)
    const rightTree = build(i+1, r)
    for(var left of leftTree){
      for(var right of rightTree){
        const root = new TreeNode(i, left, right)
        res.push(root)
      }
    }
  }
  return res
}

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class ListNode {
  constructor(key, val, pre=null, next=null){
    this.key = key;
    this.val = val;
    this.pre = pre;
    this.next = next;
  }
}

var LRUCache = function (capacity) {
  // 最大长度
  this.capacity = capacity
  this.hash = new Map()
  // 计数器
  this.count = 0
  // 虚拟头部
  this.dummyHead = new ListNode(-1, -1)
  // 虚拟尾部
  this.dummyTail = new ListNode(-1, -1)
  this.dummyHead.next = this.dummyTail
  this.dummyTail.pre = this.dummyHead
  // 头部
  this.listHead = this.dummyHead
  // 尾部
  this.listTail = this.dummyTail
};

LRUCache.prototype.get = function(key) {
  if (this.hash.has(key)) {
    const existNode = this.hash.get(key)
    // 从原位置删除
    existNode.next.pre = existNode.pre
    existNode.pre.next = existNode.next
    // 把节点插入虚拟尾部之前
    this.insertBeforeTail(existNode)
    return this.hash.get(key).val
  }else{
    return -1
  }
};

LRUCache.prototype.put = function(key, value) {
  if (this.hash.has(key)) { // 已存在
    const existNode = this.hash.get(key)
    // 从原位置删除
    existNode.next.pre = existNode.pre
    existNode.pre.next = existNode.next
    // 题目有个变更要求
    existNode.val = value
    // 把节点插入虚拟尾部之前
    this.insertBeforeTail(existNode)
  } else { // 未存在
    const newNode = new ListNode(key, value)
    if (this.count < this.capacity) { // 容量没满
      // 把新节点插入虚拟尾部之前
      this.insertBeforeTail(newNode)
      // 用key记录节点
      this.hash.set(key, newNode)
      // 计数
      this.count++
    } else { // 容量满了
      // 删除节点记录
      this.hash.delete(this.listHead.next.key)
      // 把虚拟头部后边节点删除
      this.listHead.next = this.listHead.next.next
      this.listHead.next.pre = this.listHead 
      // 把新节点插入虚拟尾部之前   
      this.insertBeforeTail(newNode)
      // 用key记录节点
      this.hash.set(key, newNode)
    }
  }
};
LRUCache.prototype.insertBeforeTail = function (newNode) {
  // 把节点插入虚拟尾部之前
  this.listTail.pre.next = newNode
  newNode.pre = this.listTail.pre
  newNode.next = this.listTail
  this.listTail.pre = newNode
}

var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map();
};

LRUCache.prototype.get = function(key) {
    if(this.map.has(key)){
        let temp=this.map.get(key)
         this.map.delete(key);
         this.map.set(key, temp);
         return temp
    }else{
        return -1
    }
};

LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)){
        this.map.delete(key);
    }
    this.map.set(key,value);
    if(this.map.size > this.capacity){
     
        this.map.delete(this.map.keys().next().value);
    }
};

示例：

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-delete-getrandom-o1
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

var RandomizedSet = function() {
  this.hash = new Map()
};

RandomizedSet.prototype.insert = function(val) {
  if (this.hash.has(val)) {
    return false
  } else {
    this.hash.set(val, true)
    return true
  }
};

RandomizedSet.prototype.remove = function(val) {
  if (this.hash.has(val)) {
    this.hash.delete(val)
    return true
  } else {
    return false
  }
};

RandomizedSet.prototype.getRandom = function() {
  let count = 1;
  let iterator = this.hash.keys();
  let result = null;
  while (true) {
    const { value, done } = iterator.next()
    if (done) {
      break;
    }
    if (Math.floor(Math.random() * count) === 0) {
      result = value
    }
    count++
  }
  return result
};

var RandomizedSet = function() {
  this.hash = Object.create(null, {})
  this.array = []
};

RandomizedSet.prototype.insert = function(val) {
  if (typeof this.hash[val] !== "undefined") {
    return false
  } else {
    this.array.push(val)
    // 存储位置
    this.hash[val] = this.array.length - 1
    return true
  }
};

RandomizedSet.prototype.remove = function(val) {
  if (typeof this.hash[val] !== "undefined") {
    // 待删除元素的索引
    const index = this.hash[val]
    // 对末尾元素进行操作
    const tailValue = this.array[this.array.length - 1]
    this.hash[tailValue] = index
    this.array[index] = tailValue
    // 删除
    this.array.pop()
    delete this.hash[val]
    return true
  } else {
    return false
  }
};

RandomizedSet.prototype.getRandom = function() {
  return this.array[Math.floor(Math.random()*this.array.length)]
};

var MyQueue = function() {
  this.inStack = []
  this.outStack = []
};

MyQueue.prototype.push = function(x) {
  this.inStack.push(x)
};

MyQueue.prototype.pop = function() {
  if(!this.outStack.length){
    while(this.inStack.length){
      this.outStack.push(
        this.inStack.pop()
      )
    }
  }
  return this.outStack.pop()
};

MyQueue.prototype.peek = function() {
  if(!this.outStack.length){
    while(this.inStack.length){
      this.outStack.push(
        this.inStack.pop()
      )
    }
  }
  return this.outStack[this.outStack.length-1]
};

MyQueue.prototype.empty = function() {
  return !this.inStack.length && !this.outStack.length
};

var MyStack = function() {
  this.list = []
  this.tempList = []
};

MyStack.prototype.push = function(x) {
  if(this.list.length){
    while(this.list.length){
      this.tempList.push(this.list.shift())
    }
    this.list.push(x)
    while(this.tempList.length){
      this.list.push(this.tempList.shift())
    }
  }else{
    this.list.push(x)
  }
};

MyStack.prototype.pop = function() {
  return this.list.shift()
};

MyStack.prototype.top = function() {
  return this.list[0]
};

MyStack.prototype.empty = function() {
  return !this.list.length
};

var reverseList = function(head) {
    if(!head){ // 这个判断多余了
        return head
    }
    let prev = null // 这个利用了哨兵，简化了判断
    while(head){ // 判断条件很重要
        const next = head.next
        head.next = prev
        if(!next){
            return head
        }
        prev = head
        head = next
    }
    return head // return pre 就不用判断next了
};

var reverseList = function (head) {
    var pre = null, cur = head, next;
    while (cur) { // 用cur取代head 迭代过程更加清晰
      next = cur.next;
      cur.next = pre;
      
      pre = cur;
      cur = next;
    }
    return pre;
  }; 

var reverseList = function(head) {
    if(!head){ // 这个其实和下边的条件重复了
        return head
    }
    return df(null, head)
    function df(prev, cur){
        if(!cur){
            return prev
        }else{
            const next = cur.next
            cur.next = prev
            return df(cur, next)
        }
    }
};

var reverseList = function (head) {
  function df(pre, cur) {
    if (cur === null) {
      return pre;
    } else {
      var temp = cur.next;
      cur.next = pre;
      return df(cur, temp);
    }
  }
  return df(null, head);
};

var reverseList = function (head) {
 function df(head) {
    if (!head || head.next === null) {
      return head;
    }
    const last = df(head.next)
    head.next.next = head
    head.next = null
    return last
  }
  return df(head);
};

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}