實(shí)現(xiàn) trim

String.prototype.trim = function() {
    return this.replace(/^\s\s*/, '').replace(/\s\s*$/, '');
}

斐波那契數(shù)列

斐波那契數(shù)拳亿，通常用 F(n) 表示嚎朽，形成的序列稱(chēng)為斐波那契數(shù)列位他。該數(shù)列由 0 和 1 開(kāi)始吧黄，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和部服。也就是：
F(0) = 0, F(1) = 1, F(N) = F(N - 1) + F(N - 2), 其中 N > 1，給定 N拗慨，計(jì)算 F(N)廓八。

function fib(N) {
    // 若 N <= 1，則返回 N
    if (N <= 1) {
        return N;
    }
    // 若 N == 2
    if (N == 2) {
        return 2;
    }
    // 至少需要三個(gè)變量存儲(chǔ) fib(N), fib(N-1) 和 fib(N-2)赵抢。
    let current = 0; // 代表 fib(N)
    let prev1 = 2; // 代表fib(N-1)
    let prev2 = 1; // 代表 fib(N-2)

    for (let i = 3; i <= N; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

時(shí)間復(fù)雜度：O(N)剧蹂。
空間復(fù)雜度：O(1)，僅僅使用了 current烦却，prev1宠叼，prev2。

刪除字符串中的所有相鄰重復(fù)項(xiàng)

• 輸入："abbaca"
• 輸出："ca"
• 解釋?zhuān)?/li>
• 例如其爵，在 "abbaca" 中冒冬，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時(shí)唯一可以執(zhí)行刪除操作的重復(fù)項(xiàng)醋闭。之后我們得到字符串 "aaca"窄驹，其中又只有 "aa" 可以執(zhí)行重復(fù)項(xiàng)刪除操作，所以最后的字符串為 "ca"证逻。

const removeDuplicates = function(s) {
    if (!s || s.length === 1) {
        return s || ''
    }
    const stock = []
    for (const item of s) {
        if (stock.length && item === stock[stock.length - 1]) {
            stock.pop()
        } else {
            stock.push(item)
        }
    }
    return stock.join('')
};
console.log(removeDuplicates('abbaca')) // ca

版本號(hào)排序

var versions = ["1.45.0", "1.5", "6", "3.3.3.3.3.3.3"];
// 要求從小到大排序乐埠，注意'1.45'比'1.5'大
function sortVersion(versions) {
// TODO
}
// => ['1.5','1.45.0','3.3.3.3.3.3','6']

const sortVersion = (list) => {
    if (!list || !list.length) {
        return
    }
    return list.sort((a, b) => {
        let aArr = a.split('.')
        let bArr = b.split('.')
        let maxLen = aArr >= bArr ? aArr : bArr
        for (let i = 0; i < maxLen; i++) {
            let x = aArr[i] || 0
            let y = bArr[i] || 0
            if (x - y !== 0) {
                return x - y
            }
        }
    })
}

打亂數(shù)組

打亂一個(gè)沒(méi)有重復(fù)元素的數(shù)組
洗牌算法：從最后一個(gè)元素開(kāi)始，從數(shù)組中隨機(jī)選出一個(gè)位置囚企，交換丈咐，直到第一個(gè)元素。

class Disorder {
    constructor(arr) {
        this.originArr = [ ...arr ]
    }

    reset() {
        return this.originArr
    }

    shuffle() {
        const shuffleArr = [ ...this.originArr ]
        let curLen = shuffleArr.length - 1
        while (curLen > -1) {
            // 生成一個(gè)范圍在當(dāng)前下標(biāo)到數(shù)組末尾元素下標(biāo)之間的隨機(jī)整數(shù)
            const random = Math.floor(shuffleArr.length * Math.random())
            console.log(random);
            // 將當(dāng)前元素和隨機(jī)選出的下標(biāo)所指的元素互相交換
            [ shuffleArr[curLen], shuffleArr[random] ] = [ shuffleArr[random], shuffleArr[curLen] ]
            curLen--
        }
        return shuffleArr
    }
}

var obj = new Disorder([ 1, 4, 8, 9 ])
console.log(obj.shuffle());
console.log(obj.reset());

二叉樹(shù)的最大深度

給定一個(gè)二叉樹(shù)龙宏，找出其最大深度棵逊。二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

function TreeDepth(pRoot) {
    if (!pRoot) {
        return 0;
    }
    let left = TreeDepth(pRoot.left);
    let right = TreeDepth(pRoot.right);
    return Math.max(left, right) + 1;
}

二叉樹(shù)的鏡像

操作給定的二叉樹(shù)银酗，將其變換為源二叉樹(shù)的鏡像辆影。

function Mirror(pRoot) {
    if (!pRoot) {
        return null
    }
    let temp = pRoot.left
    pRoot.left = pRoot.right
    pRoot.left = temp

    Mirror(pRoot.left)
    Mirror(pRoot.right)

    return pRoot
}

樹(shù)的子結(jié)構(gòu)

輸入兩棵二叉樹(shù)A，B黍特，判斷B是不是A的子結(jié)構(gòu)蛙讥。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）

// 比較兩棵樹(shù)是否相同
function compTree(root1, root2) {
    if (!root2) {
        return true
    }
    if (!root1) {
        return false
    }
    if (root1.val !== root2.val) {
        return false
    }
    return compTree(root1.left, root2.left) && compTree(root1.right, root2.right)
}

// 判斷是否子結(jié)構(gòu)
function HasSubtree(pRoot1, pRoot2) {
    if (!pRoot1 || !pRoot2) {
        return false
    }
    if (!compTree(pRoot1, pRoot2)) {
        return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2)
    }
    return true
}

給一個(gè)嵌套對(duì)象，返回展平對(duì)象（屬性為 a.b.c）

const obj = {
    a: 'a',
    b: [1, 2],
    c: true,
    d: function() { console.log('d') },
    e:  {
        a: 'a-e',
        b: [1, 2, 3],
        c: false,
        d: function() { console.log('e-d') },
        f:  {
            a: 'a-f',
            b: [1, 2, 4],
            c: true,
            d: function() { console.log('f-d') },
        }
    }
}

function flatObj (data) {
    if (!data || data.constructor !== Object) {
        return {}
    }
    const obj = {}
    function flat(data, baseKey) {
        // for...in 會(huì)遍歷原型鏈上所有屬性灭衷，不推薦使用
        Object.keys(data).forEach(key => {
            const value = data[key];
            const finalKey = baseKey ? `${baseKey}.${key}` : key;
            if (value.constructor === Object) {
                flat(value, finalKey);
            } else {
                obj[finalKey] = value;
            }
        })
        return obj
    }
    return flat(data);
}

const data = flatObj(obj)
data.d()
data['e.d']()
data['e.f.d']()

計(jì)算一個(gè)有序數(shù)組中次慢，某個(gè)數(shù)字出現(xiàn)的次數(shù)

1. 方法1：用兩個(gè)循環(huán)，一個(gè)從頭找一個(gè)從尾找，找到第一次出現(xiàn)的位置和最后一次出現(xiàn)的位置迫像。再相減即可劈愚。

function GetNumberOfK(data, k) {
    var start = -1
    var end = -1
    for (var i = 0; i < data.length; i++) {
        if (data[i] == k) {
            start = i;
            break
        }
    }
    for (var j = data.length - 1; j > -1; j--) {
        if (data[j] == k) {
            end = j
            break
        }
    }
    if (start != -1 && end != -1) {
        return end - start + 1;
    } else {
        return 0
    }
}

2. 方法2：
   二分法，找到數(shù)字出現(xiàn)的第一次和最后一次闻妓。

function GetNumberOfK(data, k) {
    if (data.length == 0) {
        return 0;
    }
    var first = theFirst(data, 0, data.length - 1, k)
    var last = theLast(data, first - 1, data.length - 1, k)
    if (first != -1 && last != -1) {
        return last - first + 1;
    } else {
        return 0;
    }
}
// 找到第一次出現(xiàn)K的位置
function theFirst(data, start, end, k) {
    if (start > end) {
        return -1;
    }
    var mid = parseInt((start + end) / 2)
    if (data[mid] > k) {
        end = mid - 1;
        return theFirst(data, start, end, k)
    } else if (data[mid] < k) {
        start = mid + 1
        return theFirst(data, start, end, k)
    }
    // 還要多加一個(gè)判斷如果mid-1也為k的話菌羽，說(shuō)明第一次出現(xiàn)的位置還更小。
    else if ((mid - 1 >= 0) && (data[mid - 1] == k)) {
        return theFirst(data, start, mid - 1, k)
    } else {
        return mid;
    }
}
// 找到最后一次出現(xiàn)K的位置
function theLast(data, start, end, k) {
    if (start > end) {
        return -1;
    }
    var mid = parseInt((start + end) / 2)
    if (data[mid] > k) {
        end = mid - 1;
        return theLast(data, start, end, k)
    } else if (data[mid] < k) {
        start = mid + 1
        return theLast(data, start, end, k)
    }
    // 還要多加一個(gè)判斷如果mid+1也為k的話纷闺，說(shuō)明最后一次出現(xiàn)的位置還更大算凿。
    else if ((mid + 1 < data.length) && (data[mid + 1] == k)) {
        return theLast(data, mid + 1, end, k)
    } else {
        return mid;
    }
}

傳入真實(shí) dom份蝴，輸出 json

const handleNode = (node) => {
    if (!node) {
        return
    }
    return {
        name: node.nodeName,
        nodes: node.children && node.children.length ?
            Array.from(node.children).map(item => handleNode(item)) :
            node.innerHTML
    }
}
console.log(handleNode(document.body));

一個(gè)數(shù)組犁功，獲取出現(xiàn)次數(shù)最多的元素及其次數(shù)

const calcMaxNum = arr => {
    if (!Array.isArray(arr) || !arr.length) {
        return
    }
    const map = new Map()
    let maxItem = null
    let maxNum = 0
    arr.forEach(item => {
        if (map.has(item)) {
            map.set(item, map.get(item) + 1)
        } else {
            map.set(item, 1)
        }
        if (map.get(item) > maxNum) {
            maxItem = item
            maxNum = map.get(item)
        }
    })
    return { maxItem, maxNum }
}
calcMaxNum([1, 2, 3, 1, '2', '3', '1', 3, 5, 4, 3])

輸入 [ [1, 4, 7], [2, 5, 8], [3, 6, 9]]，輸出 [ [1, 2, 3], [4, 5, 6], [7, 8, 9]]

方式一：
const fn = (arr) => {
    if (!Array.isArray(arr) || !arr.length) {
        return;
    }
    return Array(arr[0].length).fill('').map((item, index) => arr.map(arrItem => arrItem[index]))
}

// 方式二：
function fn(arr) {
    const newArr = [];
    for (let i = 0; i < arr[0].length; i++) {
        newArr.push([]);
    }

    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr[0].length; j++) {
            newArr[i][j] = arr[j][i]
        }
    }
    return newArr;
}
fn([[1, 4, 7], [2, 5, 8], [3, 6, 9]])

N[string]婚夫，表示 string 正好重復(fù) N 次

const decodeStr = function (str) {
    if (typeof str !== "string") {
        throw "請(qǐng)輸入字符串";
    }
    let index = 0;
    let decodeQueue = [];
    while (index < str.length) {
        let eleStr = str[index];
        if (eleStr === "[") {
            decodeQueue.push(index);
        }
        if (decodeQueue.length > 0 && eleStr === "]") {
            let leftIndex = decodeQueue.pop();
            let rightIndex = index;
            str = strFormat(str, leftIndex, rightIndex);
            index = 0;
            continue;
        }
        index++;
    }
    return str;
};
const strFormat = function (str, startIndex, rightIndex) {
    // 輔助函數(shù): 將形如str[]對(duì)應(yīng)左右index展開(kāi);
    let temp = str.substring(startIndex + 1, rightIndex);
    let copiedStr = "";
    let copyNum = "";
    while (str[--startIndex] >= 0) {
        copyNum = str[startIndex] + copyNum;
    }
    for (let i = 0; i < copyNum; i++) {
        copiedStr += temp;
    }
    str =
        str.substring(0, startIndex + 1) +
        copiedStr +
        str.substring(rightIndex + 1);
    return str;
};
decodeStr('3[abc]2[cd]ff') // 'abcabcabccdcdff'

判斷b是否為a的子序列

const isSubsequence = (b, a) => {
    let bi = 0;
    let ai = 0;
    while (bi < b.length) {
        if (a[ai] === b[bi]){
            bi++;
        }
        ai++;
        if (ai > a.length) {
            return false;
        }
    }
    return true;
};
isSubsequence([1, 5, 11], [1, 3, 5, 7, 11]); // true

請(qǐng)完成下列函數(shù)

• 可以批量請(qǐng)求數(shù)據(jù)浸卦，所有的 URL 地址在 urls 參數(shù)中
• 同時(shí)可以通過(guò) max 參數(shù)控制請(qǐng)求的并發(fā)度
• 當(dāng)所有請(qǐng)求結(jié)束之后，需要執(zhí)行 callback 回調(diào)函數(shù)案糙。
• 發(fā)請(qǐng)求的函數(shù)可以直接使用 fetch 即可

/**
 *
 * @param { Array } urls  請(qǐng)求地址數(shù)組
 * @param { Number } max 最大并發(fā)請(qǐng)求數(shù)
 * @param { Function } callback  回調(diào)地址
 */
function parallelFetch(urls, max, callback) {
    // 如果當(dāng)前環(huán)境不支持 fetch , 則提示程序無(wú)法正常運(yùn)行
    if (!window.fetch || "function" !== typeof window.fetch) {
        throw Error("當(dāng)前環(huán)境不支持 fetch 請(qǐng)求限嫌，程序終止")
    }
  
    // 如果參數(shù)有誤，則提示輸入正確的參數(shù)
    if (!urls || urls.length <= 0) {
        throw Error("urls is empty: 請(qǐng)傳入正確的請(qǐng)求地址")
    }
  
    const _urlsLength = urls.length; // 請(qǐng)求地址數(shù)組的長(zhǎng)度
    const _max = max || 1 // 保證最大并發(fā)值的有效性
    let _currentIndex = 0 // 當(dāng)前請(qǐng)求地址的索引
    let _maxFetch = max <= _urlsLength ? max : _urlsLength // 當(dāng)前可以正常請(qǐng)求的數(shù)量时捌，保證最大并發(fā)數(shù)的安全性
    let _finishedFetch = 0 // 當(dāng)前完成請(qǐng)求的數(shù)量怒医，用于判斷何時(shí)調(diào)用回調(diào)
  
    console.log(`開(kāi)始并發(fā)請(qǐng)求，接口總數(shù)為 ${_urlsLength} 奢讨，最大并發(fā)數(shù)為 ${_maxFetch}`)
    // 根據(jù)最大并發(fā)數(shù)進(jìn)行循環(huán)發(fā)送稚叹，之后通過(guò)狀態(tài)做遞歸請(qǐng)求
    for (let i = 0; i < _maxFetch; i++) {
        fetchFunc()
    }

    // 請(qǐng)求方法
    function fetchFunc() {
        // 如果所有請(qǐng)求數(shù)都完成，則執(zhí)行回調(diào)方法
        if (_finishedFetch === _urlsLength) {
            console.log(`當(dāng)前一共 ${_urlsLength} 個(gè)請(qǐng)求拿诸，已完成 ${_finishedFetch} 個(gè)`)
            if ("function" === typeof callback) {
                return callback()
            }
            return false
        }
        // 如果當(dāng)前請(qǐng)求的索引大于等于請(qǐng)求地址數(shù)組的長(zhǎng)度扒袖，則不繼續(xù)請(qǐng)求
        if (_currentIndex >= _urlsLength) {
            _maxFetch = 0
        }
  
        // 如果可請(qǐng)求的數(shù)量大于0，表示可以繼續(xù)發(fā)起請(qǐng)求
        if (_maxFetch > 0) {
            console.log( `當(dāng)前正發(fā)起第 ${_currentIndex + 1 } 次請(qǐng)求亩码，當(dāng)前一共 ${_urlsLength} 個(gè)請(qǐng)求季率，已完成 ${_finishedFetch} 個(gè)，請(qǐng)求地址為：${urls[_currentIndex]}`)
            // 發(fā)起 fetch 請(qǐng)求
            fetch(urls[_currentIndex])
                .then((res) => {
                    // TODO 業(yè)務(wù)邏輯描沟，正常的邏輯飒泻，異常的邏輯
                    // 當(dāng)前請(qǐng)求結(jié)束，正常請(qǐng)求的數(shù)量 +1
                    _maxFetch += 1
                    _finishedFetch += 1
                    fetchFunc()
                })
                .catch((err) => {
                    // TODO 異常處理吏廉，處理異常邏輯
                    // 當(dāng)前請(qǐng)求結(jié)束泞遗，正常請(qǐng)求的數(shù)量 +1
                    _maxFetch += 1
                    _finishedFetch += 1
                    fetchFunc()
                });
            // 每次請(qǐng)求，當(dāng)前請(qǐng)求地址的索引  +1
            _currentIndex += 1
            // 每次請(qǐng)求迟蜜，可以正常請(qǐng)求的數(shù)量 -1
            _maxFetch -= 1
        }
    }
}
  
let urls = []
for (let i = 0; i < 100; i++) {
    urls.push(`https://jsonplaceholder.typicode.com/todos/${i}`)
}
const max = 10
const callback = () => {
    console.log("我請(qǐng)求完了")
}
parallelFetch(urls, max, callback)