js-经常遇到的算法题
最近在面试中遇到几个js算法题，感觉挺有借鉴意义，整理一下。
1. 数组去重
比如输入: [1,2,3,4,2,3,4]
输出: [1,2,3,4]
需要去掉重复的2、3、4 这两个元素
这道题在面试的试题中出现率比较高，主要考察个人对object的使用，利用key来进行筛选。有多种方法，这里只列举一种常用的方法。
function unique(arr){
let res = [];
let json = {};
for (var i = 0 , l = arr.length; i < l; i++) {
if (!json[arr[i]]) {
res.push(arr[i]);
json[arr[i]] = 1;
}
}
return res;
}
let arr = [1,2,3,4,2,3,4];
console.log(unique(arr)); //[1,2,3,4]
2. 统计一个字符串中出现最多的及其出现的次数
给出一个字符串，统计出现次数最多的字母。如：“asdfssaaasasasasaa”，其中出现最多的是a
function repeated (str){
let json = {};
for(let i = 0 , l = str.length; i < l; i++){
if(!json[str.charAt(i)]){
json[str.charAt(i)] = 1;
} else {
json[str.charAt(i)]++;
}
}
let iMax = 0;
let iIndex = '';
for(let j in json){
if(json[j] > iMax){
iMax = json[j];
iIndex = j;
}
}
console.log('出现次数最多的是:'+iIndex+'出现'+iMax+'次');
}
let str = 'asdfssaaasasasasaa';
repeated(str);
3.计算一个整数的阶乘
如果用字母n来代表一个整数，阶乘代表着所有小于或等于n的整数的乘积。阶乘通常简写成 n! ； 例如: （5! = 1 * 2 * 3 * 4 * 5 = 120）
刚开始想到的是用循环来实现，在实现之前需要对输入的数字做一下判断
function factorial (num) {
if (num < 0) {
return -1;
} else if (num === 0 || num === 1) {
return 1;
} else {
for (var i = num - 1; i >= 1; i--) {
num *= i;
}
}
return num;
};
let num = factorial(5);
console.log(num);
用递归来实现这一方法，毕竟阶乘函数是递归函数的典型实例
function factorialize(num) {
return num > 1 ? num * factorialize(num-1) : 1;
}
4.冒泡排序
let examplearr=[8,94,15,88,55,76,21,39];
function sortarr(arr){
for(let i=0;i<arr.length-1;i++){
for(let j=0;j<arr.length-1-i;j++){
if(arr[j]>arr[j+1]){
let temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
return arr;
}
sortarr(examplearr);
console.log(examplearr);
解析
两个循环
当i=0的时候，里面的循环完整执行，从j=0执行到j=6,这也就是第一遍排序，结果是将最大的数排到了最后，这一遍循环结束后的结果应该是[8,15,88,55,76,21,39,94]
当i=1的时候，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是j<arr.length-1-i的巧妙之处，结果是[8,15,55,76,21,39,88,94]
说到这里，规律就清楚了，每次将剩下数组里面最大的一个数排到最后面，当第一个循环执行到最后的时候，也就是i=6,此时，j=0,只需要比较数组的第一和第二项，比较完毕，返回。
以下为引用示例
5.不需要借助第三个临时变量，实现两个变量的交换
function swap（a,b）{
b=b-a;
a=a+b;
b=a-b;
return [a,b];
}
6.斐波那契数列
function getFib(n){
let fibairr =[];
let i=0;
while(i<n) {
if (i<=1){
fibarr.push(i);
} else{
fibarr.push(fibarr[i-1])
}
i++;
}
return fibarr;
}
7.找出下列正整数组的最大差值
输入的数组是[10,5,11,7,8,9]
输出 6
function getMaxPro(arr){
let minPrice=arr[0];
let maxProfit=0;
for (let i=0;i<arr.length;i++){
let currentPrice=arr[i];
minPrice=Math.min(minPrice,currentPrice);
let potentialProfit =currenrPrice-minPrice;
maxProfit=Math.max(maxProfit,potentialProfit);
}
return maxProfit;
}
8.随机生成指定长度的字符串
比如指定的长度为8
function random(n){
let str='abcdefghijkmnopqrstuvwxyz9876543210';
let tmp='',
i=0,
l=str.length;
for(i=0;i<n;i++){
tmp +=str.charAt(Math.floor(Math.random()*l))
}
return tmp;
}
