前端面试题 - 算法

// 1.限制最大请求
function asyncPool(list, limitCount, fun){
    let i=0; 
    let totalList = [];
    let excuteList = [];

    const queue = function(){
        if(totalList.length === limitCount){
            return Promise.resolve();
        }

        let p = Promise.resolve().then(() => {fun(list[i++], list);})
        totalList.push(p);

        let e = p.then(() => {excuteList.splice(excuteList.indexOf(e), 1)});
        excuteList.push(e);

        let r = excuteList.length >= limitCount ? Promise.race(excuteList) : Promise.resolve()

        return r.then(() => queue)

    }

    return queue.then(() => Promise.all(totalList))
}

// 2.找到最多重复字符
function findMaxDuplicateChar(str){
    if(str.length === 1){
        return [str, 1]
    }
    let object = {};
    for(let key of Object.keys(str)){
        const char = str[key];
        if(!object[char]){
            object[char] = 1;
        } else {
            object[char] = object[char] + 1;
        }
    }

    let maxChar = '';
    let maxCount = 0;
    for(let i of Object.keys(object)){
        if(object[i] > maxCount){
            maxChar = i;
            maxCount = object[i];
        }
    }

    return [maxChar, maxCount];
}

// 3.洗牌算法
function getMess(list){
    return list.sort(function(){
        Math.random() - 0.5;
    })
}

function getMess2(list){
    let resultList = [];
    let length = list.length;
    while(length){
        resultList.push(list.splice(Math.floor(Math.random() * length--), 1)[0]);
    }
    return resultList;
}

// 4.排序算法
// (1)冒泡
function bubbleSort(list){
    let length = list.length;
    for(let i=0; i < length; i++){
        for(let j=i+1; j < length; j++){
            if(list[i] > list[j]){
                let value = list[j];
                list[j] = list[i];
                list[i] = value;
            }
        }
    }
}

// (2)快速排序
function quickSort(list){

    if(list.length <= 1){
        return list;
    }
    
    let middleIndex = Match.floor((list.length-1)/2);
    let middleValue = list.splice(middleIndex, 1)[0];

    let left = [];
    let right = [];

    for(let key of Array.keys(list)){
        if(list[key] <= middleValue){
            left.push(list[key]);
        } else {
            right.push(list[key]);
        }
    }

    return quickSort(left).concat([middle], quickSort(right));
}

// (3)插入排序
let searchIndex = (arr, item) => {
    if(item < arr[0]){
        return 0;
    } 
    if(item > arr[arr.length - 1]){
        return arr.length;
    }
    let i=0;
    for(; i<arr.length; i++){
        if(arr[i] <= item && item <= arr[i+1]){
            break;
        }
    }
    return i+1;
}

let insertSort = arr => {
    if(arr.length === 0){
        return;
    }
    let resultList = [arr[0]];
    for(let i=1; i<arr.length; i++){
        let index = searchIndex(resultList, arr[i]);
        resultList.splice(index, 0, arr[i]);
    }
    return resultList;
}

// 5.斐波那契数列
let getFibonacci = n => {
    if(n <=1) return 1;
    let result = getFibonacci(n-1) + getFibonacci(n-2);
    return result;
}

// 尾递归
let getFibonacci1 = (n, ac1=1, ac2=1) => {
    if(n<=1) {return ac2};
    let result = getFibonacci1(n-1, ac2, ac1+ac2);
    return result;
}

// 6.生成1~100的数组
// (1)ES6
let arr = Array.from(Array(100), (value, index) => index + 1);

// (2)ES5
let arr1 = Array.prototype.map(Array(101).join('0').split(''), function(){
    return arguments[1]+1;
})

// 7.数组去重
// （1）Object
function unique(arr2){
    let obj = {};
    let resultList1 = [];
    for(let i=0; i<arr.length; i++){
        if(!obj[arr2[i]]){
            obj[arr2[i]] = true;
            resultList1.push(obj[arr2[i]]);
        }
    }
    return resultList1;
}

// (2)filter
function unique2(arr3){
    return arr3.filter((item, index) => {
        if(arr3.indexOf(item) !== index){
            return false;
        }
        return true;
    })
}

// (3)Set
let resultList = Array.form(new Set(arr4))

// (4)new array
function unique3(arr4){
    let rstList = [];
    arr4.forEach(element => {
        if(rstList.indexOf(element) === -1){
            rstList.push(element);
        }
    });
    return rstList;
}

// 8.二叉树高度
function h(node){
    return node === null ? 0 : (Math.max.call(h(node.left), h(node.right)) + 1);
}

// 9.千分位逗号
function numFormat(str){
    str = str.indexOf('.') !== -1 ? str.split('.')[0] : str;
    let reverseList = Array.from(str).reverse();
    let rstList = [];
    for(let i=0; i<reverseList.length; i++){
        if(i%3 === 0 && i > 0){
            rstList.push(',');
        } else {
            rstList.push(reverseList[i]);
        }
    }
    rstList.reverse()
    let rstStr = rstList.join('');
    rstStr = str.indexOf('.') !== -1 ? rstStr + str.split('.')[1] : rstStr;
    return rstStr;
}

// 10.大数字加减法
function bigData(a, b){
    if(a === '' || b === '' || escape(a).index('%u') !== -1 || escape(b).index('%u') !== -1){
        console.log('err');
        return ;
    }
    let numA = new Number(a);
    let numB = new Number(b);
    let numC = new Number(numA + numB).toLocaleString();
    let result = numC.replace(/,/g, ''); 
    return result;
}

// 11.最长公共子串
function getLongestStr(str1, str2){
    let result = '';
    if(str1.length < str2.length){
        [str1, str2] = [str2, str1];
    }
    for(let j=str1.length; j>0; j--){
        for(let i=0; i<str1.length - j; i++){
            let str1Part = str1.substring(i, j);
            if(str2.includes(str1Part)){
                result = str1Part;
            }
        }
    }
    return result;
}

// 12.最长连续数字
function findLongestNum(str){
    let rstList = [];
    let itemList = isNum(str[0]) ? [parseInt(str[0])] : [];
    for(let key of str){
        if(key > 0){
            if(isNum(str[key]) && (key < str.length - 1) && isNum(str[key - 1]) && (parseInt(str[key - 1]) + 1 === parseInt(str[key]))){
                itemList.push(parseInt(str[key]));
            } else {
                rstList.push(itemList);
                itemList = [];
            }
        }
    }

    let maxCount = 0;
    let resultStr = '';
    rstList.forEach(item => {
        if(item.length > maxCount){
            maxCount = item.length;
            resultStr = item.join('');
        }
    })

    return resultStr;

    function isNum(str1){
        if(parseInt(str1) >= 0 && parseInt(str1) < 10){
            return true;
        }
        return false;
    }
}

// 13.LCS动态规划求最长公共子序列
function getLongestSeq(ary1, ary2){
    ary1 = ary1.unshift("");
    ary2 = ary2.unshift("");
    const length1 = ary1.length; 
    const length2 = ary2.length;
    let t = [];
    for(let i=0; i<length1; i++){
        t[i] = [];
        for(let j=0; j<length2; j++){
            if(i == 0 || j == 0){
                t[i][j] = 0;
            }
            if(ary[i] === ary[j]){
                t[i][j] = t[i-1][j-1] + 1;
            } else {
                t[i][j] = Math.max(t[i][j-1], t[i-1][j]);
            }

        }
    }

    let n1 = length1 - 1;
    let n2 = length2 - 1;
    let result = [];
    while(n1>0 && n2>0){
        if(ary1[n1] == ary2[n2]){
            result.unshift(ary1[n1]);
            i--;
            j--;
        } else {
            if(t[i-1][j] > t[i][j-1]){
                i--;
            } else {
                j--;
            }
        }
    }

    return result;
}

// 14.柯里化
function curry(fn){
    let c = (...arguments) => (fn.length === arguments.length) ?
    fn(arguments) : (...arguments1) => c(...arguments, ...arguments1);
    return c;

    // return (a) => {
    //     return (b) => {
    //         return (c) => {
    //             fn(a*b*c);
    //         }
    //     }
    // }
}

// 15.反转二叉数
function invertTree(node){
    if(node !== null){
        [node.left, node.right] = [node.right, node.left];
        invertTree(node.left);
        invertTree(node.right);
    }
    return node;
}

// 16.贪心算法解决背包问题
let number = ['A', 'B', 'C', 'D'];
let weights = [20, 15,23,30];
let values = [50, 200, 15, 30];
let capacity = 32;

function greedy(weighst, values, capacity){
    let rest = capacity;
    let num = 0;
    let sortAry = [];   
    weights.forEach((item, index) => {
        sortAry.push({
            weight: item,
            value: values[index],
            radio: values[index] / item
        })
    })
    sortAry.sort(function(a, b){a.radio > b.radio});
    let result = 0;
    sortAry.forEach(item => {
        num = Math.floor(rest / item.weight);
        rest -= num * item.weight;
        result = num * item.value;
    })
    return result;
}

// 17.找到一个数组中的两个元素之和为S的两个元素。
function findNumbersWithSum(arr, s){
    for(let i=0; i<arr.length / 2; i++){
        if(arr.indexOf(s - arr[i], i+1) !== -1){
            return [arr[i], arr.indexOf(s - arr[i])];
        }
    }
    return [];
}

// 18.两个升序数组合并成一个
function mergeSort(arr1, arr2){
    let resultList = [];
    let i=0, j=0, p=0, length1 = arr1.length, length2 = arr2.length;
    while(i < length1 || j < length2){
        if(i < length1 && j < length2){
            resultList[p++] = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
        } else if(i<length1){
            resultList[p++] = arr1[i++];
        } else {
            resultList[p++] = arr2[j++];
        }
    }
    return resultList;
}

// 19.判断一个链表是否有环
// (1) set
function hasCircle(node){
    let s = new Set();
    while(node){
        if(s.has(node)){
            console.log('有环 node=', node);
            return;
        }
        s.add(node);
        node = node.next();
    }
    console.log('无环');
    return;
}

// (2) visited
function hasCircle1(node){
    while(node){
        if(node.visit){
            console.log('有环');
            return;
        }
        node.visit = true;
        node = node.next();
    }
    console.log('无环');
}

// (3) 双指针
function hasCircle2(node){
    let quickNode = node.next().next();
    let slowNode = node.next();

    while(quickNode && slowNode){
        if(quickNode === slowNode){
            return '有环'
        }
        quickNode = quickNode.next().next();
        slowNode = node.next();
    }
    return '无环';
}

// 20.判读环的入口
function entry(node){
    let quickNode = node.next().next();
    let slowNode = node.next();

    while(quickNode && slowNode){
        if(quickNode === slowNode){
            quickNode = node;
            while(quickNode && slowNode){
                if(quickNode === slowNode){
                    return quickNode;
                }
                quickNode = quickNode.next();
                slowNode = slowNode.next();
            }
            
        }
        quickNode = quickNode.next().next();
        slowNode = node.next();
    }

    return null;
}