【面试题-数组】1-前端数组必会算法题

题1：字符串反转 ‘123abc’ -> ‘cba321’

思路：字符串转数组split()，利用数组逆反方法reverse()然后再数组转字符串join()

var str = '123abc'
console.log(str.split('').reverse().join(''));

题2：在有序的数组里找出指定的值，返回该值在数组中的索引

方案1：

    var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15];
    
	function getIndex(arr,val){
		for(var i=0;i<arr.length;i++){
			if(arr[i]==val){
				return i;
			}
		}
	} 
	console.log(getIndex(arr, 5));	//2

方案2：利用findIndex()函数

ES6为Array增加了find()，findIndex函数。
find()函数用来查找目标元素，找到就返回该元素，找不到返回undefined。
findIndex()函数也是查找目标元素，找到就返回元素的位置，找不到就返回-1。

	var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15];
	function getIndex(arr,val){
		return arr.findIndex(function(value){
			return value==val;
		});
	}
	console.log(getIndex(arr, 5));	//2

方案3：二分查找

二分查找（折半查找）效率很高，但有个条件：数组必须是有序的(递增或递减，但是有两个相同的数是不行的)
大体思路：一分为二，一半一半的去找； 假设表中元素是按升序排列，

1. 比较中间位置val == arr[middle]，如果两者相等，则查找成功；
2. 否则利用中间位置记录将表分成前、后两个子表，查找关键字val < arr[middle]，则进一步查找前一子表此时end =end = middle - 1 ，
3. 否则val > arr[middle]进一步查找后一子表，此时start = middle + 1; 。
4. 重复以上过程(循环)，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

	var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15];

	function getIndex(arr, val) {
		var start = 0;	//起点数据对应的索引值
		var end = arr.length - 1;	//终点数据对应的索引值

		/*
			1、这里分别处理了奇数与偶数的情况
			2、如果为奇数的话，此时只剩下了三个数字。各自走一次，刚好走到中间。走到同一个位置的话，start==end
			3、如果为偶数的话，此时只剩下两个数字。各自己就不需要再走了。再走就超了。start<end
		 */
		while (start <= end) {   //括号里是跳出条件，不满足条件就一直循环
			var middle = parseInt((start + end) / 2);  //0 1 2   当有奇数位时，除2回有小数，所以要取整parseInt()

			if (val == arr[middle]) {
				//如果这个条件成立，说明第一次的时候就找到了
				return middle;
			} else if (val < arr[middle]) {
				//数据在左侧
				end = middle - 1;
			} else if (val > arr[middle]) {
				//数据在右侧
				start = middle + 1;
			}
		}

		return -1;
	}
	console.log(getIndex(arr, 5));	//2

题3：判断数组是否为对称数组，对称数组形式如：[a, b, c, b, a]、[a, b, c, c, b, a]

如：李经理、王中王、手拉手、面对面、上海自来水来自海上

方案1：
思路：我们新建一个数组的倒叙数组，如果倒叙数组的[i] == 原数组的[i]，那这个数组是对称的；

var arr1 = ['a', 'b', 'c', 'd', 'c', 'b', 'a'];
var arr2 = ['a', 'b', 'c', 'c', 'b', 'a'];
var arr3 = ['a', 'b', 'c', 'a', 'b', 'c'];  //这个不对称

function symmetry(arr){   //把数组arr放到一个新数组中，因为数组是引用值，所以直接赋值是不行的，操作的时候都会改变
	var newArr=[];
	for(var i=arr.length-1;i>=0;i--){   //倒序取数，这样直接得到倒序的数组
		newArr.push(arr[i]);  //我们遍历每一项然后手动放到数组里
}

for(var i=0;i<arr.length;i++){   
	if(arr[i]!=newArr[i]){   //进行比较
		return false;   //如果不等就跳出循环，返回false
		
	}
}
return true;  //没有不等的就是对称数组，返回true
} 

console.log(
	symmetry(arr1),	//true
	symmetry(arr2),	//true
	symmetry(arr3),	//false
);

方案2：

思路：依次判断数组的首位对称项 是都相同

var arr1 = ['a', 'b', 'c', 'd', 'c', 'b', 'a'];
var arr2 = ['a', 'b', 'c', 'c', 'b', 'a'];
var arr3 = ['a', 'b', 'c', 'a', 'b', 'c']; 

function symmetry(arr) {
	var start = 0;
	var end = arr.length - 1;

	for (var i = 0; i < arr.length; i++) {  //其实这里可以写 middle + 1,这样写其实是多循环判断了一半
		if (arr[start] != arr[end]) {   //依次判断数组的首尾对称项，如果不等就不对称
			return false;
		}
		start++;  //判断完一次，就给首位下表+1 / -1； 然后进行下一次循环对比判断
		end--;
	}
	return true;
}

console.log(
	symmetry(arr1),	//true
	symmetry(arr2),	//true
	symmetry(arr3),	//false
);

方案3：
思路：方案2里会多走一半次数的循环，这里改为while循环，但是终止循环的条件是：start >= end，这个条件不能当作跳出条件，否则循环一次都走不了

var arr1 = ['a', 'b', 'c', 'd', 'c', 'b', 'a'];
var arr2 = ['a', 'b', 'c', 'c', 'b', 'a'];
var arr3 = ['a', 'b', 'c', 'a', 'b', 'c']; 

function symmetry(arr) {
	var start = 0;
	var end = arr.length - 1;

	while (true) {  //【 1.】 这这个循环一直执行
		/*
			1、这里分别处理了奇数与偶数的情况
			2、如果为奇数的话，start与end相等的时候，就已经找到最后一个了。如果再走一次，start就大于end了。此时就要跳出循环了（当前那次还要走，过了当前那就不能再走了）
			3、如果为偶数的话，start与end挨着的时候，就已经找到最后一个了。如果再走一次，start就等于end了。此时就要跳出循环了 
		*/
		if (start >= end) {   //注意：这里是start >= end，当数组奇数位数时，start = end时符合条件，等下一次start>end的时候跳出；偶数位时，start<end且挨着时符合条件，等下一次start=end时跳出
			break;   //直接跳出循环  【2.】  当满足条件时，跳出循环
		}
		if (arr[start] != arr[end]) {  //如果不等的话，就不对称，返回false 并跳出循环
			return false;
		}
		start++;
		end--;
	}
	return true;  //没有不等的情况，就对称
}


console.log(
	symmetry(arr1),	//true
	symmetry(arr2),	//true
	symmetry(arr3),	//false
);