前端算法面试题整理

1.统计字符串出现最多的字母及其次数

function getMaxCount(str) {
    let resultMap = new Map();
    for (let letter of str) {
        if (resultMap.has(letter)) {
            resultMap.set(letter, resultMap.get(letter) + 1);
        } else {
            resultMap.set(letter, 1);
        }
    }
    let maxCount = Math.max(...resultMap.values()); //利用ES6解构，从而可以使用Math.max()

    let maxCountLetters = []; //可能几个字符同时都是出现次数最多的，所以用一个Array去装这些字符
    resultMap.forEach((value, key, mapSelf) => {
        if (value === maxCount) {
            maxCountLetters.push(key);
        }
    });
    return {maxCountLetters: maxCountLetters, maxCount: maxCount};
}

getMaxCount('aabbc'); //{maxCountLetters: ['a', 'b'], maxCount: 2}

2.排序算法

function bubbleSort(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] < arr[j + 1]) {
                var temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

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

3去重算法

function unique1(arr) {
    var newArr = [];
    for (var i = 0; i < arr.length; i++) {
        if (newArr.indexOf(arr[i]) == -1) {
            newArr.push(arr[i]);
        }
    }
    return newArr;
}

var arr1 = ['b', 'b', 'a', 1, 3, 4, 4];
console.log(unique1(arr1));

function unique2(arr) {
    var hash = {},
        newArr = [];
    for (var i = 0; i < arr.length; i++) {
        if (!hash[arr[i]]) {
            hash[arr[i]] = true;
            newArr.push(arr[i]);
        }
    }
    return newArr;
}

var arr2 = ['b', 'b', 'a', 1, 3, 4, 4];
console.log(unique2(arr2));

function unique3(arr) {
    for (var i = 0; i < arr.length; i++) {
        for (var j = 0; j < arr.length; j++) {
            if (arr[i] === arr[j] && i != j) {
                arr.splice(i, 1);
            }
        }
    }
    return arr;
}

var arr3 = ['b', 'b', 'a', 1, 3, 4, 4];
console.log(unique3(arr3));

4.判断位置数组是否相等

首先判断两个数组是否相等时不能直接使用==

var array1 = [];
var array2 = [];
console.log(array1 == array2); //输出false

对于对象来说，==比较的是两个对象是否为同一个对象。数组属于对象类型，尽管数组元素是相同的，但这两个数组属于不同的对象，所以==比较为false。
数组简单比较
如果数组里的元素是标量，非object类型，可以使用==比较数组里的元素：

scalarArrayEquals(array1,array2) {
  return array1.length==array2.length && array1.every(function(v,i) { return v === array2[i]});
}

嵌套数组比较
如果数组是多层嵌套，数组的基本元素也为标量。

arrayEquals(array1, array2) {
    if(!(array1 || array1)) {
      return false;
    }
    // 先比较长度 
    if (array1.length != array2.length)
        return false;

    for (var i = 0, l=array1.length; i < l; i++) {
        // 检查是否为内嵌数组
        if (array1[i] instanceof Array && array2[i] instanceof Array) {
            // 递归比较数组
            if (!arrayEquals(array1[i],array2[i]))
                return false;       
        } else if (this[i] != array[i]) { //标量比较 
            return false;   
        }           
    }       
    return true;
}

Lodash或Underscore比较数组（推荐）

如果数组的元素可能为object，可以考虑使用Lodash或者Underscore。它们已经实现了对象的深度比较，包括数组。

_.isEqual(array1, array2)   //相等返回true，否则返回false
_.isEqual(object1, object2) //

使用Lodash或Underscore比较数组或对象很简单：

转为字符串比较数组
除了上面的比较方法外，还可以把数组转换为字符串后，比较字符串。

array1.toString() === array2.toString();

或者

JSON.stringify(array1) === JSON.stringify(array2);

但相对上面几种方式，转换为字符串后再比较的性能是比较差的。其中以JSON转换为字符串的性能最差。

5.利用中介Array.reverse()的反转数组的特性

function isPalindRome(str) {
    return str.split('').reverse().join('') === str;

}

console.log(isPalindRome('madam')); //true
console.log(isPalindRome('mada')); //false

6.不利用任何方法，手动创建新字符串

function isPalindRome(str) {
    let newStr = '';
    for(let i = str.length - 1; i >= 0; i --){
        newStr = newStr + str[i];

    }
    return newStr === str;

}

console.log(isPalindRome('madam'));
console.log(isPalindRome('mada')); 

7.从字符串的头和尾开始，依次比较字符串组是否相等，逐渐往中间收，如果全部相等，则是回文

function isPalindRome(str) {
    let length = str.length;
    for(let i = 0; i <= Math.floor(str.length / 2); i ++){
        if(str[i] !== str[length - 1 - i]){
            return false;
        }
    }

    return true;

}

console.log(isPalindRome('aabbaa')); //true
console.log(isPalindRome('aabaa')); //true
console.log(isPalindRome('abb')); //false

8. 生成某个整数范围内的随机数

//利用Math.round()进行四舍五入
function randomInt(min, max){
    return Math.round(Math.random() * (max - min) + min);
}

//利用Math.ceil()向上取整
Math.ceil(num)返回比num大的最小的整数，如果num已经是整数，就返回自己
console.log(Math.ceil(0.95)); //1
console.log(Math.ceil(4)); //4
console.log(Math.ceil(7.0009)); //8

所以，如果我们是要得到3 ～ 6之间的整数，利用ceil()方法就是：
Math.ceil(Math.random()* (6 - 3) + 3)

所以代码实现就是：

function randomRang(min, max) {
    return Math.ceil(Math.random()* (max - min) + min);;
}

9.二分查找

二分查找的前提是有序数组，算法的思想是：
1: 比较需要查找的元素和数组的中间元素做比较，如果相等则返回对应的坐标，否则
2: 如果需要查找的元素比中间元素小，则在数组的前半部分继续采用步骤1的方法查找
3: 如果需要查找的元素比中间元素大，则在数组的后半部分继续采用步骤1的方法查找
4: 递归以上步骤
5: 特别要注意的一点是，如果数组不包含需要查找的元素，则返回-1

function binarySearch(target, arr, startIndex, endIndex) {
    let length = arr.length;
    if (target < arr[0] || target > arr[length - 1]) {
        return -1;
    }
    let pivotIndex = startIndex + Math.floor((endIndex - startIndex) / 2);
    let pivot = arr[pivotIndex];
    if (pivot === target) {
        return pivotIndex;
    } else if (target < pivot) {
        return binarySearch(target, arr, startIndex, pivotIndex - 1);
    } else {
        return binarySearch(target, arr, pivotIndex + 1, endIndex)
    }

}

binarySearch(8, [0, 1, 2, 4, 5, 6, 7], 0, 7); //-1
binarySearch(0, [0, 1, 2, 4, 5, 6, 7], 0, 7); //0

10. 使用闭包获取每个li的index

在ES6之前，因为没有块级作用域，在循环体内创建的函数，常常得不到我们想要的结果。例如很经典的依次输出0～9，最后输出9个9；或者如我们这里的获取每个li元素的index:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title></title>
    <script type="text/javascript">

        //fun这种写法，点击每一个li，输出的结果都是5
        let fun = function () {
            let lists = document.getElementsByTagName('li');
            for (var index = 0; index < lists.length; index++) {
                lists[index].onclick = function () {
                    console.log(`index: ${index}`)
                }
            }

        };

        window.onload = fun;
    </script>
</head>
<body>
<ul>
    <li>a</li>
    <li>b</li>
    <li>c</li>
    <li>d</li>
    <li>e</li>
</ul>
</body>
</html>

以上的fun的这种写法之所以不对是因为：循环里的每次迭代都共享一个变量index，循环内部创建的函数都保留了对同一个变量的引用，当循环结束的时候，index的值已经变为5，所以点击每一个li都会输出5.

以下的三个函数的实现方式都是对的：

let fun1 = function () {
    let lists = document.getElementsByTagName('li');
    for (let index in lists) {
        lists[index].onclick = function () {
            console.log(`index: ${index}`)
        }

    }

};
let fun2 = function () {
    let lists = document.getElementsByTagName('li');
    for (let index = 0; index < lists.length; index++) {
        lists[index].onclick = function () {
            console.log(`index: ${index}`)
        }
    }

};

let fun3 = function () {
    let lists = document.getElementsByTagName('li');
    for (var index = 0; index < lists.length; index++) {
        (function (index) {
            lists[index].onclick = function () {
                console.log(`index: ${index}`)
            }
        })(index)
    }

};

11.冒泡排序算法

 function mao(arr){
     for(let i=0;i<arr.length;i++){
         for(let j=0;j<arr.length-i;j++){
             if(arr[j]>arr[j-1]){
                 let tmp = arr[j];
                 arr[j]=arr[j-1];
                 arr[j-1]=tmp;
             }
         }
     }   
        return arr;
    }

12: 从字符串的头和尾开始，依次比较字符串组是否相等，逐渐往中间收，如果全部相等，则是回文

function isPalindRome(str) {
    let length = str.length;
    for(let i = 0; i <= Math.floor(str.length / 2); i ++){
        if(str[i] !== str[length - 1 - i]){
            return false;
        }
    }

    return true;

}

console.log(isPalindRome('aabbaa')); //true
console.log(isPalindRome('aabaa')); //true
console.log(isPalindRome('abb')); //false