前端算法

实现let

// 加_
for(var _i=0;_i<5;_i++){}
// 立即函数表达式
(
  for(var i=0;i<5;i++){}
)()

实现const

// 实现一个const
function myconst(key, value) {
  let desc = {
    value,
    writable: false,
  };
  Object.defineProperty(window, key, desc);
}
myconst("name", { a: 1 });

实现call、apply、bind

// 实现一个function.call(thisArg, arg1, arg2, ...)
Function.prototype.mycall = function (thisArg, ...args) {
  thisArg.fn = this;
  return thisArg.fn(...args);
};
// apply
Function.prototype.myapply = function (thisArg, args) {
  thisArg.fn = this;
  return thisArg.fn(...args);
};
// bind
Function.prototype.mybind = function (thisArg, ...args) {
  return this.call(thisArg, ...args);
};

实现new

// 模拟实现new
function myNew(foo, ...args) {
    // Object.create()函数的含义：创建一个对象，并让该对象的__proto__指向参数，
    // 这里的参数是foo.prototype，意思是指向foo的原型对象
  let obj = Object.create(foo.prototype); 
  let result = foo.apply(obj, args); // 这里obj调用了foo函数，就会被加上foo函数里带有this.xxx的属性，于是就有obj.name, obj.age等
  return typeof result === "object" ? result : obj; // 这里的result是调用foo函数所返回的结果，如果该结果是对象，则返回该对象，否则返回上面所创建的对象obj
} // 相当于 let str = new foo();

防抖debounce函数

// 防抖函数
function debounce(fn, wait) {
  let timeout = null;
  return function () {
    let context = this;
    let args = arguments;
    if (timeout) clearTimeout(timeout);
    else {
      timeout = setTimeout(() => {
        fn.apply(context, args);
      }, wait);
    }
  };
}
// 防抖测试：
function debounceTest(age) {
  console.log("防抖测试", this.name, age);
}
let person = {
  name: "oneper",
};
debounce(debounceTest, 4000).call(person, 18); // 4秒后：防抖测试, oneper, 18

节流throttle函数

// 节流函数
function throttle(fn, wait) {
  let timeout = null;
  return function () {
    const thisArg = this;
    const args = arguments;
    if (!timeout) {
      setTimeout(() => {
        fn(thisArg, args);
        timeout = null;
      }, wait);
    }
  };
}

数组扁平化

const arr = [1, [2, 3], [4, [5, 6]]];
// 1.flat(Infinity) -- ＜（＾－＾）＞
arr.flat(Infinity);
// 2.序列化后正则去全部括号，添左右括号，反序列化 -- ＜（＾－＾）＞
const str = `[${JSON.stringify(arr).replace(/(\[|\])/g, "")}]`;
JSON.parse(str);
// 3.递归 -- ＜（＾－＾）＞
function myflat(arr) {
  let result = [];
  for (const item of arr) {
    item instanceof Array
      ? (result = result.concat(flat(item)))
      : result.push(item);
  }
  return result;
}
// 4.自创 -- ＜（＾－＾）＞
JSON.parse(`[${arr.toString()}]`);
// 5.reduce()递归
function myflatSec(arr) {
  return arr.reduce((result, cur) => {
    return result.concat(cur instanceof Array ? myflatSec(cur) : cur);
  }, []);
}
// 6.迭代+展开运算符
function myflatThr(arr) {
  while (arr.some(Array.isArray)) {
    arr = [].concat(...arr);
  }
}

数组去重

数组去重

// 1. 原始办法：双重循环
function unique(arr = []) {
  let result = [];
  for (let i = 0, arrLen = arr.length; i < arrLen; i++) {
    for (let j = 0, resLen = result.length; j < resLen; j++) {
      if (arr[i] === result[j]) break;
    }
    if (j === resLen) {
      res.push(arr[i]);
    }
  }
  return res;
}
// 2. 数组方法indexOf
function unique2(arr = []) {
  let result = [];
  for (let item of arr) {
    if (result.indexOf(item) === -1) result.push(item);
  }
  return result;
}
// 3. 排序后，后不等前则添加
function unique3(arr = []) {
  let result = [];
  let sortedArr = [...arr];
  sortedArr.sort((a, b) => a - b);
  for (let i = 0; i < sortedArr.length; i++) {
    if (i === 0) result.push(sortedArr[i]);
    else if (sortedArr[i] !== sortedArr[i - 1]) result.push(sortedArr[i]);
  }
  return result;
}

数组乱序

1. arr.sort(()=>Math.random()-0.5)，但不是真正的乱序
2. 利用洗牌算法思路：
   1. 从数组末尾开始，向前推进，每次随机和数组中一个元素进行交换

      数组最大、最小值

      深拷贝

      ```javascript // 1.递归 function clone(obj) { // 深拷贝的实现, 递归实现 // 是不是有点N叉树遍历的感觉？！ let buf; if (obj instanceof Array) { // 若为数组 buf = [] //创建一个空数组来存 let i = obj.length while (i—) { buf[i] = clone(obj[i]) } return buf } else if (obj instanceof Object) { // 若为对象 buf = {} // 创建一个空对象来存 for (let i in obj) { buf[i] = clone(obj[i]) } return buf } else { // 基本数据类型 return (obj) } }

// 2. JSON, 只能用于对象内部没有方法时 JSON.parse(JSON.stringify(obj))

<a name="5ahlZ"></a>
## 浅拷贝
<a name="ynuOs"></a>
## 遍历
1. 数组的遍历：
```javascript
let arr = [1, 2, 3];
/1. 原始for方法
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}
/2. for...in 也会将数组的属性遍历出来
arr.name = "joy";
for (let item in arr) {
  console.log(item); // 0, 1, 2, name
  console.log(arr[item]); // 1, 2, 3, joy
}
/3. for...of
arr.name = "joy";
for (let item of arr) {
  console.log(item); // 1, 2, 3
}

1. 对象的遍历： ```javascript let obj = { name: “joy”, age: 18, school: “fzu”, };

/1. for…in for (let item in obj) { console.log(item); // name, age, school console.log(obj[item]); // “joy”, 18, “fzu” }

/2. Object.keys(obj), Object.values(obj), Object.entries(obj) Object.keys(obj).map((item)=>{ console.log(item); // name, age, school })

3. 类数组的遍历
```javascript
/ for...of
// for...of语句在可迭代对象(包括 Array, Map, Set, String, TypedArray，arguments 对象等等)上创建一个迭代循环

创建对象的几种模式

参考资料：

• 《JS高级程序设计》
• 面向对象的程序设计

工厂模式

构造函数模式

与其它函数不同，函数内部使用this，且通过new操作符进行调用，new操作符做了两件事：1. 创建一个对象并将其proto指向该（构造）函数；2. 通过apply方法将该（构造）函数的this指向该对象。注意构造函数和普通函数没有区别，只是任何函数通过new操作符调用就被称为构造函数。

原型模式

原型模式即将属性和方法下放到函数的原型对象中：如Function.prototype.name = “mode”

原型+构造函数模式组合

ES5实现继承的4种方式

谈到继承，那么自然就会想到谁继承谁，于是就有子类和父类。至少两个以上的角色才能谈“继承”。

1. 原型链继承

直接让子类的原型对象指向父类实例（即可以调用父类的属性、方法，及其原型上的方法），当子类实例找不到对应的属性和方法时，就会往它的原型对象，也就是父类实例上找，从而实现对父类的属性和方法的继承。

Child.prototype = new Parent();
Child.prototype.constructor = Child;

缺点：

1. 所有Child实例原型都指向同一个Parent实例，因此对某个Child实例的父类引用类型变量修改会影响所有的Child实例。
2. 在创建子类实例时无法向父类构造传参, 即没有实现super()的功能

2. 构造函数继承

构造函数继承，即在子类的构造函数中执行父类的构造函数，并为其绑定子类的**this**，让父类的构造函数把成员属性和方法都挂到子类的this上去，这样既能避免实例之间共享一个原型实例，又能向父类构造方法传参。

function Parent(name){
  this.name = name;
}
function Child(){
  Parent.apply(this, args);
}

缺点：父类原型对象上的属性和方法无法被子类使用。

3. 组合式继承

组合使用原型链继承和构造函数继承

function Parent(name){
  this.name = name;
}
function Child(){
  Parent.apply(this, args);
}
Child.prototype = new Parent();
Child.prototype.constructor = Child;

缺点：期间调用了2次父类，分别是Parent.apply和new Parent()。

4. 寄生组合式继承

对组合式继承的改进：

Child.prototype = Object.create(Parent.prototype)

ES5实现继承与ES6中class对比

Sleep

// 使用定时器, 是异步的, 所以无法堵塞
function sleep(delay) {
    setTimeout(function () {}, delay * 1000)
}
console.log('a')
sleep(10)
console.log('b')
// 使用伪死循环堵塞JS单线程
function sleep(delay) {
    var start = (new Date()).getTime();
    while ((new Date()).getTime() - start < delay * 1000) {
        continue
    }
}
console.log('a')
sleep(2)
console.log('b')
// await / async
// await则是进行执行顺序控制，每次执行一个await，
// 程序都会暂停等待await返回值，然后再执行之后的await
function sleep(time) {
    return new Promise((resolve) => {
        setTimeout(resolve, time)
    })
}
(async function output() {
    console.log(2)
    let out = await sleep(2000);
    console.log(1);
})()
//Promise
var sleep = (time) => {
    return new Promise((resolve) => {
        setTimeout(resolve, time)
    })
}
sleep(2000).then((res) => {
    console.log(res + ' ' + 1)
})

函数柯里化

特点：有参数时，返回一个函数；没有参数时，执行这个函数，得到计算的结果

// 函数的柯里化
// 需求：要实现一个这样的加法函数，使得：add(1,2,3)(1)(2)(3)(4,5,6)(7,8)() === 42
// 分析这个函数的特点: 当这个函数有参数的时候，返回的是一个函数
// 如果没有参数的时候，就会去执行这个函数，得到计算的结果
function add() {
  let list = [];
  list = list.concat([...arguments]); // 类数组先转为数组
  return function () {
    // 如果传了参数，则length不为0
    if (arguments.length) {
      list = list.concat([...arguments]);
      return arguments.callee;
    } else {
      // 否则开始遍历数组，计算结果
      return list.reduce((a, b) => {
        return a + b;
      });
    }
  };
}
console.log(add(1, 2, 3)(1, 2, 4, 5, 6)());

JS中sort排序的用法

基本用法：arr.sort()，数组中的数字将会转换成字符进行比较，按从小到大排列。默认排序顺序是根据字符串Unicode码点
sort提供一个比较函数function(a,b)。

1. 不传任何参数，按照字符串Unicode码点进行排序。
2. 传入参数，可实现数字的升序、降序：
   1. 升序：arr.sort((a,b)=>a-b)
   2. 降序：arr.sort((a,b)=>b-a)
3. 根据数组中对象的某个属性值进行排序：arr.sort((a,b)=>a.id-b.id)
4. 根据数组对象中多个属性值进行排序、多条件排序：

   var arr6 = [{id:10,age:2},{id:5,age:4},{id:6,age:10},{id:9,age:6},{id:2,age:8},{id:10,age:9}];
   arr6.sort(function(a,b){
   　　if(a.id === b.id){//如果id相同，按照age的降序
   　　　　return b.age - a.age
   　　}else{
   　　　　return a.id - b.id
   　　}
   })

将扁平数据转为树状格式

https://blog.csdn.net/qq_37746973/article/details/78662177
假设后端同学通过接口向前端返回了行业信息列表，为了取用方便，我们希望可以将其转换为树状格式，例如：

let list = [
  {
    parent_ind: "女装",
    name: "连衣裙",
  },
  {
    name: "女装",
  },
  {
    parent_ind: "女装",
    name: "半身裙",
  },
  {
    parent_ind: "女装",
    name: "A字裙",
  },
  {
    parent_ind: "电脑配件",
    name: "内存",
  },
  {
    name: "数码",
  },
  {
    parent_ind: "数码",
    name: "电脑配件",
  },
];

转化为：

{
  "数码": {
    "电脑配件": {
      "内存" : {}
    }
  },
  "女装" : {
    "连衣裙": {},
    "半身裙": {},
    "A字裙": {}
  }
}

function convert_format(data = []) {
  const index = {
    undefined: {},
  };
  data.forEach((item) => {
    index[item.name] = {};
  });
  data.forEach((item) => {
    index[item.parent_ind][item.name] = index[item.name]; // 对于没有parent_id的项来说, parent_id是undefined
  });
  return index.undefined;
}

// 解法2
function convert_format(data) {
    let groups = {} // 生成个体对象
    let tree = {} // 存储最终结果
    const getGroup = key => {
        if (!Reflect.has(groups, key)) {
            Reflect.set(groups, key, {})
        }
        return Reflect.get(groups, key)
    }
    for (let item of data) {
        let group = getGroup(item.name)
        if (Reflect.has(item, 'parent_ind')) { // 有parent_ind属性
            let parent = getGroup(item.parent_ind) 
            Reflect.set(parent, item.name, group)// 存放有parent_ind属性的对象
        } else { // 无parent_ind属性
            Reflect.set(tree, item.name, group)
        }
    }
    return tree
}

将对象转数组

let items = {
  "3/28/20": 81999,
  "3/29/20": 82122
}
// 转化为
[
  {
    time: "3/28/20",
    number: 81999
  },
  {
    time: "3/29/20",
    number: 82122
  }
]

使用Object.entries：

Object.entries(items).map((entry)=>{
    const [time, number] = entry;
  return {time, number}; //用到了ES6的简写规则
})

深度遍历转换

[{
  codeName: "name1",
  codeValue: "value1",
  nodeList: [{
      codeName: "name11",
      codeValue: "value11",
      nodeList: [{
        codeName: "name111",
        codeValue: "value111"
      }]
    },
    {
      codeName: "name12",
      codeValue: "value12"
    }
  ]
}, {
  codeName: "name2",
  codeValue: "value2",
  nodeList: [{
      codeName: "name21",
      codeValue: "value21"
    },
    {
      codeName: "name22",
      codeValue: "value22"
    }
  ]
}]

转换为：

[{
  label: "name1",
  value: "value1",
  children: [{
      label: "name11",
      value: "value11",
      children: [{
        label: "name111",
        value: "value111"
      }]
    },
    {
      label: "name12",
      value: "value12"
    }
  ]
}, {
  label: "name2",
  value: "value2",
  children: [{
      label: "name21",
      value: "value21"
    },
    {
      label: "name22",
      value: "value22"
    }
  ]
}]

我的解法：

const dfsBasedTransform = (arr, type) => {
  let obj = {};
  let result = [];
  arr.map((item) => {
    if (item.codeName) obj.label = item.codeName;
    if (item.codeValue) obj.value = item.codeValue;
    if (item.nodeList)
      obj.children = dfsBasedTransform(item.nodeList, "object");
    result.push(obj);
  });
  if (type === "array") return result;
  else if (type === "object") return obj;
};

数据过滤与转换

[ [true, 'value1'], [false, 'value2']]
==>
[{ value: 'value1' }]

我的解法：

const normalizeData = (arr = []) => {
  return arr.reduce((pre, cur) => {
    const [key, value] = cur;
    if (key) return pre.concat({ value });
    return pre;
  }, []);
};