// 遍历到顶部的高度 offsetTop
function offsetSum(node) {
  var top = 0,
    left = 0;
  while (node) {
    top = top + parseInt(node.offsetTop);
    left = left + parseInt(node.offsetLeft);
    node = node.offsetParent;
  }
  return { top: top, left: left };
}

const loadJS = (url, cb) => {
  let head = window.document.getElementsByTagName('head')[0];
  let js = window.document.createElement('script');
  js.setAttribute('type', 'text/javascript');
  js.setAttribute('async', 'async');
  js.setAttribute('src', url);
  js.onload = cb;
  head.appendChild(js);
  return js;
};

var liList = document.getElementsByTagName('li');
for (let i = 0; i < liList.length; i++) {
  liList[i].onclick = function () {
    console.log(i);
  };
}
// https://blog.csdn.net/weixin_41829196/article/details/106919689

// 闭包+柯里化
function move(start) {
  var pos = start;
  return function () {
    console.log('Move to ' + (pos += 2) + '.');
  };
}

var move_next = move(6);
move_next(); // Move to 8.
move_next(); // Move to 10.

// 手写bind
Function.prototype.bind = function (context) {
  var self = this; //this => Function
  return function () {
    return self.apply(context, arguments);
  };
};

var aa = { b: '1' };
function bb() {
  console.log(this.b);
}
var cc = bb.bind(aa); // 必须重命名为cc
cc();

// 补充bind
// Function.prototype.mybind = function (target) {
//   if (typeof this !== 'function') {
//     return;
//   }
//   var that = this;
//   // that.apply(target, Array.prototype.slice.call(arguments, 1))
//   // var temp = function() {};
//   var F = function () {
//     // 每次都是新的实例，防止多个mybind互相影响
//     // this在没有new的时候  指向window  有new的时候指向实例对象，此时就相当于不绑定target
//     var _this = this instanceof that ? this : target;
//     // 如果是new的时候  将that也就是foo函数绑定到new的实例上
//     that.apply(_this, arguments);
//   };
//   // 因为任何new出来的实例都可以访问原型链。
//   // 如果直接赋值那么new出来的对象可以直接修改bar函数的原型链，这也就是是原型链污染
//   F.prototype = Object.create(that.prototype);
//   // temp.prototype = that.prototype;
//   // F.prototype = new temp();
//   return F;
// };

// function foo(name) {
//   this.name = name;
//   console.log(this.b, 'obj.b'); // 第一次aa   第二次undefined
// }
// var obj = {
//   b: 'aa',
// };
// let newFoo = foo.mybind(obj);
// newFoo('666');
// console.log(obj.name, 'obj.name1'); // 666
// let skipFoo = new newFoo('333');
// console.log(obj.name, 'obj.name2'); // 应为666
// console.log(skipFoo.name, 'skipFoo.name'); // 应为333
// console.log(skipFoo.b, 'skipFoo.b'); // undefined

// Function.prototype.myBind = function (context) {
//   if (typeof this !== 'function') {
//     throw new TypeError('Error');
//   }
//   const _this = this;
//   // arguments是类数组，所以需要扩展符
//   const args = [...arguments].slice(1);
//   // 返回一个函数
//   return function F() {
//     // 因为返回了一个函数，我们可以 new F()，所以需要判断
//     if (this instanceof F) {
//       return new _this(...args, ...arguments);
//     }
//     return _this.apply(context, args.concat(...arguments));
//   };
// };
// 手写apply
Function.prototype.apply = function (content = window, args = []) {
  var fn = Symbol();
  content[fn] = this;
  const result = content[fn](args); // 参数也是一个数组
  return result;
};
// 手写call
Function.prototype.call = function (content = window, ...rest) {
  var fn = Symbol();
  content[fn] = this;
  const result = content[fn](...rest); //参数也都是分开的
  return result;
};
// Function.prototype.myCall = function (context) {
//   // 判断是否是undefined和null
//   if (typeof context === 'undefined' || context === null) {
//     context = window;
//   }
//   context.fn = this;
//   let args = [...arguments].slice(1);
//   let result = context.fn(...args);
//   delete context.fn;
//   return result;
// };

// Function.prototype.myApply = function (context) {
//   if (typeof context === 'undefined' || context === null) {
//     context = window;
//   }
//   context.fn = this;
//   let args = arguments[1];
//   let result;
//   if (args) {
//     result = context.fn(...args); // undefined扩展符...展开会报错
//   } else {
//     result = context.fn();
//   }
//   delete context.fn;
//   return result;
// };

// Function.prototype.myapply = function (ctx, args) {
//   cxt = ctx || window;
//   var fn = Symbol();
//   cxt[fn] = this;
//   var result = cxt[fn](...args);
//   return result;
// };

function _new(fun) {
  return function () {
    let obj = {
      __proto__: fun.prototype,
    };
    fun.apply(obj, arguments);
    return obj;
  };
}

if (!Object.create) {
  Object.create = function (o) {
    function F() {}
    F.prototype = o;
    return new F();
  };
}

// 简单深拷贝
let a = {
  age: undefined,
  sex: Symbol('male'),
  jobs: function () {},
  name: 'yck',
};
let b = JSON.parse(JSON.stringify(a));
console.log(b); // {name: "yck"}  // 序列化后丢失
// 深拷贝
function deepClone(obj) {
  let map = new WeakMap();
  function dp(obj) {
    let newObj = Array.isArray(obj) ? [] : {};
    if (map.has(obj)) {
      return obj;
    } else {
      map.set(obj, '1'); // 任意占位
    }
    for (let i of Reflect.ownKeys(obj)) {
      // 可以获取Symbol的key
      if (typeof obj[i] === 'object' && obj[i] !== null) {
        newObj[i] = dp(obj[i]);
      } else {
        newObj[i] = obj[i];
      }
    }
    return newObj;
  }
  return dp(obj);
}
var obj = {
  [Symbol('hahah')]: '1',
  aa: '2',
  bb: [1, 2, 3],
  cc: null,
  dd: undefined,
  ee: function () {},
  // [function a() {}]: 666, 如果键为函数，则不能为obj 而为weakMap
};
obj.ff = obj; // 循环引用自身
let newObj = deepClone(obj);
console.log(newObj);

// 手写Promise - 废弃
// function EasyPromise(fn) {
//   this.then = (resolveCB, rejectCB) => {
//     this.resolveCB = resolveCB;
//     this.rejectCB = rejectCB;
//     return this;
//   };
//   this.catch = errCB => {
//     this.catchCB = errCB;
//   };
//   this.resolve = data => {
//     setTimeout(() => {
//       this.resolveCB(data);
//     });
//   };
//   this.reject = data => {
//     setTimeout(() => {
//       this.rejectCB(data);
//     });
//   };
//   try {
//     fn(this.resolve, this.reject);
//   } catch (e) {
//     setTimeout(() => {
//       this.catchCB(e);
//     });
//   }
// }
// new EasyPromise((resolve, reject) => {
//   console.log(b); // 直接进入catch
//   resolve("44");
// }).then(res => {console.log(res, "res");}).catch(e => {console.log(e, "错误");});

// 重构Promise
const PENDING = 'pending';
const FULFILLED = 'fulfilled';
const REJECTED = 'rejected';
class Promise {
  constructor(executor) {
    this.state = PENDING;
    this.value = '';
    this.reason = '';
    this.resolveCB = [];
    this.rejectCB = [];

    let resolve = (val) => {
      setTimeout(() => {
        // 这个setTimeout是为了让这个执行变成异步，让外边的宏任务(console)先执行，执行完在执行promise的微任务
        if (this.state == 'PENDING') {
          this.state = FULFILLED;
          this.value = val;
        }
        this.resolveCB.forEach((fn) => fn());
      }, 0);
    };

    let reject = (reason) => {
      setTimeout(() => {
        if (this.state == 'PENDING') {
          this.state = REJECTED;
          this.reason = reason;
        }
        this.rejectCB.forEach((fn) => fn());
      });
    };

    try {
      executor(resolve, reject);
    } catch (err) {
      reject(err);
    }
  }
  then(onFulfilled, onRejected) {
    // if (this.state == FULFILLED) return new Promise((resolve, reject)=>{onFulfilled(this.value)})
    if (this.state == FULFILLED) onFulfilled(this.value);
    if (this.state == REJECTED) onRejected(this.reason);
    if (this.state == PENDING) {
      this.resolveCB.push(() => onFulfilled(this.value)); // 如果继续then的话需要push的就是一个promise的方法，外层需要加setTimeout，避免push进去的是一个空对象
      this.rejectCB.push(() => onRejected(this.reason));
    }
  }
  catch(fn) {
    return this.then(null, fn);
  }
}

function promiseAll(promises) {
  const arrVal = [];
  let count = 0;
  function loop() {
    return new Promise((resolve) => {
      promises.forEach((itemPromise, index) => {
        itemPromise().then(
          (res) => {
            arrVal[index] = res;
            count++;
            if (count == promises.length) {
              return resolve(arrVal);
            }
          },
          (reason) => {
            return reject(reason);
          }
        );
      });
    });
  }
  return loop();
}

// Generator 状态机
function* foo(x) {
  let y = 2 * (yield x + 1);
  console.log('1');
  let z = yield y / 3;
  console.log(x, y, z); // 5 24 13
  return x + y + z;
}
let it = foo(5);
console.log(it.next()); // => {value: 6, done: false}
console.log(it.next(12)); // => {value: 8, done: false} 执行到这里才是刚得到y值 2*12=24
console.log(it.next(13)); // => {value: 42, done: true}

// 手写Generator
function easyGenerator(list) {
  var index = 0;
  // var countIndex = 0   异步的时候可以用来计算一共有多少步
  var len = list.length;
  return {
    // 定义 next 方法
    // 记录每次遍历位置，实现闭包，借助自由变量做迭代过程中的“游标”
    next: function () {
      //  如果是异步 定义一个变量currentIndex 然后 countIndex++  当index == currentIndex的时候往下执行，执行完index++
      var done = index >= len; // 如果索引还没有超出集合长度，done 为 false
      var value = !done ? list[index++] : undefined; // 如果 done 为 false，则可以继续取值
      // 返回遍历是否完毕的状态和当前值
      return {
        // 必须在next里边
        done: done,
        value: value,
      };
    },
  };
}

// Object增加迭代器
var myObject = {
  a: 2,
  b: 3,
};
Object.defineProperty(myObject, Symbol.iterator, {
  enumerable: false,
  writable: false,
  configurable: true,
  value: function () {
    var o = this;
    var idx = 0;
    var ks = Object.keys(o);
    return {
      next: function () {
        return {
          value: o[ks[idx++]],
          done: idx > ks.length,
        };
      },
    };
  },
});
// 手动遍历 myObject
var it = myObject[Symbol.iterator]();
it.next(); // { value:2, done:false }
it.next(); // { value:3, done:false }
it.next(); // { value:undefined, done:true }
// 用 for..of 遍历 myObject
for (var v of myObject) {
  console.log(v);
}
// 2
// 3
// 迭代器+状态机自动遍历
let myObj = {
  name: 'Tadokoro',
  age: 24,
  occupation: 'student',
};

function* myIterator() {
  for (let key of Object.keys(this)) yield this[key];
}
myObj[Symbol.iterator] = myIterator.bind(myObj);

for (let val of myObj) console.log(val);
//Tadokoro
//24
//student

// 组合继承
Parent.prototype.getValue = function () {};
function Child(value) {
  Parent.call(this, value); // 继承实例属性
}
Child.prototype = new Parent(); // 继承原型属性

// 寄生组合继承
Child.prototype = Object.create(Parent.prototype, {
  constructor: {
    value: Child,
    enumerable: false,
    writable: true,
    configurable: true,
  },
});
// ES6 语法
class Child extends Parent {
  constructor(value) {
    super(value);
  }
}

// 简单考试
function Person() {
  this.name = 'zhangpeng';
  this.sayMes = 'hello';
}
Person.prototype.say = function () {
  console.log('打印', this.sayMes);
};
function Man() {
  this.sex = 'man';
  this.sayMes = '哈哈哈'; // 被后边的sayMes覆盖
  Person.apply(this, arguments);
  console.log(this.sayMes);
}
Man.prototype = Object.create(Person.prototype, {
  constructor: {
    value: Man,
  },
});
var man = new Man();
man.say();
console.log(man.constructor); // Man

// ES6继承
class Animal {
  constructor(param) {
    this.mouseNum = '1';
    this.eyesNum = '1';
    console.log('param', param);
  }
  sayEyeNum() {
    console.log('有几只眼睛', this.eyesNum);
  }
  sayMouseNum() {
    console.log('有几张嘴', this.mouseNum);
  }
}
class Cat extends Animal {
  constructor() {
    super('传入到Animal的constructor中'); // 必须写super()
    this.mouseNum = '2';
    this.eyesNum = '2';
  }
  sayEyeNum() {
    console.log('有几只眼睛呀', this.eyesNum);
    super.sayEyeNum(); // 同时执行父类重的sayEyeNum方法
  }
}
var cat = new Cat();
console.log(cat);
cat.sayEyeNum();
cat.sayMouseNum();
// param 传入到Animal的constructor中
// Cat { mouseNum: '2', eyesNum: '2' }
// 有几只眼睛呀 2
// 有几只眼睛 2
// 有几张嘴 2

// 柯里化目的：就是要尽量减少代码中的中间变量/多元参数拆解成多个单一参数函数的方式，柯里化是实现函数代码重用的关键
// 任何函数（方法）都不应该含有过多参数，如果一个函数含有很多参数，那只能说明这个函数的代码很臃肿，有可以抽取出来的公共部分。
// 格式：Fn(a,b,c) => Fn(a)(b)(c)
function curry(fn) {
  return function res(...arg) {
    if (arg.length >= fn.length) {
      // fn.length是函数参数的个数
      return fn(...arg);
    } else {
      return res.bind(null, ...arg);
    }
  };
}
function add(a, b) {
  return a + b;
}
curry(add)(1)(2);
// 更容易理解
// function currying(func) {
//   const args = [];
//   return function result(...rest) {
//     if (rest.length === 0) return func(...args);
//     args.push(...rest);
//     return result;
//   };
// }
// 组合函数目的：实现从左到右的数据流
function compose(...args) {
  return function (x) {
    return args.reduce(function (total, current) {
      return current(total);
    }, x);
  };
}
function a1(a) {
  console.log('a', a);
  return 1;
}
function a2(b) {
  console.log('b', b);
  return 2;
}
function a3(c) {
  console.log('c', c);
  return 3;
}
compose(a1, a2, a3)(0);
// a 0
// b 1
// c 2

// 工厂模式
class Factory {
  constructor(type) {
    if (type == '33') return { a: '33' };
    if (type == '44') return { a: '44' };
  }
}
const aa = new Factory('33');
const bb = new Factory('44');
console.log(aa); // 33
console.log(bb); // 44

// 单例模式
class Single {
  constructor() {}
  static getInstance() {
    if (!this.instance) {
      this.instance = new Single();
    }
    return this.instance;
  }
}
const s1 = Single.getInstance();
s1.aa = '11';
const s2 = Single.getInstance();
console.log(s1.aa); // 11
console.log(s2.aa); // 11

// function Single(){
//     this.instance = null
// }
// Single.getInstance= function(){
//     if(!this.instance){
//         this.instance = new Single()
//     }
//     return this.instance
// }
// var a = Single.getInstance()
// a.aa = '11'
// var b = Single.getInstance()
// b.bb = '22'
// console.log(a.aa)
// console.log(b.aa)

// 适配器模式-同一个组件，要求返回的数据结构一致
class Adapter {
  constructor(obj) {
    return {
      a: obj.a || 'a',
      b: obj.b || 'b',
    };
  }
}
const a1 = new Adapter({ a: '1' });
const a2 = new Adapter({ a: '2' });
console.log(a1); // { a: '1', b: 'b' }
console.log(a2); // { a: '2', b: 'b' }

// 装饰模式-非ES6
// var Plane = function () {};

// Plane.prototype.fire = function () {
//   console.log('发射普通子弹');
// };

// var MissileDecorator = function (plane) {
//   this.plane = plane;
// };
// MissileDecorator.prototype.fire = function () {
//   this.plane.fire(); //包含了一个普通的fire
//   console.log('发射导弹');
// };

// // 装饰模式
// @testable
// class MyTestableClass {
//   // ...
// }
// function testable(target) {
//   target.isTestable = true;
// }
// MyTestableClass.isTestable; // true

// 装饰器
function lock(fn) {
  var lock = false;
  return function () {
    if (lock) return '频繁点击'; // 最好return Promise.reject
    lock = true;
    fn().finally(() => {
      lock = false;
    });
  };
}

// AOP装饰函数
// 前置代码
Function.prototype.before = function (fn) {
  const self = this;
  return function () {
    fn.apply(this, arguments);
    return self.apply(this, arguments);
  };
};
// 后置代码
Function.prototype.after = function (fn) {
  const self = this;
  return function () {
    self.apply(this, arguments);
    return fn.apply(this, arguments);
  };
};

// 发布订阅 - 直接改写vue的Dep就行
class Pub {
  constructor() {
    this.eventList = [];
  }
  on(fn) {
    this.eventList.push(fn);
  }
  emit() {
    this.eventList.forEach((item) => {
      item();
    });
  }
}
const pub = new Pub();
pub.on(() => {
  console.log('1');
});
pub.emit(); // 1

// 观察者模式-利用Proxy

// Ajax-CORS
// Create the XHR object.
function createCORSRequest(method, url) {
  var xhr = new XMLHttpRequest();
  xhr.open(method, url, true);
  xhr.withCredentials = true;
  xhr.setRequestHeader('aaa', '111');
  xhr.timeout = obj.timeout;
  xhr.onload = function (e) {};
  // xhr.onreadystatechange = function (e) { };
  xhr.ontimeout = function (e) {};
  xhr.onerror = function (e) {};
  xhr.upload.onprogress = function (e) {};
  xhr.send();
}

// 新防抖
export const debounce = (fn, delay = 500) => {
  let timer = null;
  return function () {
    clearTimeout(timer);
    timer = setTimeout(() => {
      fn.apply(this, arguments);
    }, delay);
  };
};
// 新节流
export const throttle = (fn, delay = 500) => {
  let valid = true;
  return function () {
    if (!valid) return false;
    valid = false;
    setTimeout(() => {
      fn();
      valid = true;
    }, delay);
  };
};

function observe(obj) {
  // 判断类型
  if (!obj || typeof obj !== 'object') {
    return;
  }
  // 这里还要加一个数组的逻辑
  Object.keys(obj).forEach((key) => {
    defineReactive(obj, key, obj[key]);
  });
}
function defineReactive(obj, key, val) {
  // 递归子属性
  observe(val);
  let dp = new Dep();
  Object.defineProperty(obj, key, {
    enumerable: true,
    configurable: true,
    get: function reactiveGetter() {
      console.log('get value');
      // 将 Watcher 添加到订阅
      if (Dep.target) {
        dp.addSub(Dep.target);
      }
      return val;
    },
    set: function reactiveSetter(newVal) {
      console.log('change value');
      // observe(newVal); 最好再遍历一下新设置的值
      val = newVal;
      // 执行 watcher 的 update 方法
      dp.notify();
    },
  });
}
// 通过 Dep 解耦属性的依赖和更新操作
class Dep {
  constructor() {
    this.subs = [];
  }
  // 添加依赖
  addSub(sub) {
    this.subs.push(sub);
  }
  // 更新
  notify() {
    this.subs.forEach((sub) => {
      sub.update();
    });
  }
}
// 全局属性，通过该属性配置 Watcher
Dep.target = null;

class Watcher {
  constructor(obj, key, cb) {
    // 将 Dep.target 指向自己
    // 然后触发属性的 getter 添加监听
    // 最后将 Dep.target 置空
    Dep.target = this;
    this.cb = cb;
    this.obj = obj;
    this.key = key;
    this.value = obj[key]; // 主要是这里  会触发getter  把this添加到dp中通过dp.addSub(Dep.target)
    Dep.target = null;
  }
  update() {
    // 获得新值
    this.value = this.obj[this.key];
    // 调用 update 方法更新 Dom
    this.cb(this.value);
  }
}

// 运行
var data = { name: 'yck' };
observe(data);
function update(value) {
  document.querySelector('div').innerText = value;
}
// 模拟解析到 `{{name}}` 触发的操作
new Watcher(data, 'name', update);
// update Dom innerText
data.name = 'yyy';

// Proxy 写响应式
function reactive(target = {}) {
  if (typeof target != 'object' || target == null) {
    return target;
  }
  // 代理配置
  const proxyConf = {
    //receiver指的是原始的操作行为所在的那个对象，一般情况下是proxy实例本身
    get(target, key, receiver) {
      const ownKeys = Reflect.ownKeys(target);
      if (ownKeys.includes(key)) {
        // 监听逻辑push
      }
      const result = Reflect.get(target, key, receiver);
      // 深度监听-只有get时候才会触发
      return reactive(result);
    },
    set(target, key, val, receiver) {
      // 重复数据不处理
      if (val === target[key]) return true;

      const ownKeys = Reflect.ownKeys(target);
      if (ownKeys.includes(key)) {
        // 已有key
      } else {
        // 新增key
      }
      const result = Reflect.set(target, key, val, receiver);
      return result; // 是否设置成功
    },
    deleteProperty(target, key) {
      const result = Reflect.deleteProperty(target, key);
      return result; // 是否删除成功
    },
  };
  // 生成代理对象
  const observed = new Proxy(target, proxyConf);
  return observed;
}

// 拍平
function fn(arr) {
  let arr1 = [];
  arr.forEach((val) => {
    if (Array.isArray(val)) {
      arr1 = arr1.concat(fn(val));
    } else {
      arr1.push(val);
    }
  });
  return arr1;
}
// 递归写法
function flat(a) {
  let newArr = [];
  function dp(arr) {
    arr.forEach((item) => {
      if (Array.isArray(item)) {
        dp(item);
      } else {
        newArr.push(item);
      }
    });
  }
  dp(a);
  return newArr;
}

// 二分查找-前提是有序的
function binarySearch(arr, target) {
  let l = 0;
  let r = arr.length - 1;
  while (l <= r) {
    let mid = Math.floor((l + r) / 2);
    if (arr[mid] == target) {
      return mid;
    }
    if (arr[mid] < target) {
      l = mid + 1;
    }
    if (arr[mid] > target) {
      r = mid - 1;
    }
  }
  return -1;
}
console.log(binarySearch([0, 1, 2, 3, 4, 5], 4));

// 冒泡
function bubble(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[i]) {
        const cache = arr[i];
        arr[i] = arr[j];
        arr[j] = cache;
      }
    }
  }
  return arr;
}
console.log(bubble([5, 3, 2, 6])); // [2, 3, 5, 6]

// 快排
function quickSort(arr) {
  if (arr.length <= 1) return arr; // 注意结束条件
  const midVal = arr.splice(Math.floor(arr.length / 2), 1)[0]; //  注意这里用了splice,主意取[0]
  const leftArr = [];
  const rightArr = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < midVal) {
      leftArr.push(arr[i]);
    } else {
      rightArr.push(arr[i]);
    }
  }
  return quickSort(leftArr).concat(midVal, quickSort(rightArr)); // 注意这里加了midVal
}
console.log(quickSort([5, 3, 2, 6])); // [2, 3, 5, 6]

// 归并排序
function mergeSort(arr) {
  if (arr.length < 2) return arr;
  const midIndex = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, midIndex);
  const rightArr = arr.slice(midIndex);
  // 这里开始和快排不同，这里不去遍历了，改用merge了，merge是一个while循环，所以复杂度还是n
  return merge(mergeSort(leftArr), mergeSort(rightArr));
}
function merge(a, b) {
  const result = [];
  while (a.length && b.length) {
    a[0] > b[0] ? result.push(b.shift()) : result.push(a.shift());
  }
  return result.concat(a, b); // 最后concat是当a,b个数不同的时候，把最后一个放在最后
}
console.log(mergeSort([5, 3, 2, 6])); // [2, 3, 5, 6]

// 滑动窗口，对撞指针
// 找到有序数组中最短的连续子数组，子数组之和>=s（209）
function minArrLength(num, arr) {
  let cacheLen = Infinity;
  let l = 0;
  let r = 0;
  let sum = 0;
  while (r < arr.length) {
    // 右侧小于长度就行
    sum = sum + arr[r];
    while (sum >= num) {
      cacheLen = Math.min(cacheLen, r - l + 1); // 记得+1
      sum = sum - arr[l];
      l++;
    }
    r++;
  }
  return cacheLen === Infinity ? 0 : cacheLen;
}
minArrLength(7, [7, 3, 1, 2, 4, 1]); // 1

// 符号
function fun(str) {
  const arrLeft = ['(', '{', '['];
  const obj = {
    '(': ')',
    '{': '}',
    '[': ']',
  };
  const memo = [];
  const res = str.split('').every((item) => {
    if (arrLeft.indexOf(item) > -1) {
      memo.push(item);
      return true;
    } else {
      const curr = memo.pop();
      if (item == obj[curr]) {
        return true;
      } else {
        return false;
      }
    }
  });
  console.log(!!res);
  return !!res;
}
fun('{[}');

// obj的应用
// 给一个数组(可以无序)，返回两个值等于 target 的索引（1）
// 三个数字相加等于sum的话，就遍历两层，另外一层用map
var twoSum = function (nums, target) {
  let map = new Map();
  let cacheIndexArr = [];
  nums.forEach((item, index) => {
    map.set(item, index);
  });
  nums.some((item, index) => {
    const val = target - item;
    // 防止3取到自身为3的时候，相当于取了两次自己
    if (map.has(val) && index != map.get(val)) {
      cacheIndexArr.push(index);
      cacheIndexArr.push(map.get(val));
      return true;
    }
    return false;
  });
  return cacheIndexArr;
};
console.log(twoSum([3, 2, 4], 6)); // [1, 2]

// 链表
// 每两个相邻的链表交换位置（24）
// 之前temp -> node1 -> node2
// 之后temp -> node2 -> node1
// 虚拟节点再设置成node1，继续下一轮
var swapPairs = function (head) {
  const dummyHead = new ListNode(0);
  dummyHead.next = head;
  let temp = dummyHead;
  while (temp.next !== null && temp.next.next !== null) {
    const node1 = temp.next;
    const node2 = temp.next.next;
    // 下边的顺序背下来就行
    temp.next = node2;
    node1.next = node2.next;
    node2.next = node1;
    temp = node1; // 如果只是反转链表这里改成node2,然后所有都需要遍历一遍
  }
  return dummyHead.next; // 这里一定是dummyHead
};

// 反转链表-就地反转
// 虚拟节点取curr后的值
var reverseList = function (head) {
  let [prev, curr] = [null, head];
  while (curr) {
    let tmp = curr.next; // 1. 临时存储当前指针后续内容
    curr.next = prev; // 2. 反转链表
    prev = curr; // 3. 接收反转结果
    curr = tmp; // 4. 接回临时存储的后续内容
  }
  return prev;
};

// 广度优先遍历
var levelOrder = function (root) {
  let queue = [root];
  let nums = [];
  if (!root) return nums;
  while (queue.length > 0) {
    const tempNode = queue.shift();
    nums.push(tempNode.val);
    if (tempNode.left) queue.push(tempNode.left);
    if (tempNode.right) queue.push(tempNode.right);
  }
  return nums;
}; // [3,9,20,15,7]

// 广度优先遍历-分层
var levelOrder = function (root) {
  let queue = [root];
  let res = [];
  if (!root) return res;
  while (queue.length > 0) {
    let nowRes = [];
    let next = [];
    while (queue.length > 0) {
      const tempNode = queue.shift();
      nowRes.push(tempNode.val);
      if (tempNode.left) next.push(tempNode.left);
      if (tempNode.right) next.push(tempNode.right);
    }
    queue = next;
    res.push(nowRes); 
  }
  return res;
}; // 分层[[3],[9,20],[15,7]]

// 图像旋转 - 这种方法只使用于n*n，如果n*m还得找规律
// 这个空间复杂度增加了 复制了一个数组
function rotate(arr) {
  var n = arr.length;
  var memo = new Array(n).fill(0).map(() => new Array(n));
  for (var i = 0; i < n; i++) {
    for (var j = 0; j < n; j++) {
      memo[i][j] = arr[j][i];
    }
  }
  return memo.map((item) => item.reverse());
}
console.log(
  rotate([
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
  ])
);
// var rotate = function (matrix) {
//   let matrixLength = matrix.length;
//   for (let i = 0; i < matrixLength; i++) {
//     for (let j = i; j < matrixLength; j++) { // !!!注意：这里是从i开始的
//       let temp = matrix[i][j];
//       matrix[i][j] = matrix[j][i];
//       matrix[j][i] = temp;
//     }
//   }
//   return matrix.map((item) => item.reverse());
// };
// 螺旋矩阵

// 求二叉树深度
var maxDepth = function (root) {
  if (root == null) return 0;
  const left = maxDepth(root.left);
  const right = maxDepth(root.right);
  return Math.max(left, right) + 1;
};

// 反转二叉树
var invertTree = function (root) {
  if (root === null) {
    return null;
  }
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
};
// 判断二叉树是否一样 - 可以转为数组，然后转为字符串，判断字符串是否相同

// 判断是否左右对称
var isSymmetric = function (root) {
  function check(left, right) {
    if (left.val == right.val) {
      return check(left.left, right.right) && check(left.right, right.left);
    }
    return false;
  }
  check(root.left, root.right);
};
// 不好理解
// var check = function (left, right) {
//   if (!left && !right) return true;
//   if (!left || !right) return false;
//   return (
//     left.val == right.val &&
//     check(left.left, right.right) &&
//     check(left.right, right.left)
//   );
// };
// var isSymmetric = function (root) {
//   return check(root, root);
// };

// 判断二叉树和为 sum 的路径，必须包含子叶，必须到底（112）
const hasPathSum = (root, sum) => {
  // 溯源的终止条件，且从顶到底，顶部就是知道sum总和知道，然后一点一点减
  if (root == null) return sum == 0;
  return (
    hasPathSum(root.left, sum - root.val) ||
    hasPathSum(root.right, sum - root.val)
  );
};

// 二叉搜索树最近公共祖先
const lowestCommonAncestor = (root, p, q) => {
  if (p.val < root.val && q.val < root.val) {
    return lowestCommonAncestor(root.left, p, q);
  }
  if (p.val > root.val && q.val > root.val) {
    return lowestCommonAncestor(root.right, p, q);
  }
  return root;
};

// 将有序数组转换为二叉搜索树(108)
var sortedArrayToBST = function (nums) {
  function bfs(arr) {
    if (arr.length == 0) return null;
    const mid = Math.floor(arr.length / 2);
    const curr = arr[mid];
    const left = arr.slice(0, mid);
    const right = arr.slice(mid + 1);
    const node = new TreeNode(curr);
    node.left = bfs(left);
    node.right = bfs(right);
    return node;
  }
  return bfs(nums);
};

// 回溯 -- 全排列！！！
// 给一个数组，返回所有排列可能-全排列（46）（47）
// 46 - 没有重复
// 输入: [1,2,3]
// 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
function arrange(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);
  function dfs(start, temp) {
    if (start == nums.length) {
      result.push(temp.slice());
      return;
    }
    for (var i = 0; i < nums.length; i++) {
      if (used[i]) continue; // 这里记得判断已经取过的值
      used[i] = true;
      temp.push(nums[i]);
      dfs(start + 1, temp); // 这里的start只是一个计数器，和下边不太一样
      used[i] = false;
      temp.pop();
    }
  }
  dfs(0, []);
  console.log(result);
  return result;
}
arrange([1, 2, 3]);

// 47 - 有重复
// 输入: [1,1,3]
// 输出: [[1,1,3],[1,3,1],[3,1,1]]
function arrange(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);
  function dfs(start, temp) {
    if (start == nums.length) {
      result.push(temp.slice());
      return;
    }
    for (var i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (nums[i] == nums[i - 1] && !used[i - 1]) continue; // 只多了这么一句区别，保证顺序，上一个都还没取过呢就先跳过，保证唯一次
      used[i] = true;
      temp.push(nums[i]);
      dfs(start + 1, temp); // 这个start只是一个计时器
      used[i] = false;
      temp.pop();
    }
  }
  nums.sort((x, y) => x - y); // 这里进行排序
  dfs(0, []);
  console.log(result);
  return result;
}
arrange([1, 1, 3]);

// 回溯 -- 求和！！！
// 给一个集合，从集合中取几个数(可使用多次)让和为 T，求这样的子集合（39）（40）
// 39 可以重复
// 输入：candidates = [2,3,6,7], target = 7,
// 输出： [ [7], [2,2,3] ]
function arrange(nums, target) {
  const result = [];
  function dfs(start, temp, sum) {
    if (sum > target) {
      return;
    }
    if (sum == target) {
      return result.push(temp.slice());
    }
    for (var i = start; i < nums.length; i++) {
      temp.push(nums[i]);
      dfs(i, temp, sum + nums[i]);
      temp.pop(); // 因为temp是一个引用类型，所以需要操作，sum不是引用类型不用修改
    }
  }
  dfs(0, [], 0);
  console.log(result);
  return result;
}
arrange([2, 3, 6, 7], 7);
// 40 不可以重复
// 输入: candidates = [10,1,2,7,6,1,5], target = 8,
// 输出: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
function arrange(nums, target) {
  const result = [];
  function dfs(start, temp, sum) {
    if (sum > target) {
      return;
    }
    if (sum == target) {
      return result.push(temp.slice());
    }
    for (var i = start; i < nums.length; i++) {
      if (i - 1 >= start && nums[i - 1] == nums[i]) continue; //这个是过滤数组内重复的问题
      temp.push(nums[i]);
      dfs(i + 1, temp, sum + nums[i]); // 这里用i+1是为了避免遍历时取到重复的值
      temp.pop();
    }
  }
  nums.sort((x, y) => x - y);
  dfs(0, [], 0);
  console.log(result);
  return result;
}
arrange([10, 1, 2, 7, 6, 1, 5], 8);

// 回溯 -- 子集
// 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）（78）（90）
// 78 - 不含重复字符
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
const subsets = (nums) => {
  const res = [];
  const dfs = (start, temp) => {
    res.push(temp.slice()); // 无条件 区别
    for (let i = start; i < nums.length; i++) {
      // 这里从start开始,避免往回选
      temp.push(nums[i]);
      dfs(i + 1, temp);
      temp.pop();
    }
  };

  dfs(0, []);
  console.log(res);
  return res;
};
subsets([1, 2, 3]);

// 90 - 含重复字符
// 输入: [1,2,2]
// 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
const subsets = (nums) => {
  const res = [];
  const dfs = (start, temp) => {
    res.push(temp.slice());
    for (let i = start; i < nums.length; i++) {
      // 这里从start开始,避免往回选
      if (nums[i] == nums[i - 1] && i != start) continue; //这个条件很重要,只取一次2为初始的情况 区别在这里
      temp.push(nums[i]);
      dfs(i + 1, temp); // 这里避免start后的重复选择
      temp.pop();
    }
  };
  nums.sort((a, b) => a - b);
  dfs(0, []);
  console.log(res);
  return res;
};
subsets([1, 2, 2]);

// 自己延伸 几个数组，每个取一项，一共有多少种方法组合
function merge(arr) {
  const result = [];
  function dfs(start, temp) {
    if (start == arr.length) {
      return result.push(temp.slice());
    }
    for (var i = 0; i < arr[start].length; i++) {
      temp.push(arr[start][i]);
      dfs(start + 1, temp); // 这里是start+1
      temp.pop();
    }
  }
  dfs(0, []);
  console.log(result);
}
merge([
  [1, 2],
  [3, 4],
  [5, 6],
]);
// 结果：[ [ 1, 3, 5 ],[ 1, 3, 6 ],[ 1, 4, 5 ],[ 1, 4, 6 ],[ 2, 3, 5 ],[ 2, 3, 6 ],[ 2, 4, 5 ],[ 2, 4, 6 ] ]

// 动态规划
// 斐波那契
function fib(num) {
  const temp = new Array(num + 1).fill(-1); // 这里是n+1
  temp[0] = 0;
  temp[1] = 1;
  for (var i = 2; i <= num; i++) {
    // 这里可以=
    temp[i] = temp[i - 1] + temp[i - 2];
  }
  console.log(temp);
  return temp[num];
}
fib(4);
// 递归
function fib(n) {
  if (n <= 1) {
    return 1;
  }
  return fib(n - 1) + fib(n - 2);
}

// 1/2节台阶 - 也可以全排列求和可重复
function fib(num) {
  const temp = new Array(num + 1).fill(-1); // 这里是n+1
  temp[0] = 0; //
  temp[1] = 1; // 走一节有一种走法
  temp[2] = 2; // 走两节有两种走法
  for (var i = 3; i <= num; i++) {
    // 这里可以=num
    temp[i] = temp[i - 1] + temp[i - 2];
  }
  console.log(temp);
  return temp[num];
}
fib(4);
// 递归 - 见斐波那契的递归
// function step(n) {
//   const temp = [];
//   temp[0] = 0; //
//   temp[1] = 1; // 走一节有一种走法
//   temp[2] = 2; // 走两节有两种走法
//   function dp(index) {
//     if (index >= n) return;
//     temp[index] = temp[index - 1] + temp[index - 2];
//     index++;
//     dp(index);
//   }
//   dp(3);
//   console.log(temp);
// }
// step(5);
// 打印所有方法
function step(n) {
  memo = [];
  function dp(sum, temp) {
    if (sum == 0) {
      return memo.push(temp.slice());
    }
    if (sum < 0) return;
    console.log(sum);
    for (var i = 1; i <= 2; i++) {
      temp.push(i);
      dp(sum - i, temp);
      temp.pop();
    }
  }
  dp(n, []);
  console.log(memo);
}
step(5);
// 机器人，m\*n 矩阵，从左上向右下，只能右和下，有多少种走法（62）
// 输入：m = 3, n = 7
// 输出：28
var uniquePaths = function (m, n) {
  const memo = new Array(m).fill(0).map(() => new Array(n).fill(0));
  // dp[0][j] = 1，dp[i][0] = 1
  // 因为一直向下或者一直向右走而不转向的话只有一种走法
  for (var i = 0; i < m; i++) {
    memo[i][0] = 1;
  }
  for (var j = 0; j < n; j++) {
    memo[0][j] = 1;
  }
  for (var i = 1; i < m; i++) {
    for (var j = 1; j < n; j++) {
      memo[i][j] = memo[i - 1][j] + memo[i][j - 1]; // 这里是走法，只用相加就可以，不用比大小
    }
  }
  return memo[m - 1][n - 1];
};
uniquePaths(3, 7);

// 背包问题 - 最大价值
function bag(w, v, C) {
  const n = w.length;
  const memo = new Array(n).fill(0).map(() => new Array(C + 1).fill(0));
  for (var j = 0; j <= C; j++) {
    memo[0][j] = j > w[0] ? v[0] : 0; // 第一行初始化
  }
  for (var i = 1; i < n; i++) {
    for (var j = 0; j <= C; j++) {
      memo[i][j] = memo[i - 1][j]; // 不放入和上一项保持一致
      if (j > w[i]) {
        // 当大于要取的项时才有比较的意义
        memo[i][j] = Math.max(memo[i][j], memo[i - 1][j - w[i]] + v[i]);
      }
    }
  }
  console.log(memo);
  return memo[n - 1][C];
}
bag([2, 1, 3, 2], [12, 10, 20, 15], 10);
// 完全背包 - 最大价值
function bag(w, v, C) {
  const n = w.length;
  const memo = new Array(n).fill(0).map(() => new Array(C + 1).fill(0));
  for (var j = 0; j <= C; j++) {
    memo[0][j] = j > w[0] ? v[0] : 0; // 第一行初始化
  }
  for (var i = 1; i < n; i++) {
    for (var j = 0; j <= C; j++) {
      for (var k = 1; k < j / w[i]; k++) {
        //区别就是这里的k
        memo[i][j] = memo[i - 1][j]; // 不放入和上一项保持一致
        if (j > w[i]) {
          // 当大于要取的项时才有比较的意义
          memo[i][j] = Math.max(
            memo[i][j],
            memo[i - 1][j - k * w[i]] + k * v[i]
          );
        }
      }
    }
  }
  console.log(memo);
  return memo[n - 1][C];
}
bag([2, 1, 3, 2], [12, 10, 20, 15], 10);
// 最长递增子序列（300）
var lengthOfLIS = function (nums) {
  var memo = new Array(nums.length - 1).fill(1);
  if (nums.length == 0) return 0;
  for (var i = 1; i < nums.length; i++) {
    for (j = 0; j < i; j++) {
      // memo[i] = nums[i] > nums[j] ? memo[j] + 1 : memo[j];
      memo[i] = Math.max(memo[i], memo[j]);
      if (arr[i] > arr[j]) {
        memo[i] = Math.max(memo[i], memo[j] + 1);
      }
    }
  }
  let val = 0;
  memo.forEach((res) => {
    val = res > val ? res : val;
  });
  console.log(val);
  console.log(memo);
  return val;
};
lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]);
// 最长公共子序列 LCS(1143)
var longestCommonSubsequence = function (text1, text2) {
  const n = text1.length;
  const m = text2.length;
  const memo = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
  for (var i = 1; i <= n; i++) {
    for (var j = 1; j <= m; j++) {
      memo[i][j] = Math.max(memo[i][j - 1], memo[i - 1][j]);
      if (text1[i - 1] == text2[j - 1]) {
        // 这里要计算第0位，但是循环是从1开始的，所以要-1
        memo[i][j] = memo[i][j] + 1;
      }
    }
  }
  console.log(memo);
  return memo[n][m];
};