Johnny's blog

手写系列

去重

// set && map
function unique(arr) {
   return Array.from(new Set(arr))
}
function unique(arr) {
    const seen = new Map()
    return arr.filter((a) => !seen.has(a) && seen.set(a, 1))
}
// 双重循环
function unique(arr) {
  for(let i=arr.length-1;i>0;i--) {
		for(let j=0;j<i;j++){
      if(arr[i] === arr[j]) arr.splice(i,1)
    }
  }
  return arr
}
function unique(array) {
    return array.filter(function(item, index){
        return array.indexOf(item) === index;
    })
}
// 排序后去重
function unique(arr) {
    return arr.sort().filter(function(item, index, array){
        return !index || item !== array[index - 1]
    })
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

排序

2.1.快排

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const index = Math.floor((arr.length - 1) / 2);
  const center = arr.splice(index, 1)[0];
  let right = [];
  let left = [];
  arr.forEach(item => {
    if (item > center) {
      right.push(item);
    } else {
      left.push(item);
    }
  });
  return quickSort(left).concat([center], quickSort(right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2冒泡

function bSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      // 每轮都是从0开始左右两两对比 每轮选择一个最大的
      if (arr[j] > arr[j+1]) {
        let temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3选择

function sSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let cur = i;
    for (let j = i + 1; j < arr.length; j++) {
      // 第i个和后面每个对比 有更小的就记录下来 每轮选出最小的
      if (arr[j] < arr[cur]) {
        cur = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[cur];
    arr[cur] = temp;
  }
  return arr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.4归并

function mergeSort(arr) { // 拆分
  if (arr.length <= 1) return arr;
  const mid = Math.floor((arr.length) / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) { // 合并
  const res = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  return res.concat(left, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

深拷贝

function deepClone(obj) {
    let cloneObj;
    if (obj && typeof obj !== 'object') {
        cloneObj = obj;
    } else if (obj && typeof obj === 'object') {
        cloneObj = Array.isArray(obj) ? [] : {};
        for (let key in obj) {
            if (obj.hasOwnProperty(key)) {
                if (obj[key] && typeof obj[key] === 'object') {
                    cloneObj[key] = deepClone(obj[key]);
                } else {
                    cloneObj[key] = obj[key];
                }
            }
        }
    }
    return cloneObj;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

new、call、apply、bind

/* 当没有第二个参数的情况下，apply和call无区别。
apply后面的参数是一个类数组对象可以是数组，arguments，或任何有length属性的对象
call后面可以是任何数量的参数 */
function mynew () {
  const obj = new Object();
  const fn = Array.prototype.shift.apply(arguments); // 取arguments第一个参数
  obj.__proto__ = fn.prototype;
  const result = fn.apply(obj, arguments);
  return typeof result === 'object' ? result : obj;
}
1
2
3
4
5
6
7
8
9
10
Function.prototype.bind = function (context) {
    var _this = this
    var args = Array.prototype.slice.call(arguments, 1)
    return function() {
        return _this.apply(context, args)
    }
}
Function.prototype.myCall = function (context = window,...args) {
  var func = this,
      fn = Symbol('fn'); // 确保属性名独一无二
  context[fn] = func; // 这里的转变：调用者（函数）作为context对象的方法
  var res = context[fn](...args);
  delete context[fn]; // 记得将context对象上刚刚新增的func方法删除
  return res;
}
Function.prototype.myApply = function (context = window,args) {
  var func = this,
      fn = Symbol('fn'); // 确保属性名独一无二
  context[fn] = func; // 这里的转变：调用者（函数）作为context对象的方法
  var res = context[fn](...args);
  delete context[fn]; // 记得将context对象上刚刚新增的func方法删除
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

防抖节流

function debounce(func, wait) {
  let timeout;
  return function() {
    let context = this;
    let args = arguments;
    if (timeout) clearTimeout(timeout);
    timeout = setTimeout(() => {
      func.apply(context, args);
    }, wait);
  };
}
// 使用
window.onscroll = debounce(function() {
  console.log('debounce');
}, 1000);

function throttle(fn, delay) {
  var prevTime = Date.now();
  return function() {
    var curTime = Date.now();
    if (curTime - prevTime > delay) {
      fn.apply(this, arguments);
      prevTime = curTime;
    }
  };
}
// 使用
window.onscroll = throttle(function() {
  console.log('throtte');
}, 1000);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

函数柯里化

其实我们无时无刻不在使用柯里化函数，只是没有将它总结出来而已。它的本质就是将一个参数很多的函数分解成单一参数的多个函数。

实际应用中：

  1. 延迟计算 （用闭包把传入参数保存起来，当传入参数的数量足够执行函数时，开始执行函数）
  2. 动态创建函数 （参数不够时会返回接受剩下参数的函数）
  3. 参数复用（每个参数可以多次复用）
function add() {
    // 第一次执行时，定义一个数组专门用来存储所有的参数
    var _args = Array.prototype.slice.call(arguments);

    // 在内部声明一个函数，利用闭包的特性保存_args并收集所有的参数值
    var _adder = function() {
        _args.push(...arguments);
        return _adder;
    };

    // 利用toString隐式转换的特性，当最后执行时隐式转换，并计算最终的值返回
    _adder.toString = function () {
        return _args.reduce(function (a, b) {
            return a + b;
        });
    }
    return _adder;
}

add(1)(2)(3)                // 6
add(1, 2, 3)(4)             // 10
add(1)(2)(3)(4)(5)          // 15
add(2, 6)(1)                // 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

toString()和valueOf()区别：

默认情况下，执行这个抽象操作时会先执行valueOf方法，如果返回的不是原始值，会继续执行toString方法，如果返回的还不是原始值，那么会报错，如果有指定转换类型时，情况又会有所不同。

（注意：valueOf和toString方法在Date，array等对象中有些是被重写过的，所以不同对象调用此方法可能产生的操作不同，如果没有这些方法，会调用最原始的Object.prototype上的valueOf和toString方法）

toString(): 是返回一个反映这个对象的字符串

valueOf(): 是返回它相应的原始值

实现O(1)的LRU算法

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

LRUCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    // 存在即更新
    let temp = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, temp);
    return temp;
  }
  return -1;
};

LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    // 存在即更新（删除后加入）
    this.cache.delete(key);
  } else if (this.cache.size >= this.capacity) {
    // 不存在即加入
    // 缓存超过最大值，则移除最近没有使用的
    this.cache.delete(this.cache.keys().next().value);
  }
  this.cache.set(key, value);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

10几行实现redux

// 维持应用的 state
// 提供 getState() 方法获取 state
// 提供 dispatch(action) 方法更新 state
// 通过 subscribe(listener) 注册监听器
// 通过 subscribe(listener) 返回的函数注销监听器
// createStore参数为可变参数，第一个参数为reducer，第二个参数为初始state
export function createStore(...arg) {
  let state = null;
  let reducer = arg[0];
  // 使用第二个参数为state初始化
  if (arg.length > 1) { state = arg[1] }
  // 保存监听器的数据
  let listeners = [];
  let getState = () => state;
  let subscribe = listener => listeners.push(listener);
  let dispatch = (action) => {
    //执行reducer函数，更新状态
    state = reducer(state, action);
    //遍历listeners，执行之中的监听器函数
    listeners.forEach(listener => listener());
  }
  return {
    getState,
    dispatch,
    subscribe
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

数组转换为树状结构

const arr = [
  {id: 1, pid: 0},
  {id: 2, pid: 1},
  {id: 3, pid: 2},
  {id: 4, pid: 1},
  {id: 5, pid: 0},
  {id: 6, pid: 5}
];
const tree = [
  {
    id: 1,
    children: [{
      id: 2,
      children: [{
        id: 3,
        chidlren: []
      }]
    }, {
      id: 4,
      children: []
    }]
  },
  {
    id: 5,
    children: [{
      id: 6,
      children: []
    }]
  }
];
function listToTree(arr) {
  const tree = [];
  const toTree = function(arr, tree, id) {
    arr.forEach(item => {
      if (item.pid === id) {
        const obj = {
          id: item.id,
          children: []
        };
        toTree(arr, obj.children, item.id);
        tree.push(obj);
      }  
    });
  }
  toTree(arr, tree, 0);
  return tree;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

Promise

Promise是异步编程的一种解决方案，比传统的回调函数和事件更合理和强大。

所谓Promise，简单来说就是一个容器，里面保存着某个未来才会结束的事情（通常是一个异步操作）。从语法上说，Promise是一个对象，从他可以获取异步操作的消息。

特点：

  • 对象的状态不受外界影响。Promise对象代表一个异步操作，有三种状态：pending（进行中）、fulfilled（已成功）和rejected（已失败）。只有异步操作的结果可以决定当前是哪一种状态，任何其他操作都无法改变这个状态。这也是Promise这个名字的由来。

  • 一旦状态改变，就不会再变，任何时候都是可以得到这个结果的。Promise对象的状态改变只有两种可能：从pending变为fulfilled和从pending变为rejected。只要这两种情况发生，状态就会凝固，不会再变了。再对Promise对象添加回调函数也会立即得到这个结果。有了Promise对象，就可以将异步操作以同步操作的流程表达出来。

缺点：

首先无法取消Promise，一旦新建他就会立即执行，无法中途取消。其次，如果不设置回调函数，Promise内部跑出的错误无法反应到外部。当pending的时候，无法知道进展到了哪一步。

class MyPromise {
  constructor(func) {
    this.status = 'pending'
    this.value = null
    this.resolvedTasks = []
    this.rejectedTasks = []
    this._resolve = this._resolve.bind(this)
    this._reject = this._reject.bind(this)
    try {
      func(this._resolve, this._reject)
    } catch (error) {
      this._reject(error)
    }
  }

  _resolve(value) {
    setTimeout(() => {
      this.status = 'fulfilled'
      this.value = value
      this.resolvedTasks.forEach(t => t(value))
    })
  }

  _reject(reason) {
    setTimeout(() => {
      this.status = 'reject'
      this.value = reason
      this.rejectedTasks.forEach(t => t(reason))
    })
  }

  then(onFulfilled, onRejected) {
    return new MyPromise((resolve, reject) => {
      this.resolvedTasks.push((value) => {
        try {
          const res = onFulfilled(value)
          if (res instanceof MyPromise) {
            res.then(resolve, reject)
          } else {
            resolve(res)
          }
        } catch (error) {
          reject(error)
        }
      })
      this.rejectedTasks.push((value) => {
        try {
          const res = onRejected(value)
          if (res instanceof MyPromise) {
            res.then(resolve, reject)
          } else {
            reject(res)
          }
        } catch (error) {
          reject(error)
        }
      })
    })
  }

  catch(onRejected) {
    return this.then(null, onRejected);
  }
}

// Promise.all() 执行过个 promise 时，只要其中任何一个promise 失败都会执行 reject ，并且 reject 的是第一个抛出的错误信息，只有所有的 promise 都 resolve 时才会调用 .then 中的成功回调
// 实现Promise.all
function promiseAll(promises) {
  return new Promise((resolve, reject) => {
    if (!Array.isArray(promises)){
      throw new TypeError(`argument must be a array`)
    }
    const result = [];
    let count = 0;
    for (let i = 0; i < promises.length; i++) {
      Promise.resolve(promises[i])
        .then(value => {
          count++;
          result[i] = value;
          if (count === promises.length) return resolve(result);
        })
        .catch(err => reject(err));
    }
  });
}

// Promise.allSettled() 可以获取数组中每个 promise 的结果，无论成功或失败
// 实现Promise.allSettled
function promiseAllSettled(promises) {
  return new Promise((resolve, reject) => {
    if (!Array.isArray(promises)){
      throw new TypeError(`argument must be a array`)
    }
    const result = [];
    let count = promises.length;
    for (let i = 0; i < promises.length; i++) {
      promises[i].then(value => {
        result[i] = { status: 'fulfilled', value: value };
      }, error => {
        result[i] = { status: 'rejected', reason: error };
      }).finally(() => {
        if (!--count) resolve(result);
      });
    }
  });
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106