Fork me on GitHub

JS算法

置顶 | 发表于 | 分类于 |
字数统计: 2.9k | 阅读时长 ≈ 15 min

有时候突然来了兴趣想练习下算法题，以下的算法题都是从各种博客和coderbyte上找来的。
coderbyte上的题目还是挺有意思的 (๑•̀ㅂ•́)و✧

虽然这些题目都比较基础，不过也有好些做不出来的，或者做出来了想的也有点复杂来着 ━(￣ー￣*|||━━

数组去重

这是很经典的算法题了。最开始我是这样写的：

1
2
3
4
5
6
7
8
9
10
11
12
13
var arr = [1,2,24,1,14,2,13];
function removal(arr){
	arr=arr.sort(function(a,b){
		return a-b;
	});
	var ret = [];
	for(var i = 0; i < arr.length; i++){
		if(arr[i] !== arr[i+1]){
			ret.push(arr[i]);
		}
	}
	return ret;
}

但是这样写有比较复杂，后来我改成了这样：

1
2
3
4
5
6
7
8
9
function removal(arr){
	var ret = [];
	for(var i = 0; i < arr.length; i++){
		if(ret.indexOf(arr[i]) == -1){
			ret.push(arr[i]);
		}
	}
	return ret;
}

还有一种方法：

1
2
3
4
5
6
7
8
9
10
11
12
function removal(arr){
	var ret = [];
	var obj = {};
	for (var j = 0; j < arr.length; j++) {
		var key = arr[j];
		if (!obj[key]) {
			obj[key] = 1;
			ret.push(key);
		}
	}
	return ret;
}

附上网上看到的用ES6新特性Set去重：

1
2
3
4
function remove2(arr){
	 return Array.from(new Set(arr));
}
var single2 = remove2(arr1);

判断字符串是否是回文

比如：redivider是回文

1
2
3
4
var str = "redivider";
function checkPalindrom(str) {
    return str == str.split('').reverse().join('');
}

字符串中出现最多的字母

比如：”afjghdfraaaasdenas”

1
2
3
4
5
6
7
8
9
10
11
12
13
var str1 = "afjghdfraaaasdenas";
var arr3 = str1.split('');
var obj = {},num = 0,ret2 = [];
for(var k = 0; k < arr3.length; k++){
	if(!obj[arr3[k]]){
		obj[arr3[k]] = 1;
		// num++;
	}
	obj[arr3[k]] ++;
	ret2.push(obj[arr3[k]]);
}
var max= Math.max.apply(null,ret2);
console.log(arr3[ret2.indexOf(max)]);

网上看到的其他方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function findMaxDuplicateChar(str) {
  if(str.length == 1) {
    return str;
  }
  let charObj = {};
  for(let i=0;i<str.length;i++) {
    if(!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    }else{
      charObj[str.charAt(i)] += 1;
    }
  }
  let maxChar = '',
      maxValue = 1;
  for(var k in charObj) {
    if(charObj[k] >= maxValue) {
      maxChar = k;
      maxValue = charObj[k];
    }
  }
  return maxChar;
}
module.exports = findMaxDuplicateChar;

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
function bubbleSort(arr) {
    for(var i = 0, l = arr.length; i < l-1; i++) {
        for(var j = i + 1; j < l; j++) {
          if(arr[i] > arr[j]) {
                let tem = arr[i];
                arr[i] = arr[j];
                arr[j] = tem;
            }
        }
    }
    return arr;
}

生成指定长度的斐波那契数列

例如：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]…

1
2
3
4
5
6
7
8
9
function drawfeibo(l){
	var arr = new Array;
	arr[0] = 0;
	arr[1] = 1;
	for(var i = 2; i < l; i++){
		arr[i] = arr[i-1] + arr[i-2];//
	}
	return arr;
}

获取正数组的最大差值

比如数组[10,5,11,7,8,9]，输出6

1
2
3
4
5
6
7
function getDvalue(arr){
	//var arr = [10,5,11,7,8,9];
	var max = Math.max.apply(null,arr);
	var min = Math.min.apply(null,arr);
	var D_value = max - min;
	return D_value;
}

随机生成指定长度的字符串

比如：给定长度 8 输出 4ldkfg9j

1
2
3
4
5
6
7
8
9
10
function getStr(l){
	var str = 'abcdefghijklmnopqrstuvwxyz9876543210';
	var arr = str.split(''),arr2 = [];
	for(var i = 0; i < l; i++){
		var temp = arr[Math.floor(Math.random() * arr.length)];
		arr2.push(temp);
	}
	var result = arr2.join('');
	return result;
}

网上看到的其他方法：

1
2
3
4
5
6
7
8
9
10
11
12
function randomString(n) {
  let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
  let tmp = '',
      i = 0,
      l = str.length;
  for (i = 0; i < n; i++) {
    tmp += str.charAt(Math.floor(Math.random() * l));
  }
  return tmp;
}

module.exports = randomString;

字符的左右移动

给定一个字符串，这个字符串为号和26个字母的任意组合。现在需要把字符串中的号都移动到最左侧，而把字符串中的字母移到最右侧并保持相对顺序不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var str = 'sosunn**afns*repsni*';
function sortstring(str){
		var arr = str.split('');
		var number = [], zimu = [];
		for(var i = 0; i < arr.length; i++){
			if(arr[i].charCodeAt()<=57){
				number.push(arr[i]);
			}else{
				zimu.push(arr[i]);
			}
		}
		var newstr = number.concat(zimu).join('');
		return newstr;
	}

网上看到的其他方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function sortstring(stars){
	var rs = stars.split('');
	var flag = 0;
	for(var i=rs.length -1; i>=0; i--){
			if(rs[i] == '*'){
					flag++;
			}else{
					if(flag == 0)
							continue;
					else{
							rs[i+flag] = rs[i];
							rs[i] = '*';
					}
			}
	}
	return rs.join(''); //****sosunnafnsrepsni
}

在一个字符串中找到第一个只出现一次的字符

如输入abaccdefbf，则输出d
我开始是这样想的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function getfirstchar(str){
	var arr=str.split('');
	var ret=[],arrnew=[];
	for(var i = 0; i < arr.length; i++){
		ret.push(arr[i].charCodeAt());//ASCII
	}
	ret = ret.sort();
	for(var k = 0; k < ret.length; k++){
		if(ret[k] != ret[k + 1]){
			arrnew.push(ret[k]);
		}
	}
	return String.fromCharCode(arrnew[0]));
}

不过后来感觉我的时间复杂度比较高，这是网上看到的其他方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var str = 'abaccdefbf';
var results = {};
var rs = str.split('');
rs.forEach(function(al){
		if(results[al] === undefined){
				results[al] = 1;
		}else{
				results[al]++;
		}
})
var keys = Object.keys(results);
for(var i = 0; i < keys.length; i++){
		if(results[keys[i]] === 1){
				console.log(keys[i]);
				break;
		}
}

返回句子中第一次出现的最长的单词

比如：’I love dogs ss’，返回 love；’fub&!!time’，返回time

1
2
3
4
5
6
7
8
9
10
11
function LongestWord(sen) {
    var pat = new RegExp("[`~!@#$^&*=+|{}\\[\\]()<>~@%#￥&*——|{}【】？]", 'g');
    var arr = sen.replace(pat,' ').split(' ');
	arr = arr.reverse();
	for(var n = 1; n < arr.length; n++){
		if(arr[n - 1].length >= arr[n].length){
			var result = arr[n - 1]
		}
	}
  return result;
}

从数组中移除

比如：destroyer([[1, 2, 3, 1, 2, 3], 2, 3])，输出[1,1]

1
2
3
4
5
6
7
8
9
10
11
function destroyer(array){
	var ret = array;
	var arr = [];
	for(var k = 0; k < array[0].length; k++){
		for(var j = 1; j < ret.length; j++){
			array[0].splice(array[0].indexOf(ret[j]),1);
		}
	}
	return array[0];
}
destroyer([[1, 2, 3, 1, 2, 3], 2, 3]);

输出一个数字的二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
function geterjinzhi(num){
	var index=0,
		number = parseInt(num,16).toString(2);
	var arr = number.split('');
	for(var k = 0; k < arr.length; k++){
		if(arr[k] == 1){
			index++;
		}
	}
	return index;
}

ArrayAdditionI

Have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.

比如： ArrayAddition([1, 22, 23, 25, 26]), 输出true，
ArrayAddition([1, 22, 23, 24, 27, 29, 33]), 输出false，
ArrayAddition([4, 6, 23, 10, 1, 3]), 输出true

这是很久之前写的代码，写的很复杂，我也不是很理解当时的脑回路了= = 大概类似于排列组合吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function ArrayAddition(arr){
 var max = Math.max.apply(null,arr);
 arr.splice(arr.indexOf(max),1)
 var num = 0, flag = false;
 function xunhuan(n,array){
	 if(n != max){
		 for(var m = 1; m < arr.length; m++){
			 for(var index = 0; index < array.length; index++){
				 if(array[array.length-1] + m < arr.length){
					 n += arr[array[array.length-1] + m];
					 array.push(array[array.length-1] + m);
					n = xunhuan(n,array);
				 }
			 }
		 }
	 }else{
		 flag = true;
	 }
	 return n;
 }
 for(var k = 1; k < arr.length; k++){
	 for(var i = 0; i < arr.length; i++){
			 var newarr = [];
			 num = arr[i] + arr[k];
			 newarr.push(i);
			 newarr.push(k);
			 num = xunhuan(num,newarr);
	 }
 }
 console.log('ArrayAddition',flag)
 return flag;
}

全排列

比如：if num = 4, return (4 * 3 * 2 * 1))

1
2
3
4
5
6
7
function FirstFactorial(num){
	var reslut = num;
	for(var k = 1; k < num; k++){
		reslut *= k;
	}
	return result;
	}

输入分钟输出时间显示

return the number of hours and minutes the parameter converts to (ie. if num = 63 then the output should be 1:3).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function TimeConvert(num) {
	var a = Math.floor(num/60) + 1,n = '';
	for(var i = 1; i <= a; i++){
		var b = i* 60;
		if( num > b){
			 n = num - b;
		}else{
			 n = num - 60 * (i-1);
		}
	}
	var str = (a-1) + ':' + n;
	return str;
}
TimeConvert(100);

return the string with the letters in alphabetical order

比如：ie. hello becomes ehllo.

1
2
3
4
5
6
7
8
9
10
11
12
13
function AlphabetSoup(str){
		var arr = str.split(''),ret = [],newarr = [];
		for(var i = 0; i < arr.length; i++){
			ret.push(arr[i].charCodeAt());
		}
		ret.sort(function(a,b){return a - b;});

		for(var k = 0; k < ret.length; k++){
			newarr.push(String.fromCharCode(ret[k]));
		}
		return newarr.join('');
	}
 AlphabetSoup('coderbyte');

the string to be true each letter must be surrounded by a + symbol

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function simplesymbols(str){
		var arr = str.split(''), html = false;
		if(arr[0].charCodeAt()>=97 || arr[arr.length - 1].charCodeAt()>=97){
			html = false;
		}else{
			var h = true;
			for(var i = 1; i < arr.length - 1; i++){
				if(arr[i].charCodeAt()>=97){
					if(arr[i - 1] === '+'){
						if(arr[i + 1] === '+'){
							html = true;
						}
					}
				}
				h = h && html;
			}
			html = h;
		}
		return html;
	}
 simplesymbols("=d+=3=+s+");

capitalize the first letter of each word

1
2
3
4
5
6
7
8
9
10
11
12
function lettercapitalize(str){
	var arr = str.split('');
	arr[0] = String.fromCharCode(arr[0].charCodeAt() - 32);
	for(var k = 0; k < arr.length-1; k++){
		if(arr[k] === ' '){
			arr[k+1] = String.fromCharCode(arr[k+1].charCodeAt() - 32);
		}
	}
	var newstr = arr.join('');
	return newstr;
}
lettercapitalize('hello world');

判断是不是质数

1
2
3
4
5
6
7
8
9
10
function isPrime(num){
	var html = true;
	for(var i = 2; i < num; i++){
		var n = num % i;
		if(n == 0){
			return  false;
		}
	}
	return html;
}
在刚刚的方法基础上获取质数因子
1
2
3
4
5
6
7
8
9
10
11
function primeFactors(num){
	var arr = [];
	for(var i = 2; i < num; i++){
		if(num % i == 0){
			if(isPrime(i)){
				arr.push(i);
			}
		}
	}
	return arr;
}

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function greatestCommonDivisor(num1,num2){
	var num = num1;
	if(num1 > num2){
		 num = num2;
	}
	var arr = [];
	for(var i = 2; i < num; i++){
		if(num % i == 0){
			arr.push(i);
		}
	}
	var max = Math.max.apply(null,arr);
	return max;
}

输入两个数组，得到不在另一个数组中的值组成的新数组

列如：[1, 2, 3, 5], [1, 2, 3, 4, 5] return [4]
[1, “calf”, 3, “piglet”],[1, “calf”, 3, 4] return [“piglet”,’4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function getUniqueFromnArr(arr1,arr2){
	var ret = [];
	var array = [arr1,arr2].sort(function(a,b){return a.length-b.length});
	for(var i = 0; i < array[0].length; i++){
		if(array[0].indexOf(array[1][i]) == -1){
			ret.push(array[1][i]);
		}
		if(array[1].indexOf(array[0][i]) == -1){
			ret.push(array[0][i]);
		}
	}
	for(var k = array[0].length; k < array[1].length; k++){
		if(array[0].indexOf(array[1][k]) == -1){
			ret.push(array[1][i]);
		}
	}
	return ret;
}

另一个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function diff(arr1, arr2) {
	var newArr = [];
	//过滤数组1中与数组2相等的项
	var arr1Filtered=arr1.filter(function(num){
		for(var i=0; i<arr2.length; i++){
			if(num==arr2[i]){
				return false;
			}
		}
		return true;
	});
	//过滤数组2中与数组1相等的项
	var arr2Filtered=arr2.filter(function(num){
		for(var i=0; i<arr1.length; i++){
			if(num==arr1[i]){
				return false;
			}
		}
		return true;
	});
	//连接两个数组
	newArr=arr1Filtered.concat(arr2Filtered);
	return newArr;
}

判断两个Object是不是相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function ObjectEqual(obj1,obj2){
	if(typeof obj1 == 'object' && typeof obj2 == 'object'){
		var count = 0,len = Object.keys(obj1).length;
		if(len == Object.keys(obj2).length){
			for(var key in obj1){
				if(typeof obj2[key] != 'undefined'){
					if(obj1[key] == obj2[key]){
						count ++;
					}else{
						return false;
					}
				}
			}
			if(len == count){
				return true;
			}
		}
	}
	return false;
}

网上看到的另一个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function where(collection, source) {
	var arr = [];
	var porp=Object.keys(source);
	arr=collection.filter(function(obj){
		for(var i=0; i<porp.length; i++){
			if(obj[porp[i]]!==source[porp[i]]){
				//判断参数1中各个对象的porp属性的值是否与参数二中的porp属性值相等
				return false;
			}
		}
		return true;
	});
	return arr;
}

找到字符串中缺失的字母

1
2
3
4
5
6
7
8
9
10
11
12
13
function fearNotLetter(str){
	var arr = str.split(""),ret=[];
	for(var i = 0; i < arr.length; i++){
		arr[i] = arr[i].charCodeAt();
	}
	arr = arr.sort(function(a,b){a-b});
	for(var k = arr[0]; k < arr[arr.length-1]; k++){
		if(arr.indexOf(k) == -1){
			ret.push(String.fromCharCode(k));
		}
	}
	return ret;
}

另一个方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function fearNotLetter(str) {
	//将字符串转为ASCII码，并存入数组
	var arr=[];
	for(var i=0; i<str.length; i++){
		arr.push(str.charCodeAt(i));
	}
	for(var j=1; j<arr.length; j++){
		var num=arr[j]-arr[j-1];
		//判断后一项减前一项是否为1，若不为1，则缺失该字符的前一项
		if(num!=1){
			//将缺失字符ASCII转为字符并返回
			return String.fromCharCode(arr[j]-1);
		}
	}
	return undefined;
}

获取多个数组的组合数组并去重

比如：getSortAndUniteArr([1, 3, 2], [5, 2, 1, 4], [2, 1]) return [1, 3, 2, 5, 4]

1
2
3
4
5
6
7
8
9
10
11
12
function getSortAndUniteArr(arr1,...arr3){
	var ret = [],obj = {};
	var arr = arr1.concat(...arr3);
	for (var i = 0; i < arr.length; i++) {
		var k = arr[i];
		if(!obj[k]){
			obj[k] = 1;
			ret.push(k);
		}
	}
	return ret;
}

网上看到的另一个方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function unite(arr1, arr2, arr3) {
	  for(var j=1; j<arguments.length; j++){
	    //过滤掉第j个数组中已经在前面出现过的值
	    var filteredArr=arguments[j].filter(function(num){
	      for(var i=0; i<arr1.length; i++){
	        if(arr1[i]==num){
	          return false;
	        }
	      }
	      return true;
	    });
	    arr1=arr1.concat(filteredArr);
	  }
	  return arr1;
	}

参考

https://www.cnblogs.com/lvmylife/p/7208541.html

https://coderbyte.com

https://blog.csdn.net/crystal6918/article/details/60955989

-------------完结撒花 -------------

本文标题:JS算法

文章作者:咕噜咕噜

发布时间:2018年03月26日

最后更新:2022年07月19日

原始链接:https://aartemida.github.io/2018/03/26/JS算法/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。