前端手撕系列

手写Promise A+规范

核心步骤：

function myPromise(fun) {
    const _this_ = this;
    this.status = 'pending';
    this.result = undefined;
    this.error = undefined;
    this.successQueen = [];
    this.failQueen = [];

    function resolve(val) {
        if (_this_.status === 'pending') {
            _this_.result = val;
            _this_.status = 'resolved';
            _this_.successQueen.forEach(fn => fn())
        }
    }

    function reject(err) {
        if (_this_.status === 'pending') {
            _this_.status = 'rejected';
            _this_.error = err;
            _this_.failQueen.forEach(fn => fn())
        }
    }

    try {
        fun(resolve, reject)
    } catch(e) {
        reject(e)
    }
}

myPromise.prototype.then = function (success, fail) {
    const _this_ = this;
    let promise2 = undefined;
    if (this.status === 'resolved') {
        promise2 = new myPromise((res, rej) => {
            setTimeout(() => {
                const x = success(_this_.result);
                resolvePromise(promise2, x, res, rej);
            })
        })
    } else if (this.status === 'rejected') {
        promise2 = new myPromise((res, rej) => {
            setTimeout(() => {
                const x = fail(_this_.result);
                resolvePromise(promise2, x, res, rej);
            })
        })
    } else if (this.status === 'pending') {
        promise2 = new myPromise((res, rej) => {
            _this_.successQueen.push(() => {
                setTimeout(() => {
                    const x = success(_this_.result);
                    resolvePromise(promise2, x, res, rej);
                })
            })
            _this_.failQueen.push(() => {
                setTimeout(() => {
                    const x = fail(_this_.result);
                    resolvePromise(promise2, x, res, rej);
                })
            })
        })
    }

}

function resolvePromise(p2, x, resolve, reject) {
    if (x === undefined || x === p2) {
        reject(new TypeError('typeError'));
    }

    if ((typeof x === 'function' || typeof x === 'object') && x.then) {
        x.then.call(x, function(y) {
            resolvePromise(p2, y, resolve, reject);
        }, function(rej) {
            reject(rej);
        })
    } else {
        resolve(x);
    }
}

手写一个call

function myCall() {
    const context = [ ...arguments ][0];
    const self = this;
    context.fun = self;
    const args = [ ...arguments ].slice(1);
    const res = context.fun(...args);
    delete context.fun;
    return res;
}

手写一个bind（可以使用apply）

function myBind(context) {
    const fn = this;
    const arg1 = [ ...arguments ].splice(1);
    return function A() {
        const arg2 = [ ...arguments ];
        const allArgs = [ ...arg1, ...arg2 ];
        if (this instanceof A) {
            return new fn(...allArgs)
        } else {
            return fn.apply(context, allArgs)
        }
    }
}

手写一个new

function myNew(contructor) {
    if (typeof contructor !== 'function') {
        throw new TypeError('argument need to be a function')
    }
    const args = [ ...arguments ].slice(1);
    const obj = Object.create(contructor.prototype);
    const result = contructor.apply(obj, args);
    if (result && (typeof result === 'object' || typeof result === 'function')) {
        return result;
    } else {
        return obj
    }
}

手写一个instanceof

function myInstanceof(left, right) {
    let head = left;
    while(head) {
        if (head.contructor.prototype === right.prototype) {
            return true;
        }
        head = Object.getPrototypeOf(left);
    }
    return false
}

利用函数科里化，实现一个累加函数

function carry(fn) {
    const arr = [];
    function fun() {
        arr.push(...[ ...arguments ]);
        return fun;
    }
    fun.toString = function() {
        return fn(...arr);
    }
    fun.valueOf = function() {
        return fn(...arr);
    }
    return fun;
}

function add() {
    return [ ...arguments ].reduce((a, b) => a + b)
}

const lazyAdd = carry(add);

console.log(`${lazyAdd(1, 2, 3)(4, 5, 6)}`)

实现一个节流函数

类似英雄技能冷却，成功执行后重置冷却时间
否则等待冷却，什么都不执行

function throttle(fn, time) {
	let preTime = Date.now();
    return function() {
        if (Date.now() - preTime < time) return;
        fn.apply(this, arguments);
        preTime = Date.now();
    }
}

实现一个防抖函数

使用定时器规定一个执行死区，在死区期间执行函数将会杀死现有定时器并导致重新计时
只有安全度过死区时间，才会顺利执行函数

function throttle(fun, time) {
    let timer = null;
    return function() {
        const _this_ = this;

        if (timer) {
            clearTimeout(timer);
            timer = null;
        }

        timer = setTimeout(() => {
            fun.apply(_this_, arguments)
        }, time)
    }
}

多维数组扁平化

function flattenArray(arr) {
    const res = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] instanceof Array) {
            res.push(...flattenArray(arr[i]))
        } else {
            res.push(arr[i])
        }
    }
    return res;
}

数组去重

//使用set
function uniqueArrBySet(arr) {
    return [ ...new Set(arr) ];
}

// 使用map
function uniqueArrByMap(arr) {
    const map = new Map();
    arr.forEach(item => {
        map.set(item, 1)
    })
    return [ ...map.keys() ]
}

// 使用过滤器和索引
function uniqueArrByFilter(arr) {
    return arr.filters((item, index) => {
        return index === arr.indexOf(item)
    })
}

// 使用对象键值对，本质上还是用filter来过滤
function uniqueArrByKeyValue(arr) {
    const seen = {};
    return arr.filters(item => {
        if (seen[item]) return false;
        seen[item] = 1;
        return true;
    })
}

// 使用reduce
function uniqueArrByReduce(arr) {
    return arr.reduce((acc, item) => {
        if (!arr.includes(item)) {
            acc.push(item)
        }
        return arr;
    }, [])
}

冒泡排序

1. 第一次冒：找出最大的
2. 第二次冒：找出第二大的
3. 第三次冒：找出第三大的
   …

function sortByBub(arr) {
    const length = arr.length;
    for(let i = 0; i < length - 1; i++) {
        for(let j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

快速排序

1. 从数组正中间选一个基准
2. 遍历数组，比基准小的放左边，比基准大的放右边
3. 分别再对左边和右边执行上述操作

function quickSort(arr) {
    if (arr.length <= 0) return arr;

    let centerIndex = Math.floor(arr.length / 2)
    let center = arr[centerIndex];

    const left = [];
    const right = [];

    for(let i = 0; i < arr.length; i++) {
        if (i === centerIndex) continue;
        if (arr[i] < center) {
            left.push(arr[i])
        } else {
            right.push(arr[i])
        }
    }

    return [ ...quickSort(left), center, ...quickSort(right) ]
}

归并排序

分裂阶段：

1. 将一个数组从中间一分为二
2. 然后分别对左右两个部分，再次分别一分为二
3. 递归执行上述步骤，直到左右两边的数组均只有一个元素

合并阶段：

1. 对于两组分裂后的数组，我们称为left、right
2. 准备一个新数组arr，从left[0]和right[0]中选取最小的push进arr中，对于选种的元素需要将其从数组中shift出来
3. 直到left和right两个数组全部清空
4. 这个时候得到的arr就是left和right归并后排好序的结果
5. 递归执行上述步骤

function mergeSort(arr) {
    if (arr.length <= 0) return arr;

    const center = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, center));
    const right = mergeSort(arr.slice(center));

    return merge(left, right);
}

function merge(left, right){
    const result = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        } else{
            result.push(right.shift());
        }
    }
    while(left.length)
        result.push(left.shift());
    while(right.length)
        result.push(right.shift());
    return result;
}

插入排序

1. 取出第二个元素，从右向左对比，直到放在第一个比他小的元素前面
2. 取出第三个元素，从右向左对比，直到放在第一个比他小的元素前面
3. 取出第四个元素，从右向左对比，直到放在第一个比他小的元素前面
4. …..

function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {
        let cur = arr[i];
        let j = i - 1;
        while(j >= 0 && arr[j] > cur) {
            // 一开始的arr[j + 1]就是arr[i]，arr[i]已经赋值给cur进行保存，相当于被从数组中“抽出来”了
            // 因此这个地方可以放心将arr[j + 1]（也就是arr[i]）进行覆盖
            arr[j + 1] = arr[j]; // 向右移动元素
            j--;
        }
        arr[j + 1] = cur
    }
    return arr;
}

选择排序

1. 第一轮循环从0开始，向右寻找最小的数，找到后与0位置的元素交换
2. 第二轮循环从1开始，向右寻找第二小的数，找到后与1位置的元素交换
3. 第二轮循环从2开始，向右寻找第三小的数，找到后与2位置的元素交换
4. …

function selectSort(arr) {
    const length = arr.length;
    for(let i = 0; i < length; i++) {
        let min = i;
        for(let j = i + 1; j < length; j++) {
            if (arr[j] < arr[min]) min = j;
        }
        [arr[i], arr[min]] = [arr[min], arr[i]];
    }
    return arr;
}