前端常见算法题 JavaScript 实现（19校招持续更新）

1. 求数组最大值和最小值之差

方法一：使用归并方法reduce (ES5)

API:array.reduce(function(prev, cur,index, array), initialValue);
reduce方法有两个参数：

• 第一个参数：在每一个项上调用的函数

  该函数有四个参数：

  • prev：初始值
  • cur：当前元素
  • index：当前元素的索引
  • array：当前元素所属的数组对象

• 第二参数：作为归并基础的初始值（可选）

代码实现：

var arr = [567, 45, 3, 3, 6, 2, 7, 234, 56];

function getMaxSubMin(arr) {
    Array.prototype.max = function () {
        return this.reduce(function (preValue, curValue, index, array) {
            return preValue > curValue ? preValue : curValue;
        })
    }
    Array.prototype.min = function () {
        return this.reduce(function (preValue, curValue, index, array) {
            return preValue > curValue ? curValue : preValue;
        })
    }
    return arr.max() - arr.min();
};
console.log(getMaxSubMin(arr));//565

方法二：使用内置函数的数学方法Math.max()和Math.min()

代码：

var arr = [567, 45, 3, 3, 6, 2, 7, 234, 56];

function getMaxSubMin(arr) {
    Array.prototype.max = function () {
        return Math.max.apply({}, this);
    };
    Array.prototype.min = function () {
        return Math.min.apply({}, this);
    };
    return arr.max() - arr.min();
};
console.log(getMaxSubMin(arr)); //565

2. 日期格式的数组如何排序

代码：

var dateArr = ['2018-01-20', '2017-02-19', '2016-08-08', '2018-12-09'];

function sortByDate(dateArr) {
    dateArr.sort(function (a, b) {
        return Date.parse(b.replace(/-/g, "/")) - Date.parse(a.replace(/-/g, "/"));
    });
    return dateArr;
}
console.log(sortByDate(dateArr));
/* [ 
'2018-12-09',
'2018-01-20',
'2017-02-19',
'2016-08-08' ] */

3. 调用'abcd'.f()将字符串'abcd'格式化成'd-c-b-a'

String.prototype.f = function () {
    return this.split("").reverse().join("-");
}
console.log('abcd'.f());//'d-c-b-a'

4. 为所有数组对象添加一个findDuplicate(n)方法，用于返回该数组中出现频率>=n的元素列表

Array.prototype.findDuplicate = function (count) {
    return this.reduce((re, val) => {
        let index = re.findIndex(o => o.val === val)
        if (index >= 0) {
            re[index].count++
        } else {
            re.push({
                count: 1,
                val
            })
        }
        return re
    }, []).filter(o => o.count >= count).map(o => o.val)
};

var arr = [1, 2, 3, 3, 4, 4, 4, 4, 4, 4];
console.log(arr.findDuplicate(4));

5. 尾递归优化计算Fibonacci数列

function Fib(n, ac1 = 1, ac2 = 1) {
    if (n <= 1) {
        return ac2;
    };
    return Fib(n - 1, ac2, ac1 + ac2);
}

6. 封装一个repeat函数，调用console.log4次hello world，每次间隔3秒

function repeat(func, times, wait) {
    return function () {
        var arg = arguments;
        var handle = function (i) {
            setTimeout(function () {
                func.apply(null, arg);
            }, wait * i)
        }
        for (let i = 0; i < times; i++) {
            handle(i);
        }
    }
}
var repeatFunc = repeat(console.log, 4, 3000);
repeatFunc("hellworld");

7. 输出一个数组中第N大的数据(堆排序)

该实现只需循环k次。非常适合内存有限、数据海量的情况。时间复杂度：O（N * log2K）

function topKOfArr(k, arr) {
    function swap(a, b) {
        var t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
    var i, j;
    for (i = arr.length; i > arr.length - k; i--) {
        for (j = Math.floor(i / 2) - 1; j >= 0; j--) {
            if (arr[j] < arr[2 * j + 1]) {
                swap(j, 2 * j + 1);
            }
            if (2 * j + 2 < i && arr[j] < arr[2 * j + 2]) {
                swap(j, 2 * j + 2);
            }
        }
        swap(i - 1, 0);
    }
    console.log(arr.length - k);
    return arr.slice(arr.length - k, arr.length - k + 1);
}

var arr = [1, 4, 6, 8, 99, 77, 56, 10, 25, 20],
    k = 5;
console.log(topKOfArr(k, arr)); //[ 20 ]

8. 实现一个快排

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    var pivotIndex = Math.floor(arr.length / 2);
    //找基准，并把基准从原数组删除
    var pivot = arr.splice(pivotIndex, 1)[0];
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}
var arr = [12, 34, 45, 65, 1, 2, 3];
console.log(quickSort(arr));