简单算法

实现 trim

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

斐波那契数列

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1, F(N) = F(N - 1) + F(N - 2), 其中 N > 1，给定 N，计算 F(N)。

function fib(N) {
    // 若 N <= 1，则返回 N
    if (N <= 1) {
        return N;
    }
    // 若 N == 2
    if (N == 2) {
        return 2;
    }
    // 至少需要三个变量存储 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;
}

时间复杂度：O(N)。
空间复杂度：O(1)，仅仅使用了 current，prev1，prev2。

删除字符串中的所有相邻重复项

• 输入："abbaca"
• 输出："ca"
• 解释：
• 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "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

版本号排序

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
            }
        }
    })
}

打乱数组

打乱一个没有重复元素的数组
洗牌算法：从最后一个元素开始，从数组中随机选出一个位置，交换，直到第一个元素。

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

    reset() {
        return this.originArr
    }

    shuffle() {
        const shuffleArr = [ ...this.originArr ]
        let curLen = shuffleArr.length - 1
        while (curLen > -1) {
            // 生成一个范围在当前下标到数组末尾元素下标之间的随机整数
            const random = Math.floor(shuffleArr.length * Math.random())
            console.log(random);
            // 将当前元素和随机选出的下标所指的元素互相交换
            [ 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());

二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

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
}

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

// 比较两棵树是否相同
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)
}

// 判断是否子结构
function HasSubtree(pRoot1, pRoot2) {
    if (!pRoot1 || !pRoot2) {
        return false
    }
    if (!compTree(pRoot1, pRoot2)) {
        return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2)
    }
    return true
}

给一个嵌套对象，返回展平对象（属性为 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 会遍历原型链上所有属性，不推荐使用
        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']()

计算一个有序数组中，某个数字出现的次数

1. 方法1：用两个循环，一个从头找一个从尾找，找到第一次出现的位置和最后一次出现的位置。再相减即可。

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：
   二分法，找到数字出现的第一次和最后一次。

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;
    }
}
// 找到第一次出现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)
    }
    // 还要多加一个判断如果mid-1也为k的话，说明第一次出现的位置还更小。
    else if ((mid - 1 >= 0) && (data[mid - 1] == k)) {
        return theFirst(data, start, mid - 1, k)
    } else {
        return mid;
    }
}
// 找到最后一次出现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)
    }
    // 还要多加一个判断如果mid+1也为k的话，说明最后一次出现的位置还更大。
    else if ((mid + 1 < data.length) && (data[mid + 1] == k)) {
        return theLast(data, mid + 1, end, k)
    } else {
        return mid;
    }
}

传入真实 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));

一个数组，获取出现次数最多的元素及其次数

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 正好重复 N 次

const decodeStr = function (str) {
    if (typeof str !== "string") {
        throw "请输入字符串";
    }
    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) {
    // 辅助函数: 将形如str[]对应左右index展开;
    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

请完成下列函数

• 可以批量请求数据，所有的 URL 地址在 urls 参数中
• 同时可以通过 max 参数控制请求的并发度
• 当所有请求结束之后，需要执行 callback 回调函数。
• 发请求的函数可以直接使用 fetch 即可

/**
 *
 * @param { Array } urls  请求地址数组
 * @param { Number } max 最大并发请求数
 * @param { Function } callback  回调地址
 */
function parallelFetch(urls, max, callback) {
    // 如果当前环境不支持 fetch , 则提示程序无法正常运行
    if (!window.fetch || "function" !== typeof window.fetch) {
        throw Error("当前环境不支持 fetch 请求，程序终止")
    }
  
    // 如果参数有误，则提示输入正确的参数
    if (!urls || urls.length <= 0) {
        throw Error("urls is empty: 请传入正确的请求地址")
    }
  
    const _urlsLength = urls.length; // 请求地址数组的长度
    const _max = max || 1 // 保证最大并发值的有效性
    let _currentIndex = 0 // 当前请求地址的索引
    let _maxFetch = max <= _urlsLength ? max : _urlsLength // 当前可以正常请求的数量，保证最大并发数的安全性
    let _finishedFetch = 0 // 当前完成请求的数量，用于判断何时调用回调
  
    console.log(`开始并发请求，接口总数为 ${_urlsLength} ，最大并发数为 ${_maxFetch}`)
    // 根据最大并发数进行循环发送，之后通过状态做递归请求
    for (let i = 0; i < _maxFetch; i++) {
        fetchFunc()
    }

    // 请求方法
    function fetchFunc() {
        // 如果所有请求数都完成，则执行回调方法
        if (_finishedFetch === _urlsLength) {
            console.log(`当前一共 ${_urlsLength} 个请求，已完成 ${_finishedFetch} 个`)
            if ("function" === typeof callback) {
                return callback()
            }
            return false
        }
        // 如果当前请求的索引大于等于请求地址数组的长度，则不继续请求
        if (_currentIndex >= _urlsLength) {
            _maxFetch = 0
        }
  
        // 如果可请求的数量大于0，表示可以继续发起请求
        if (_maxFetch > 0) {
            console.log( `当前正发起第 ${_currentIndex + 1 } 次请求，当前一共 ${_urlsLength} 个请求，已完成 ${_finishedFetch} 个，请求地址为：${urls[_currentIndex]}`)
            // 发起 fetch 请求
            fetch(urls[_currentIndex])
                .then((res) => {
                    // TODO 业务逻辑，正常的逻辑，异常的逻辑
                    // 当前请求结束，正常请求的数量 +1
                    _maxFetch += 1
                    _finishedFetch += 1
                    fetchFunc()
                })
                .catch((err) => {
                    // TODO 异常处理，处理异常逻辑
                    // 当前请求结束，正常请求的数量 +1
                    _maxFetch += 1
                    _finishedFetch += 1
                    fetchFunc()
                });
            // 每次请求，当前请求地址的索引  +1
            _currentIndex += 1
            // 每次请求，可以正常请求的数量 -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("我请求完了")
}
parallelFetch(urls, max, callback)