大廠高頻手撕算法題

目前互聯(lián)網(wǎng)行業(yè)目前正在處于內(nèi)卷狀態(tài)，各個大廠不斷提高招人門檻，前端工程師找工作也越發(fā)艱難，為了助力各位老鐵能夠在面試過程中脫穎而出，我結(jié)合自己的面試經(jīng)驗，準備了這三十六道面試過程中的手撕算法題，與各位共享。

一、冒泡排序

冒泡排序的思路：遍歷數(shù)組，然后將最大數(shù)沉到最底部；
時間復(fù)雜度：O(N^2)；
空間復(fù)雜度：O(1)

function BubbleSort(arr) {
    if(arr == null || arr.length <= 0){
        return [];
    }
    var len = arr.length;
    for(var end = len - 1; end > 0; end--){
        for(var i = 0; i < end; i++) {
            if(arr[i] > arr[i + 1]){
                swap(arr, i, i + 1);
            }
        }
    }
    return arr;
}
function swap(arr, i, j){
    // var temp = arr[i];
    // arr[i] = arr[j];
    // arr[j] = temp;
    //交換也可以用異或運算符
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

二、選擇排序

選擇排序的實現(xiàn)思路：遍歷數(shù)組，把最小數(shù)放在頭部；
時間復(fù)雜度：O(N^2)；
空間復(fù)雜度：O(1)

function SelectionSort(arr) {
    if(arr == null || arr.length < 0) {
        return [];
    }
    for(var i = 0; i < arr.length - 1; i++) {
        var minIndex = i;
        for(var j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
    return arr;
}

function swap(arr, i, j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

三、插入排序

插入排序?qū)崿F(xiàn)思路：將一個新的數(shù)，和前面的比較，只要當前數(shù)小于前一個則和前一個交換位置，否則終止；
時間復(fù)雜度：O(N^2)；
空間復(fù)雜度：O(1)

function insertSort(arr) {
    if(arr == null  || arr.length <= 0){
        return [];
    }
    var len = arr.length;
    for(var i = 1; i < len; i++) {
        for(var j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
    return arr;
}

function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

四、歸并排序

歸并排序的思路：
1.先左側(cè)部分排好序
2.再右側(cè)部分排好序
3.再準備一個輔助數(shù)組，用外排的方式，小的開始填，直到有個動到末尾，將另一個數(shù)組剩余部分拷貝到末尾
4.再將輔助數(shù)組拷貝回原數(shù)組
時間復(fù)雜度:O(N * logN)
空間復(fù)雜度:O(N)

// 遞歸實現(xiàn)

function mergeSort(arr){
    if(arr == null  || arr.length <= 0){
        return [];
    }
    sortProcess(arr, 0, arr.length - 1);
    return arr;
}

function sortProcess(arr, L, R){
    //遞歸的終止條件，就是左右邊界索引一樣
    if(L == R){
        return;
    }
    var middle = L + ((R - L) >> 1);//找出中間值
    sortProcess(arr, L, middle);//對左側(cè)部分進行遞歸
    sortProcess(arr, middle + 1, R);//對右側(cè)部分進行遞歸
    merge(arr, L, middle, R);//然后利用外排方式進行結(jié)合
}

function merge(arr, L, middle, R){
    var help = [];
    var l = L;
    var r = middle + 1;
    var index = 0;
    //利用外排方式進行
    while(l <= middle && r <= R){
        help[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
    }
    while(l <= middle){
        help.push(arr[l++]);
    }
    while(r <= R){
        help.push(arr[r++]);
    }

    for(var i = 0; i < help.length; i++) {
        arr[L + i] = help[i];
    }
    //arr.splice(L, help.length, ...help);//這個利用了ES6的語法
}

// 循環(huán)實現(xiàn)

function mergeSort(arr){
    if(arr ==null || arr.length <= 0){
        return [];
    }
    var len = arr.length;
    //i每次乘2，是因為每次合并以后小組元素就變成兩倍個了
    for(var i = 1; i < len; i *= 2){
        var index = 0;//第一組的起始索引
        while( 2 * i  + index <= len){
            index += 2 * i;
            merge(arr, index - 2 * i, index - i, index);
        }
        //說明剩余兩個小組，但其中一個小組數(shù)據(jù)的數(shù)量已經(jīng)不足2的冪次方個
        if(index + i < len){
            merge(arr, index, index + i, len);
        }
    }
    return arr;
}

//利用外排的方式進行結(jié)合
function merge(arr, start, mid, end){
    //新建一個輔助數(shù)組
    var help = [];
    var l = start, r = mid;
    var i = 0;
    while(l < mid && r < end){
        help[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
    }
    while(l < mid){
        help[i++] = arr[l++];
    }
    while(r < end){
        help[i++] = arr[r++];
    }
    for(var j = 0; j < help.length; j++){
        arr[start + j] = help[j];
    }
}

五、快速排序

快速排序?qū)崿F(xiàn)思路：隨機取出一個值進行劃分，大于該值放右邊，小于該值放左邊（該算法在經(jīng)典快排的基礎(chǔ)上經(jīng)過荷蘭國旗思想和隨機思想進行了改造）
時間復(fù)雜度：O(N*logN)?
空間復(fù)雜度：O(logN)

function quickSort(arr) {
    if(arr == null || arr.length <= 0){
        return [];
    }
    quick(arr, 0, arr.length - 1);
}

function quick(arr, L, R){
    //遞歸結(jié)束條件是L >= R
    if(L < R){
        //隨機找一個值，然后和最后一個值進行交換，將經(jīng)典排序變?yōu)榭焖倥判?br>        swap(arr, L + Math.floor(Math.random() * (R - L + 1)), R);
        //利用荷蘭國旗問題獲得劃分的邊界，返回的值是小于區(qū)域的最大索引和大于區(qū)域的最小索引，在這利用荷蘭國旗問題將等于區(qū)域部分就不用動了
        var tempArr = partition(arr, L, R, arr[R]);
        quick(arr, L, tempArr[0]);
        quick(arr, tempArr[1], R);
    }
}
//返回值是小于區(qū)域最后的索引和大于區(qū)域的第一個索引
function partition(arr, L, R, num){
    var less = L - 1;
    var more = R + 1;
    var cur = L;
    while(cur < more){
        if(arr[cur] < num){
            swap(arr, ++less, cur++);
        }else if(arr[cur] > num) {
            swap(arr, --more, cur);
        }else{
            cur++;
        }
    }
    return [less, more];
}
function swap(arr, i, j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

六、堆排序

堆排序思路：
1.讓數(shù)組變成大根堆
2.把最后一個位置和堆頂做交換
3.則最大值在最后，則剩下部分做heapify，則重新調(diào)整為大根堆，則堆頂位置和該部分最后位置做交換
4.重復(fù)進行，直到減完，則這樣最后就調(diào)整完畢，整個數(shù)組排完序（為一個升序）
時間復(fù)雜度:O(N * logN)
空間復(fù)雜度:O(1)

function heapSort(arr) {
    if(arr == null || arr.length <= 0) {
        return [];
    }

    //首先是建立大頂堆的過程
    for(var i = 0; i < arr.length; i++) {
        heapInsert(arr, i);
    }
    var size = arr.length;//這個值用來指定多少個數(shù)組成堆，當?shù)玫揭粋€排序的值后這個值減一
    //將堆頂和最后一個位置交換
    /**
     * 當大頂堆建立完成后，然后不斷將最后一個位置和堆頂交換；
     * 這樣最大值就到了最后，則剩下部分做heapify，重新調(diào)整為大根堆，則堆頂位置和倒數(shù)第二個位置交換，重復(fù)進行，直到全部排序完畢*/
    //由于前面已經(jīng)是大頂堆，所以直接交換
    swap(arr, 0, --size);
    while(size > 0) {
        //重新變成大頂堆
        heapify(arr, 0, size);
        //進行交換
        swap(arr, 0, --size);
    }
}

//加堆過程中
function heapInsert(arr, index) {
    //比較當前位置和其父位置，若大于其父位置，則進行交換，并將索引移動到其父位置進行循環(huán)，否則跳過
    //結(jié)束條件是比父位置小或者到達根節(jié)點處
    while(arr[index] > arr[parseInt((index - 1) / 2)]){
        //進行交換
        swap(arr, index, parseInt((index - 1) / 2));
        index = parseInt((index - 1) / 2);
    }
}
//減堆過程
/**
 * size指的是這個數(shù)組前多少個數(shù)構(gòu)成一個堆
 * 如果你想把堆頂彈出，則把堆頂和最后一個數(shù)交換，把size減1，然后從0位置經(jīng)歷一次heapify，調(diào)整一下，剩余部分變成大頂堆*/
function heapify(arr, index, size) {
    var left = 2 * index + 1;
    while(left < size) {
        var largest = (left + 1 < size && arr[left] < arr[left + 1]) ? left + 1 : left;
        largest = arr[index] > arr[largest] ? index : largest;

        //如果最大值索引和傳進來索引一樣，則該值到達指定位置，直接結(jié)束循環(huán)
        if(index == largest) {
            break;
        }

        //進行交換，并改變索引和其左子節(jié)點
        swap(arr, index, largest);
        index = largest;
        left = 2 * index + 1;
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

七、桶排序

桶排序會經(jīng)歷三次遍歷：準備一個數(shù)組、遍歷一遍數(shù)組、重構(gòu)一遍數(shù)組，是非基于比較的排序，下面以一個問題來闡述其思路。
問題：
給定一個數(shù)組，求如果排序之后，相鄰兩個數(shù)的最大差值，要求時間復(fù)雜度O(N),且要求不能用基于比較的排序
思路：
1.準備桶：數(shù)組中有N個數(shù)就準備N+1個桶
2.遍歷一遍數(shù)組，找到最大值max和最小值min 。若min = max，則差值=0；若min≠max，則最小值放在0號桶，最大值放在N號桶，剩下的數(shù)屬于哪個范圍就進哪個桶
3.根據(jù)鴿籠原理，則肯定有一個桶為空桶，設(shè)計該桶的目的是為了否定最大值在一個桶中，則最大差值的兩個數(shù)一定來自于兩個桶，但空桶兩側(cè)并不一定是最大值
4.所以只記錄所有進入該桶的最小值min和最大值max和一個布爾值表示該桶有沒有值
5.然后遍歷這個數(shù)組，如果桶是空的，則跳到下一個數(shù)，如果桶非空，則找前一個非空桶，則最大差值=當前桶min - 上一個非空桶max，用全局變量更新最大值
時間復(fù)雜度：O(N)
空間復(fù)雜度：O(N)

function maxGap(arr) {
    if(arr == null || arr.length <= 0) {
        return 0;
    }
    var len = arr.length;
    var max = -Infinity, min = Infinity;
    //遍歷一遍數(shù)組,找到最大值max和最小值min
    for(var i = 0; i < len; i++) {
        max = max > arr[i] ? max : arr[i];
        min = min > arr[i] ? arr[i] : min;
    }

    //若min = max,則差值為0;
    if(min == max) {
        return 0;
    }

    var hasNum = new Array(len + 1);
    var mins = new Array(len + 1);
    var maxs = new Array(len + 1);

    var bid = 0;//指定桶的編號

    for(var i = 0; i < len; i++) {
        bid = bucket(arr[i], min, max, len);//獲得該值是在哪個桶//由于有N+1個桶，所以間隔就是N個，所以此處除以的是len，然后通過這個函數(shù)得到應(yīng)該放到哪個桶里
        maxs[bid] = hasNum[bid] ? Math.max(arr[i], maxs[bid]) : arr[i];
        mins[bid] = hasNum[bid] ? Math.min(arr[i], mins[bid]) : arr[i];
        hasNum[bid] = true;
    }

    var res = 0;
    var lastMax = maxs[0];

    for(var i = 0; i < len + 1; i++) {
        if(hasNum[i]) {
            res = Math.max(mins[i] - lastMax, res);
            lastMax = maxs[i];
        }
    }
    return res;
}

//獲得桶號
//這個函數(shù)用于判斷在哪個桶中，參數(shù)分別為值、最小值、最大值、桶間隔
function bucket(value, min, max, len) {
    return parseInt((value - min) / ((max - min) / len));
}

八、new

function New (Fn, ...arg) {
    // 一個新的對象被創(chuàng)建
    const result = {};
    // 該對象的__proto__屬性指向該構(gòu)造函數(shù)的原型
    if (Fn.prototype !== null) {
        Object.setPrototypeOf(result, Fn.prototype);
    }
    // 將執(zhí)行上下文（this）綁定到新創(chuàng)建的對象中
    const returnResult = Fn.apply(result, arg);
    // 如果構(gòu)造函數(shù)有返回值，那么這個返回值將取代第一步中新創(chuàng)建的對象。否則返回該對象
    if ((typeof returnResult === "object" || typeof returnResult === "function") && returnResult !== null) {
        return returnResult;
    }
    return result;
}

九、instanceof

function Instanceof(left, right) {
    let leftVal = Object.getPrototypeOf(left);
    const rightVal = right.prototype;

    while (leftVal !== null) {
        if (leftVal === rightVal)
            return true;
        leftVal = Object.getPrototypeOf(leftVal);
    }
    return false;
}

十、 Object.create()

Object.ObjectCreate = (proto, propertiesObject)=> {
    // 對輸入進行檢測
    if (typeof proto !== 'object' && typeof proto !== 'function' && proto !== null) {
        throw new Error(`Object prototype may only be an Object or null:${proto}`);
    }
    // 新建一個對象
    const result = {};
    // 將該對象的原型設(shè)置為proto
    Object.setPrototypeOf(result, proto);
    // 將屬性賦值給該對象
    Object.defineProperties(result, propertiesObject);
    // 返回該對象
    return result;
}

十一、 Object assign()

function ObjectAssign(target, ...sources) {
    // 對第一個參數(shù)的判斷，不能為undefined和null
    if (target === undefined || target === null) {
        throw new TypeError('cannot convert first argument to object');
    }

    // 將第一個參數(shù)轉(zhuǎn)換為對象(不是對象轉(zhuǎn)換為對象)
    const targetObj = Object(target);
    // 將源對象(source)自身的所有可枚舉屬性復(fù)制到目標對象（target）
    for (let i = 0; i < sources.length; i++) {
        let source = sources[i];
        // 對于undefined和null在源角色中不會報錯，會直接跳過
        if (source !== undefined && source !== null) {
            // 將源角色轉(zhuǎn)換成對象
            // 需要將源角色自身的可枚舉屬性（包含Symbol值的屬性）進行復(fù)制
            // Reflect.ownKeys(obj)  返回一個數(shù)組，包含對象自身的所有屬性，不管屬性名是Symbol還是字符串，也不管是否可枚舉
            const keysArray = Reflect.ownKeys(Object(source));
            for (let nextIndex = 0; nextIndex < keysArray.length; nextIndex ++) {
                const nextKey = keysArray[nextIndex];
                // 去除不可枚舉屬性
                const desc = Object.getOwnPropertyDescriptor(source, nextKey);
                if (desc !== undefined && desc.enumerable) {
                    // 后面的屬性會覆蓋前面的屬性
                    targetObj[nextKey] = source[nextKey];
                }
            }
        }
    }

    return targetObj;
}
// 由于掛載到Object的assign是不可枚舉的,直接掛載上去是可枚舉的，所以采用這種方式
if (typeof Object.myAssign !== 'function') {
    Object.defineProperty(Object, "myAssign", {
        value : ObjectAssign,
        writable: true,
        enumerable: false,
        configurable: true
    });
}

十二、 map

Array.prototype.myMap = function(fn) {
    // 判斷輸入的第一個參數(shù)是不是函數(shù)
    if (typeof fn !== 'function') {
        throw new TypeError(fn + 'is not a function');
    }

    // 獲取需要處理的數(shù)組內(nèi)容
    const arr = this;
    const len = arr.length;
    // 新建一個空數(shù)組用于裝載新的內(nèi)容
    const temp = new Array(len);

    // 對數(shù)組中每個值進行處理
    for (let i = 0; i < len; i++) {
        // 獲取第二個參數(shù)，改變this指向
        let result = fn.call(arguments[1], arr[i], i, arr);
        temp[i] = result;
    }
    // 返回新的結(jié)果
    return temp;
}

十三、 filter

Array.prototype.myFilter = function (fn) {
    if (typeof fn !== 'function') {
        throw new TypeError(`${fn} is not a function`);
    }

    // 獲取該數(shù)組
    const arr = this;
    // 獲取該數(shù)組長度
    const len = this.length >>> 0;
    // 新建一個新的數(shù)組用于放置該內(nèi)容
    const temp = [];

    // 對數(shù)組中每個值進行處理
    for (let i = 0; i < len; i++) {
        // 處理時注意this指向
        const result = fn.call(arguments[1], arr[i], i, arr);
        result && temp.push(arr[i]);
    }

    return temp;
}

十四、 reduce

Array.prototype.myReduce = function(fn) {
    if (typeof fn !== 'function') {
        throw new TypeError(`${fn} is not a function`);
    }

    const arr = this;
    const len = arr.length >>> 0;
    let value;// 最終返回的值
    let k = 0;// 當前索引

    if (arguments.length >= 2) {
        value = arguments[1];
    } else {
        // 當數(shù)組為稀疏數(shù)組時，判斷數(shù)組當前是否有元素，如果沒有索引加一
        while (k < len && !( k in arr)) {
            k++;
        }
        // 如果數(shù)組為空且初始值不存在則報錯
        if (k >= len) {
            throw new TypeError('Reduce of empty array with no initial value');
        }
        value = arr[k++];
    }
    while (k < len) {
        if (k in arr) {
            value = fn(value, arr[k], k, arr);
        }
        k++;
    }

    return value;
}

十五、 flat

// 使用reduce和concat
Array.prototype.flat1 = function () {
    return this.reduce((acc, val) => acc.concat(val), []);
}

// 使用reduce + concat + isArray +recursivity
Array.prototype.flat2 = function (deep = 1) {
    const flatDeep = (arr, deep = 1) => {
        // return arr.reduce((acc, val) => Array.isArray(val) && deep > 0 ? [...acc, ...flatDeep(val, deep - 1)] : [...acc, val], []);
        return deep > 0 ? arr.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatDeep(val, deep - 1) : val), []) : arr.slice();
    }

    return flatDeep(this, deep);
}

// 使用forEach + concat + isArray +recursivity
// forEach 遍歷數(shù)組會自動跳過空元素
Array.prototype.flat3 = function (deep = 1) {
    const result = [];
    (function flat(arr, deep) {
        arr.forEach((item) => {
            if (Array.isArray(item) && deep > 0) {
                flat(item, deep - 1);
            } else {
                result.push(item);
            }
        })
    })(this, deep);

    return result;
}

// 使用for of + concat + isArray +recursivity
// for of 遍歷數(shù)組會自動跳過空元素
Array.prototype.flat4 = function (deep = 1) {
    const result = [];
    (function flat(arr, deep) {
        for(let item of arr) {
            if (Array.isArray(item) && deep > 0) {
                flat(item, deep - 1);
            } else {
                // 去除空元素，因為void 表達式返回的都是undefined，不適用undefined是因為undefined在局部變量會被重寫
                item !== void 0 && result.push(item);
            }
        }
    })(this, deep);

    return result;
}

// 使用堆棧stack
Array.prototype.flat5 = function(deep = 1) {
    const stack = [...this];
    const result = [];
    while (stack.length > 0) {
        const next = stack.pop();
        if (Array.isArray(next)) {
            stack.push(...next);
        } else {
            result.push(next);
        }
    }

    // 反轉(zhuǎn)恢復(fù)原來順序
    return result.reverse();
}

十六、 call

Function.prototype.call1 = function(context, ...args) {
    // 獲取第一個參數(shù)（注意第一個參數(shù)為null或undefined是，this指向window），構(gòu)建對象
    context = context ? Object(context) : window;
    // 將對應(yīng)函數(shù)傳入該對象中
    context.fn = this;
    // 獲取參數(shù)并執(zhí)行相應(yīng)函數(shù)
    let result = context.fn(...args);
    delete context.fn;
    

十七、 apply

Function.prototype.apply1 = function(context, arr) {
    context = context ? Object(context) : window;
    context.fn = this;

    let result = arr ? context.fn(...arr) : context.fn();

    delete context.fn;

    return result;
}

十八、 bind

Function.prototype.bind1 = function (context, ...args) {
    if (typeof this !== 'function') {
        throw new TypeError('The bound object needs to be a function');
    }

    const self = this;
    const fNOP = function() {};
    const fBound = function(...fBoundArgs) {
        // 指定this
        // 當作為構(gòu)造函數(shù)時，this 指向?qū)嵗藭r this instanceof fBound 結(jié)果為 true
        return self.apply(this instanceof fNOP ? this : context, [...args, ...fBoundArgs]);
    }

    //  修改返回函數(shù)的 prototype 為綁定函數(shù)的 prototype,為了避免直接修改this的原型，所以新建了一個fNOP函數(shù)作為中介
    if (this.prototype) {
        fNOP.prototype = this.prototype;
    }
    fBound.prototype = new fNOP();

    return fBound;
}

十九、 防抖

function debounce(fn, wait, immediate) {
    let timer = null;
    return function(...args) {
        // 立即執(zhí)行的功能(timer為空表示首次觸發(fā))
        if (immediate && !timer) {
            fn.apply(this, args);
        }
        // 有新的觸發(fā)，則把定時器清空
        timer && clearTimeout(timer);
        // 重新計時
        timer = setTimeout(() => {
            fn.apply(this, args);
        }, wait)
    }
}

二十、 節(jié)流

// 時間戳版本
function throttle(fn, wait) {
    // 上一次執(zhí)行時間
    let previous = 0;
    return function(...args) {
        // 當前時間
        let now = +new Date();
        if (now - previous > wait) {
            previous = now;
            fn.apply(this, args);
        }
    }
}

// 定時器版本
function throttle(fn, wait) {
    let timer = null;
    return function(...args) {
        if (!timer) {
            timer = setTimeout(() => {
                fn.apply(this, args);
                timer = null;
            }, wait)
        }
    }
}

二十一、深拷貝

// 乞巧版
function cloneDeep1(source) {
    return JSON.parse(JSON.stringify(source));
}

// 遞歸版
function cloneDeep2(source) {
    // 如果輸入的為基本類型，直接返回
    if (!(typeof source === 'object' && source !== null)) {
        return source;
    }

    // 判斷輸入的為數(shù)組函數(shù)對象，進行相應(yīng)的構(gòu)建
    const target = Array.isArray(source) ? [] : {};

    for (let key in source) {
        // 判斷是否是自身屬性
        if (Object.prototype.hasOwnProperty.call(source, key)) {
            if (typeof source === 'object' && source !== null) {
                target[key] = cloneDeep2(source[key]);
            } else {
                target[key] = source[key];
            }
        }
    }

    return target;
}

// 循環(huán)方式
function cloneDeep3(source) {
    if (!(typeof source === 'object' && source !== null)) {
        return source;
    }

    const root = Array.isArray(source) ? [] : {};
    // 定義一個棧
    const loopList = [{
        parent: root,
        key: undefined,
        data: source,
    }];

    while (loopList.length > 0) {
        // 深度優(yōu)先
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;

        // 初始化賦值目標，key為undefined則拷貝到父元素，否則拷貝到子元素
        let res = parent;
        if (typeof key !== 'undefined') {
            res = parent[key] = Array.isArray(data) ? [] : {};
        }

        for (let key in data) {
            if (data.hasOwnProperty(key)) {
                if (typeof data[key] === 'object' && data !== null) {
                    loopList.push({
                        parent: res,
                        key: key,
                        data: data[key],
                    });
                } else {
                    res[key] = data[key];
                }
            }
        }
    }

    return root;
}

二十二、 根據(jù)Promise/A+規(guī)范實現(xiàn)Promise

人家有相關(guān)標準，我們就要遵守，畢竟遵紀守法才是好公民，現(xiàn)在只能硬著頭皮把這個標準過一遍。

下面就是基于Promise/A+規(guī)范實現(xiàn)的代碼，已經(jīng)經(jīng)過promises-aplus-tests庫進行了驗證。

const PENDING = 'pending';
const FULFILLED = 'fulfilled';
const REJECTED = 'rejected';
/**
 * Promise構(gòu)造函數(shù)
 * excutor: 內(nèi)部同步執(zhí)行的函數(shù)
 */
class Promise {
    constructor(excutor) {
        const self = this;
        self.status = PENDING;
        self.onFulfilled = [];// 成功的回調(diào)
        self.onRejected = [];// 失敗的回調(diào)

        // 異步處理成功調(diào)用的函數(shù)
        // PromiseA+ 2.1 狀態(tài)只能由Pending轉(zhuǎn)為fulfilled或rejected；fulfilled狀態(tài)必須有一個value值；rejected狀態(tài)必須有一個reason值。
        function resolve(value) {
            if (self.status === PENDING) {
                self.status = FULFILLED;
                self.value = value;
                 // PromiseA+ 2.2.6.1 相同promise的then可以被調(diào)用多次，當promise變?yōu)閒ulfilled狀態(tài)，全部的onFulfilled回調(diào)按照原始調(diào)用then的順序執(zhí)行
                self.onFulfilled.forEach(fn => fn());
            }
        }

        function reject(reason) {
            if (self.status === PENDING) {
                self.status = REJECTED;
                self.reason = reason;
                // PromiseA+ 2.2.6.2 相同promise的then可以被調(diào)用多次，當promise變?yōu)閞ejected狀態(tài)，全部的onRejected回調(diào)按照原始調(diào)用then的順序執(zhí)行
                self.onRejected.forEach(fn => fn());
            }
        }

        try {
            excutor(resolve, reject);
        } catch (e) {
            reject(e);
        }
    }

    then(onFulfilled, onRejected) {
        // PromiseA+ 2.2.1 onFulfilled和onRejected是可選參數(shù)
        // PromiseA+ 2.2.5 onFulfilled和onRejected必須被作為函數(shù)調(diào)用
        // PromiseA+ 2.2.7.3 如果onFulfilled不是函數(shù)且promise1狀態(tài)是fulfilled，則promise2有相同的值且也是fulfilled狀態(tài)
        // PromiseA+ 2.2.7.4 如果onRejected不是函數(shù)且promise1狀態(tài)是rejected，則promise2有相同的值且也是rejected狀態(tài)
        onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : value => value;
        onRejected = typeof onRejected === 'function' ? onRejected : reason => { throw reason };

        const self = this;
        const promise = new Promise((resolve, reject) => {
            const handle = (callback, data) => {
                // PromiseA+ 2.2.4 onFulfilled或者onRejected需要在自己的執(zhí)行上下文棧里被調(diào)用，所以此處用setTimeout
                setTimeout(() => {
                    try {
                         // PromiseA+ 2.2.2 如果onFulfilled是函數(shù)，則在fulfilled狀態(tài)之后調(diào)用，第一個參數(shù)為value
                        // PromiseA+ 2.2.3 如果onRejected是函數(shù)，則在rejected狀態(tài)之后調(diào)用，第一個參數(shù)為reason
                        const x = callback(data);
                        // PromiseA+ 2.2.7.1 如果onFulfilled或onRejected返回一個x值，運行這[[Resolve]](promise2, x)
                        resolvePromise(promise, x, resolve, reject);
                    } catch (e) {
                        // PromiseA+ 2.2.7.2 onFulfilled或onRejected拋出一個異常e，promise2必須以e的理由失敗
                        reject(e);
                    }
                })
            }
            if (self.status === PENDING) {
                self.onFulfilled.push(() => {
                    handle(onFulfilled, self.value);
                });

                self.onRejected.push(() => {
                    handle(onRejected, self.reason);
                })
            } else if (self.status === FULFILLED) {
                setTimeout(() => {
                    handle(onFulfilled, self.value);
                })
            } else if (self.status === REJECTED) {
                setTimeout(() => {
                    handle(onRejected, self.reason);
                })
            }
        })

        return promise;
    }
}

function resolvePromise(promise, x, resolve, reject) {
    // PromiseA+ 2.3.1 如果promise和x引用同一對象，會以TypeError錯誤reject promise
    if (promise === x) {
        reject(new TypeError('Chaining Cycle'));
    }

    if (x && typeof x === 'object' || typeof x === 'function') {
        // PromiseA+ 2.3.3.3.3 如果resolvePromise和rejectPromise都被調(diào)用，或者對同一個參數(shù)進行多次調(diào)用，那么第一次調(diào)用優(yōu)先，以后的調(diào)用都會被忽略。
        let used;
        try {
            // PromiseA+ 2.3.3.1 let then be x.then
            // PromiseA+ 2.3.2 調(diào)用then方法已經(jīng)包含了該條（該條是x是promise的處理）。
            let then = x.then;

            if (typeof then === 'function') {
                // PromiseA+ 2.3.3.3如果then是一個函數(shù)，用x作為this調(diào)用它。第一個參數(shù)是resolvePromise，第二個參數(shù)是rejectPromise
                // PromiseA+ 2.3.3.3.1 如果resolvePromise用一個值y調(diào)用，運行[[Resolve]](promise, y)
                // PromiseA+ 2.3.3.3.2 如果rejectPromise用一個原因r調(diào)用，用r拒絕promise。
                then.call(x, (y) => {
                    if (used) return;
                    used = true;
                    resolvePromise(promise, y, resolve, reject)
                }, (r) => {
                    if (used) return;
                    used = true;
                    reject(r);
                })
            } else {
                // PromiseA+ 如果then不是一個函數(shù)，變?yōu)閒ulfilled狀態(tài)并傳值為x
                if (used) return;
                used = true;
                resolve(x);
            }
        } catch (e) {
            // PromiseA+ 2.3.3.2 如果檢索屬性x.then拋出異常e，則以e為原因拒絕promise
            // PromiseA+ 2.3.3.4 如果調(diào)用then拋出異常，但是resolvePromise或rejectPromise已經(jīng)執(zhí)行，則忽略它
            if (used) return;
            used = true;
            reject(e);
        }

    } else {
        // PromiseA+ 2.3.4 如果x不是一個對象或函數(shù)，狀態(tài)變?yōu)閒ulfilled并傳值x
        resolve(x);
    }
}

二十三、 Promise.resolve()

class Promise {
    // ...
    // 將現(xiàn)有對象轉(zhuǎn)為 Promise 對象
    static resolve(value) {
        // 如果參數(shù)是 Promise 實例，那么Promise.resolve將不做任何修改、原封不動地返回這個實例。
        if (value instanceof Promise) return value;

        // 參數(shù)是一個thenable對象（具有then方法的對象）,Promise.resolve方法會將這個對象轉(zhuǎn)為 Promise 對象，然后就立即執(zhí)行thenable對象的then方法。
        if (typeof value === 'object' || typeof value === 'function') {
            try {
                let then = value.then;
                if (typeof then === 'function') {
                    return new Promise(then.bind(value));
                }
            } catch (e) {
                return new Promise((resolve, reject) => {
                    reject(e);
                })
            }
        }

        // 參數(shù)不是具有then方法的對象，或根本就不是對象,Promise.resolve方法返回一個新的 Promise 對象，狀態(tài)為resolved。
        return new Promise((resolve, reject) => {
            resolve(value);
        })
    }
}

二十四、 Promise.reject()

class Promise {
    // ...
    // 返回一個新的 Promise 實例，該實例的狀態(tài)為rejected。
    static reject(reason) {
        return new Promise((resolve, reject) => {
            reject(reason);
        })
    }
}

二十五、 Promise.all()

class Promise {
    // ...
    // 用于將多個 Promise 實例，包裝成一個新的 Promise 實例。只有所有狀態(tài)都變?yōu)閒ulfilled，p的狀態(tài)才會是fulfilled
    static all(promises) {
        const values = [];
        let resolvedCount = 0;
        return new Promise((resolve, reject) => {
            promises.forEach((p, index) => {
                Promise.resolve(p).then(value => {
                    resolvedCount++;
                    values[index] = value;
                    if (resolvedCount === promises.length) {
                        resolve(values);
                    }
                }, reason => {
                    reject(reason);
                })
            })
        })
    }
}

二十六、 Promise.race()

class Promise {
    // ...
     // 只要有一個實例率先改變狀態(tài)，狀態(tài)就跟著改變。那個率先改變的 Promise 實例的返回值，就傳遞給回調(diào)函數(shù)。
    static race(promises) {
        return new Promise((resolve, reject) => {
            promises.forEach((p, index) => {
                Promise.resolve(p).then(value => {
                    resolve(value);
                }, reason => {
                    reject(reason);
                })
            })
        })
    }
}

二十七、 Promise.catch()

class Promise {
    // ...
    // 是.then(null, rejection)或.then(undefined, rejection)的別名，用于指定發(fā)生錯誤時的回調(diào)函數(shù)。
    catch(onRejected) {
        return this.then(undefined, onRejected);
    }
}

二十八、 Promise.finally()

class Promise {
    // ...
    // 用于指定不管 Promise 對象最后狀態(tài)如何，都會執(zhí)行的操作。
    finally(callback) {
        return this.then(
            value => Promise.resolve(callback()).then(() => value),
            reason => Promise.resolve(callback()).then(() => { throw reason })
        )
    }
}

二十九、Async實現(xiàn)原理

這是Async的實現(xiàn)原理，即將Generator函數(shù)作為參數(shù)放入run函數(shù)中，最終實現(xiàn)自動執(zhí)行并返回Promise對象。

function run(genF) {
    // 返回值是Promise
    return new Promise((resolve, reject) => {
        const gen = genF();
        function step(nextF) {
            let next;
            try {
                // 執(zhí)行該函數(shù)，獲取一個有著value和done兩個屬性的對象
                next = nextF();
            } catch (e) {
                // 出現(xiàn)異常則將該Promise變?yōu)閞ejected狀態(tài)
                reject(e);
            }

            // 判斷是否到達末尾，Generator函數(shù)到達末尾則將該Promise變?yōu)閒ulfilled狀態(tài)
            if (next.done) {
                return resolve(next.value);
            }

            // 沒到達末尾，則利用Promise封裝該value，直到執(zhí)行完畢，反復(fù)調(diào)用step函數(shù)，實現(xiàn)自動執(zhí)行
            Promise.resolve(next.value).then((v) => {
                step(() => gen.next(v))
            }, (e) => {
                step(() => gen.throw(e))
            })
        }

        step(() => gen.next(undefined));
    })
}

三十、發(fā)布訂閱模式

// 發(fā)布訂閱（TypeScript版）
interface Publish {
    registerObserver(eventType : string, subscribe : Subscribe) : void;
    remove(eventType : string, subscribe ?: Subscribe) : void;
    notifyObservers(eventType : string) : void;
}
interface SubscribesObject{
    [key : string] : Array
}
class ConcretePublish implements Publish {
    private subscribes : SubscribesObject;

    constructor() {
        this.subscribes = {};
    }

    registerObserver(eventType : string, subscribe : Subscribe) : void {
        if (!this.subscribes[eventType]) {
            this.subscribes[eventType] = [];
        }

        this.subscribes[eventType].push(subscribe);
    }

    remove(eventType : string, subscribe ?: Subscribe) : void {
        const subscribeArray = this.subscribes[eventType];
        if (subscribeArray) {
            if (!subscribe) {
                delete this.subscribes[eventType];
            } else {
                for (let i = 0; i < subscribeArray.length; i++) {
                    if (subscribe === subscribeArray[i]) {
                        subscribeArray.splice(i, 1);
                    }
                }
            }
        }
    }

    notifyObservers(eventType : string, ...args : any[]) : void {
        const subscribes = this.subscribes[eventType];
        if (subscribes) {
            subscribes.forEach(subscribe => subscribe.update(...args))
        }
    }
}

interface Subscribe {
    update(...value : any[]) : void;
}

class ConcreteSubscribe1 implements Subscribe {
    public update(...value : any[]) : void {
        console.log('已經(jīng)執(zhí)行更新操作1，值為', ...value);
    }
}
class ConcreteSubscribe2 implements Subscribe {
    public update(...value : any[]) : void {
        console.log('已經(jīng)執(zhí)行更新操作2，值為', ...value);
    }
}

function main() {
    const publish = new ConcretePublish();
    const subscribe1 = new ConcreteSubscribe1();
    const subscribe2 = new ConcreteSubscribe2();

    publish.registerObserver('1', subscribe1);
    publish.registerObserver('2', subscribe2);

    publish.notifyObservers('2', '22222');
}

main();

三十一、懶加載

1)首先，不要將圖片地址放到src屬性中，而是放到其它屬性(data-original)中。
2)頁面加載完成后，根據(jù)scrollTop判斷圖片是否在用戶的視野內(nèi)，如果在，則將data-original屬性中的值取出存放到src屬性中。
3)在滾動事件中重復(fù)判斷圖片是否進入視野，如果進入，則將data-original屬性中的值取出存放到src屬性中。
elementNode.getAttribute(name)：方法通過名稱獲取屬性的值。
elementNode.setAttribute(name, value)：方法創(chuàng)建或改變某個新屬性。
elementNode.removeAttribute(name)：方法通過名稱刪除屬性的值。

//懶加載代碼實現(xiàn)
var viewHeight = document.documentElement.clientHeight;//可視化區(qū)域的高度

function lazyload () {
    //獲取所有要進行懶加載的圖片
    let eles = document.querySelectorAll('img[data-original][lazyload]');//獲取屬性名中有data-original的
    Array.prototype.forEach.call(eles, function(item, index) {
        let rect;
        if(item.dataset.original === '') {
            return;
        }

        rect = item.getBoundingClientRect();

        //圖片一進入可視區(qū)，動態(tài)加載
        if(rect.bottom >= 0 && rect.top < viewHeight) {
            !function () {
                let img = new Image();
                img.src = item.dataset.original;
                img.onload = function () {
                    item.src = img.src;
                }
                item.removeAttribute('data-original');
                item.removeAttribute('lazyload');
            }();
        }
    })
}

lazyload();

document.addEventListener('scroll', lazyload);

三十二、FileReader使用

function uploadMulFile(uploadFile) {
    return new Promise((resolve, reject) => {
        let fileLength = 0;
        let reader = new FileReader();
        reader.readAsText(uploadFile[fileLength]);
        reader.onabort = function(e) {
            console.log("文件讀取異常");
        }
        reader.onerror = function(e) {
            console.log("文件讀取錯誤");
        }

        reader.onload = function(e){
            if(e.target.result) {

                fileLength++;
                if(fileLength < uploadFile.length) {
                    reader.readAsText(uploadFile[fileLength]);
                }else{
                    resolve({
                        carArr,
                        crossArr,
                        roadArr
                    })
                }
            }
        }
    })
}

三十三、Ajax使用（非Promise版）

function ajax(url) {
    var XHR;
    //進行性能檢測
    if(window.ActiveXObject) {
        XHR = new ActiveXObject("Microsoft.XMLHTTP");//兼容IE//IE瀏覽器中使用的請求的方法，需實例化
    }else if(window.XMLHttpRequest) {
        XHR = new XMLHttpRequest();//標準瀏覽器中的使用的請求方法，需實例化
    }else{
        XHR = null;
    }

    if(XHR) {
        XHR.onreadystatechange = function() {
            //readyState:Ajax請求服務(wù)的狀態(tài)
            if(XHR.readyState == 4) {
                //status：頁面的響應(yīng)碼
                if(XHR.status == 200) {
                    //返回的數(shù)據(jù)以string的形式返回
                    console.log(XHR.responseText);
                }
            }
        };

        XHR.open("get", url);//open(‘method’,‘url’,boolean)；參數(shù)1：請求方式；參數(shù)2：請求文件的地址；參數(shù)3：設(shè)置是否異步，true表示異步， 默認值為 true 所以可以不寫。
        XHR.send();
    }
}

三十四、Ajax使用（Promise版）

//Promise形式
function ajaxPromise(method, url, data) {
    var xhr = null;
    if(window.ActiveXObject) {
        xhr = new ActiveXObject("Microsoft.XMLHTTP");
    }else{
        xhr = new XMLHttpRequest();
    }

    return new Promise(function(resolve, reject) {
        xhr.onreadystatechange = function(){
            if(xhr.readyState === 4 ) {
                if(xhr.status === 200) {
                    resolve(JSON.parse(xhr.responseText));
                }else{
                    reject(xhr.status);
                }
            }
        };

        if(method.toUpperCase() == "GET") {
            var arr = [];
            for(var key in data) {
                arr.push(key + '=' + data[key]);
            }

            var getData = arr.join('&');
            xhr.open("GET", url + "?" + getData, true);//true表示異步
            xhr.send(null);
        }else if(method.toUpperCase() == "POST") {
            xhr.open("POST", url, true);
            xhr.responseType = "json";
            xhr.setRequestHeader('Content', 'application/x-www-form-urlencoded;charset=utf-8');
            xhr.send(data);
        }


    })
}

三十五、JsonP

function jsonp(url, onsuccess, onerror, charset) {
    var hash = Math.random().toString().slice(2);
    window['jsonp' + hash] = function(data) {
        if(onsuccess && typeof onsuccess == 'function') {
            onsuccess(data);
        }
    }

    var script = createScript(url + "?callback=jsonp" + hash, charset); // 動態(tài)產(chǎn)檢一個script標簽

    //監(jiān)聽加載成功的事件，獲取數(shù)據(jù)，這個位置用了兩個事件onload和onreadystatechange是為了兼容IE，因為IE9之前不支持onload事件，只支持onreadystatechange事件
    script.onload = script.onreadystatechange = function() {
        //若不存在readyState事件則證明不是IE瀏覽器，可以直接執(zhí)行，若是的話，必須等到狀態(tài)變?yōu)閘oaded或complete才可以執(zhí)行
        if(!this.readyState || this.readyState == 'loaded' || this.readyState == 'complete') {
            script.onload = script.onreadystatechange = null;
            // 移除該script的DOM對象
            if(script.parentNode) {
                script.parentNode.removeChild(script);
            }

            //刪除函數(shù)或變量
            window['jsonp' + hash] = null;
        }
    }

    script.onerror = function () {
        if(onerror && typeof onerror == 'function') {
            onerror();
        }
    }

    document.getElementsByTagName('head')[0].appendChild(script);//往html中增加這個標簽，目的是把請求發(fā)送出去
}

function createScript(url, charset) {
    var script = document.createElement('script');
    script.setAttribute('type', 'text/javascript');
    charset && script.setAttribute('charset', charset);
    script.setAttribute('src', url);
    script.async = true;
}

三十六、將一個字符串轉(zhuǎn)換為駝峰形式

//方式一：操作字符串數(shù)組
function transformStr2Hump1(str) {
    if(str == null) {
        return "";
    }
    var strArr = str.split('-');
    for(var i = 1; i < strArr.length; i++) {
        strArr[i] = strArr[i].charAt(0).toUpperCase() + strArr[i].substring(1);
    }
    return strArr.join('');
}

//方式二：操作字符數(shù)組
function transformStr2Hump2(str) {
    if(str == null) {
        return "";
    }
    var strArr  =str.split('');
    for(var i = 0; i < strArr.length; i++) {
        if(strArr[i] == "-"){
            //刪除-
            strArr.splice(i, 1);
            //將該處改為大寫
            if(i < strArr.length) {
                strArr[i] = strArr[i].toUpperCase();
            }
        }
    }
    return strArr.join("");
}

//方式三：利用正則
function transformStr2Hump3(str) {
    if(str == null) {
        return "";
    }
    var reg = /-(\w)/g;//匹配字母或數(shù)字或下劃線或漢字
    return str.replace(reg, function($0, $1) {
        return $1.toUpperCase();
    })
}