四月八日

class CreateNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    // 内部使用头节点便于控制
    this._head = { next: null };
    // 对外头节点
    this.count = 0;
  }
  push(node) {
    let cur = this._head;
    // 找到链表中的最后一个
    while (cur.next !== null) {
      cur = cur.next;
    }
    this.count += 1;
    cur.next = node;
  }
  // 把指定位置元素移除
  removeAt(index) {
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    let res = null;
    let count = 0;
    // 拿到目标节点的前一个节点
    while (index !== count) {
      cur = cur.next;
      count++;
    }
    // 保存目标节点
    res = cur.next;
    // 拼接后面的节点
    cur.next = cur.next.next;
    this.count -= 1;

    return res;
  }
  // 查找指定位置元素
  getItem(index) {
    let count = 0;
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    while (count !== index) {
      cur = cur.next;
      count++;
    }
    return cur.next;
  }
  // 在任意位置插入元素
  insert(index, node) {
    // 边界处理,因为可以在最有一个节点之后插入,所以不需要判断index和长度项等的情况
    if (index < 0 || index > this.count) return;
    //插入元素是在指定位置元素的前面插入
    let cur = this._head;
    let count = 0;
    // 找到插入位置的节点,把新节点链接到当前节点
    while (index !== count) {
      cur = cur.next;
      count += 1;
    }
    // 保存下一个节点
    const next = cur.next;
    cur.next = node;
    node.next = next;
    this.count += 1;

  }
  // 返回一个元素的位置
  indexOf(node) {
    let count = 0;
    let cur = this.head;
    while (cur !== null) {
      if (node === cur) return count;
      cur = cur.next;
      count += 1;
    }
    return -1;
  }
  // 移除某个元素
  remove(node) {
    const index = this.insert(node);
    return this.removeAt(index);
  }
  // 获取头节点
  getHead() {
    return this._head.next;
  }
}

const list = new LinkedList();
list.push(new CreateNode(1))
list.push(new CreateNode(2))
list.push(new CreateNode(3))
list.insert(3, new CreateNode(4))
console.log(list.getHead())

class CreateNode {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  constructor() {
    // 添加头节点信息
    this._head = {
      next: null,
      prev: null
    };
    this.count = 0;
  }
  push(node) {
    let cur = this._head;
    // 找到链表中的最后一个
    while (cur.next !== null) {
      cur = cur.next;
    }
    // 没有初始化头节点的时候不需要指明prev
    if (this._head.next !== null) {
      node.prev = cur;
    }
    cur.next = node;
    this.count += 1;
    return this.count;
  }
  // 把指定位置元素移除
  removeAt(index) {
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    let res = null;
    let count = 0;
    // 拿到目标节点的前一个节点
    while (index !== count) {
      cur = cur.next;
      count++;
    }
    // 保存需要返回的目标节点
    res = cur.next;
    // 移除之后要修复后一个节点的prev指针
    // 需要把修复prev的操作放在前面,因为下一步保存的时候仍然保留了,后一个节点的错误引用
    cur.next.next.prev = cur
    // 拼接后面的节点
    cur.next = cur.next.next;
    this.count -= 1;

    return res;
  }
  // 查找指定位置元素
  getItem(index) {
    let count = 0;
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    while (count !== index) {
      cur = cur.next;
      count++;
    }
    return cur.next;
  }
  // 在任意位置插入元素
  insert(index, node) {
    // 边界处理,因为可以在最有一个节点之后插入,所以不需要判断index和长度项等的情况
    if (index < 0 || index > this.count) return;
    //插入元素是在指定位置元素的前面插入
    let cur = this._head;
    let count = 0;
    // 找到插入位置的节点,把新节点链接到当前节点
    while (index !== count) {
      cur = cur.next;
      count += 1;
    }
    // 对节点的引用应该是先修复指针,在赋值
    // 保存下一个节点
    const next = cur.next;
    // 下一个节点的prev;
    next.prev = node;
    // 新节点的next
    node.next = next;
    // 新节点的prev
    node.prev = cur;
    // 前一个节点的next
    cur.next = node;
    this.count += 1;
  }
  // 返回一个元素的位置
  indexOf(node) {
    let count = 0;
    let cur = this.head;
    while (cur !== null) {
      if (node === cur) return count;
      cur = cur.next;
      count += 1;
    }
    return -1;
  }
  // 移除某个元素
  remove(node) {
    const index = this.insert(node);
    return this.removeAt(index);
  }
  // 获取头节点
  getHead() {
    return this._head.next;
  }
}

class CreateNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class CircularLinkedList {
  constructor() {
    this._head = {
      next: null,
    };
    this.count = 0;
  }
  push(node) {
    let cur = null;
    // 没有初始化头节点则
    if (this.getHead() == null) {
      cur = this._head;
      // 最有一个节点指向自己
      node.next = node;
    } else {
      // 如果已经有了头节点,保存头节点用于修复指针
      const head = this.getHead();
      cur = head;
      while (cur.next !== head) {
        cur = cur.next;
      }
      node.next = head;
    }
    cur.next = node;
    this.count += 1;
    return this.count;
  }
  // 把指定位置元素移除
  removeAt(index) {
    if (index < 0 || index >= this.count) return undefined;
    // 保存下真实的头节点
    const head = this.getHead()
    let cur = this._head;
    let res = null;
    let count = 0;
    // 拿到目标节点的前一个节点
    while (index !== count) {
      cur = cur.next;
      count++;
    }

    // 保存需要返回的目标节点
    res = cur.next;
    // 如果是头节点
    if (index === 0) {
      // 拿到最后一个节点,修复next指针
      const tail = this.getItem(this.count - 1);
      tail.next = cur.next.next;
      cur.next = cur.next.next;
    }
    // 如果被移除的节点是最后一个节点
    else if (index === this.count - 1) {
      cur.next = head;
    } else {
      cur.next = cur.next.next;
    }
    this.count -= 1;

    return res;
  }
  // 查找指定位置元素
  getItem(index) {
    let count = 0;
    if (index < 0 || index >= this.count) return undefined;
    let cur = this._head;
    while (count !== index) {
      cur = cur.next;
      count++;
    }
    return cur.next;
  }
  // 在任意位置插入元素
  insert(index, node) {
    // 边界处理,因为可以在最有一个节点之后插入,所以不需要判断index和长度项等的情况
    if (index < 0 || index > this.count) return;
    //插入元素是在指定位置元素的前面插入
    const head = this.getHead();
    let cur = this._head;
    let count = 0;
    // 找到插入位置的节点,把新节点链接到当前节点
    while (index !== count) {
      cur = cur.next;
      count += 1;
    }
    // 末尾插入要修复next
    if (index === this.count - 1) {
      node.next = head;
    }
    // 头部插入
    if (index === 0) {
      const tail = this.getItem(this.count - 1);
      tail.next = node;
    }
    const next = cur.next;
    cur.next = node;
    node.next = next;
    this.count += 1;
  }
  // 返回一个元素的位置
  indexOf(node) {
    let count = 0;
    let cur = this.head;
    while (count < this.count) {
      if (node === cur) return count;
      cur = cur.next;
      count += 1;
    }
    return -1;
  }
  // 移除某个元素
  remove(node) {
    const index = this.insert(node);
    return this.removeAt(index);
  }
  // 获取头节点
  getHead() {
    return this._head.next;
  }
}

if (module.hot) {
  module.hot.accept('./print.js', function() {
    console.log('Accepting the updated printMe module!');
    printMe();
  })
}

{
  module: {
    rules: [
      {
        //...
        // 指定优先级，都会先被这个loader处理
        enforce:'pre'
      }，
      {
        oneOf:[
          // 其他的loader
        ]
      }
    ]
  }
}

{
  test: /\.js$/i,
  use: [{
    loader: 'babel-loader',
    options:{
      cacheDirectory:true
    }
  }],
},

// 将node-modules 中代码单独打包成
// 分析多入口文件中有没有公共的依赖，会把依赖单独打包
optimization: {
  splitChunks: {
    chunks: 'all'
  }
},

yarn add -D workbox-webpack-plugin

{
  plugins:[
    //...
    new GenerateSW({
      // 帮助serviceWork快速启动，
      // 删除旧的serverwork
      clientsClaim:true,
      skipWaiting:true
    })
  ]
}

if ('serviceWorker' in navigator) {
  window.addEventListener('load', () => {
    navigator.serviceWorker.register('./service-worker.js')
      .then(() => {
        console.log('注册成功');
      })
      .catch(() => {
        console.log('注册失败');
      });
  });
}

module.exports = {
  //...
  externals: {
    jquery: 'jQuery'
  }
};

const path = require('path');
const webpack = require('webpack');

module.exports = {
  entry:{
    lodash:['lodash'],
    jquery:['jquery'],
    moment:["moment"]
  },
  output:{
    // 生成文件的名称
    filename:'[name]_[contenthash:8].js',
    path:path.resolve(__dirname,'dll'),
    // 单独打包的库对外暴露的名称
    library: "[name]_[fullhash]"
  },
  plugins:[
    new webpack.DllPlugin({
      context: __dirname,
      // 映射单独打包的库的名称
      name: '[name]_[fullhash]',
      // 生成的manifest文件
      path:path.resolve(__dirname,'dll/[name]_manifest.json')
    })
  ],
  mode:'production'
}

module.export = {
  plugins:[
    new webpack.DllReferencePlugin({
      // 存在于manifest文件中的包，不会被打包
			manifest: require(path.resolve(__dirname,'dll/moment_manifest.json'))
    }),
    new webpack.DllReferencePlugin({
			manifest: require(path.resolve(__dirname,'dll/lodash_manifest.json'))
    }),
    new webpack.DllReferencePlugin({
			manifest: require(path.resolve(__dirname,'dll/jquery_manifest.json'))
		}),
    new AddAssetHtmlPlugin({
      filepath: path.resolve(__dirname, './dll/*.js'),
    })
  ]
}

{
  optimization: {
    minimize: true,
    // https://webpack.docschina.org/plugins/terser-webpack-plugin/
    minimizer: [new TerserPlugin({
      cache:true,// 开启缓存
      parallel:true,//多进程打包
      sourceMap:true //启用source-map
    })],
   splitChunks: {
      // async表示只从异步加载得模块（动态加载import()）里面进行拆分
      // initial表示只从入口模块进行拆分
      // all表示以上两者都包括
      chunks: 'async', //all 
      minSize: 1024 * 30 , //分割chunk的最小大小，大于30kb才会被提取
      minRemainingSize: 0,
      maxSize: 0,// 没有最大限制
      minChunks: 1, // 至少被引用一次
      // 按需加载的时候并行加载文件的最大个数
      // 可以理解为针对一个模块拆分后的个数，包括模块本身
      // import()文件本身算一个请求
      // 并不算js以外的公共资源请求比如css
      // 如果同时有两个模块满足cacheGroup的规则要进行拆分，但是maxInitialRequests的值只能允许再拆分一个模块，那尺寸更大的模块会被拆分出来
      // 一个按需加载的包最终被拆分成 n 个包，maxAsyncRequests 就是用来限制 n 的最大值。
      maxAsyncRequests: 30, 
      maxInitialRequests: 30, //入口js文件最大请求数量
      enforceSizeThreshold: 50000,
      name: true, // 可以使用命名规则
      cacheGroups: {
        // node_module中的包会被引入到defaultVendors包中
        defaultVendors: {
          test: /[\\/]node_modules[\\/]/,
          priority: -10,
          // 如果当前打包的模块和之前的是同一个就会复用，而不是重复打包
          reuseExistingChunk: true,
        },
        default: {
          minChunks: 2,
          priority: -20,
          reuseExistingChunk: true,
        },
      },
      // 将当前模块中记录的其他模块的hash单独打包成一个文件
      // 因为如果main.js 引用 a.js,main.js中会保存a.js打包时生成的cotenthash
      // 如果a.js发生改变则contenthash发生改变，那么main.js的contenthash也会改变
      // 代码分割的时候一定要加
      runtimeChunk:()=> {
        name:entrypoint=>`runtime-${entrypoint.name}`
      }
    },

  },
}

const flatten = (root) => {
  if (root === null) return root;

  const stack = [];
  const dig = (root) => {
    if (root === null) return;
    const right = root.right;
    root.right = null;
    // 暂存右节点
    if (right !== null) stack.push(right);

    // 将左节点放到有节点上
    // 并先序遍历继续递归向下
    if (root.left !== null) {
      root.right = root.left;
      root.left = null;
      dig(root.right);
    } else {
      // 如果已经没有下面的节点
      // 从队列中取出最后的右子树遍历
      const next = stack.pop();
      if (next == undefined) return;
      root.right = next;
      dig(next);
    }
  };
  dig(root);
  return root;
};

var type = _curry1(function type(val) {
  return val === null
    ? 'Null'
    : val === undefined
      ? 'Undefined'
      : Object.prototype.toString.call(val).slice(8, -1);
});
export default type;

var adjust = _curry3(function adjust(idx, fn, list) {
  if (idx >= list.length || idx < -list.length) {
    return list;
  }
  var start = idx < 0 ? list.length : 0;
  var _idx = start + idx;
  var _list = _concat(list);
  _list[_idx] = fn(list[_idx]);
  return _list;
});

var all = _curry2(_dispatchable(['all'], _xall, function all(fn, list) {
  var idx = 0;
  while (idx < list.length) {
    if (!fn(list[idx])) {
      return false;
    }
    idx += 1;
  }
  return true;
}));
export default all;

var minDepth = function (root) {
  if (root === null) {
    return 0;
  }

  // 记录最小深度（根节点到最近的叶子节点的距离）
  let minDepthValue = Infinity;

  // 记录当前遍历到的节点深度
  let currentDepth = 0;

  const traverse = function (root) {
    if (root === null) {
      return;
    }

    // 前序位置进入节点时增加当前深度
    currentDepth++;

    // 如果当前节点是叶子节点，更新最小深度
    if (root.left === null && root.right === null) {
      minDepthValue = Math.min(minDepthValue, currentDepth);
    }

    traverse(root.left);
    traverse(root.right);

    // 后序位置离开节点时减少当前深度
    currentDepth--;
  };

  // 从根节点开始 DFS 遍历
  traverse(root);
  return minDepthValue;
};