前端算法面试题整理
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
作者:为光pig
原文链接:https://www.jianshu.com/p/4c3797fe0794