算法题汇总
- 编写一个数组去重的方法
function oSort(arr) {
var newArr = [];
for(var i = 0; i < arr.length; i++) {
if(newArr.indexOf(arr[i]) < 0){
newArr.push(arr[i]);
}
}
return newArr;
}
- 统计字符串中字母个数并统计最多字母数
//思路：构建字面量对象
var obj = {a: 1, b: 2};
obj['c'] = 3;
for (o in obj) {
console.log(o +" = "+ obj[o]);
}
//输出结果：
//a = 1;
//b = 2;
//c = 3;
//示例
var str = "aaxxxxxbocjacjaadjadx";
var obj = {};
var maxCount = 0;
for (i = 0; i < str.length; i++) {
var chat = str.charAt(i);
if(obj[chat]){
obj[chat] = ++obj[chat];
//记录出现最多的次数
if(obj[chat] > maxCount){
maxCount = obj[chat];
}
}else{
obj[chat] = 1;
}
}
for(o in obj){
//输出字母及其出现的次数
console.log(o +" = "+ obj[o]);
if(obj[o] == maxCount){
//输出出现次数最多的字母和次数
console.log("出现次数最多的字母：" + o +" = "+ obj[o]);
}
}
//另外一种较复杂的写法
//思路：同样是构造字面量对象，但是是对象中嵌套对象
var obj = {a:{value: 'a',count: 3}, b:{value: 'b', count:4}}
for(key in obj) {
console.log(obj[key].value + '=' + obj[key].count);
}
//示例
var str = "aaxxbocjacjaadjadx";
var obj = {};
for (i = 0; i < str.length; i++) {
var chat = str.charAt(i);
if(obj[chat] && obj[chat].key == chat){
obj[chat].count = ++obj[chat].count;
}else{
obj[chat] = {};
obj[chat].key = chat;
obj[chat].count = 1;
}
}
for(o in obj){
console.log(obj[o].key +" = "+ obj[o].count);
}
3.快速排序
"快速排序"的整个过程只需要三步：
（1）在数据集之中，选择一个元素作为"基准"（pivot）。
（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
function quickSort(arr) {
if(arr.length <= 1) {
return arr;
}
//从中间选择一个元素作为"基准"
var pivotIndex = Math.floor(arr.length / 2);
//arr变成除去基准值的数据
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for(var i = 0; i < arr.length; i++) {
if(arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
//递归调用直至排序完成
return quickSort(left).concat([pivot], quickSort(right));
};
var arr = [9,1,5,3,7,5,9];
console.log(quickSort(arr));
//输出：1,3,5,5,7,9,9
4.冒泡排序
正向冒泡排序算法：
（1）对比第一项和第二项，如果第一项大于第二项，交换他们；
（2）对比第二项和第三项，如果第二项大于第三项，交换他们；
（3）以此类推直到数据结束，这样最后一项就是其中最大的值；
（4）然后排除掉最后一项，重复1、2、3步骤，直到全部排序完成；
//正向冒泡排序算法
function bubbleSort(arr){
var len = arr.length;
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 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 = [6,3,5,4,7,1,2];
console.log(bubbleSort(arr));
//输入结果：1,2,3,4,5,6,7
反向冒泡排序算法：
（1）对比第一项和第二项，如果第一项小于第二项，交换他们；
（2）对比第二项和第三项，如果第二项小于第三项，交换他们；
（3）以此类推直到数据结束，这样最后一项就是其中最小的值；
（4）然后排除掉最后一项，重复1、2、3步骤，直到全部排序完成；
//反向冒泡排序算法
function bubbleSort(items) {
var len = items.length;
for(var i = 0; i < len; i++) {
for(var j = 0; j <= len - i - 1; j++) {
if(items[j] < items[j + 1]) {
var temp = items[j + 1];
items[j + 1] = items[j];
items[j] = temp;
}
}
}
return items;
}
var arr = [6,3,5,4,7,1,2];
console.log(bubbleSort(arr));
//输入结果：7,6,5,4,3,2,1
5.利用sort() 函数进行排序
直接使用时不稳定，因为其不会按照数值的大小对数字进行排序，而是按照字符编码的顺序进行排序，如下：
var arr = [1,7,3,8,2,9,0,1,11];
console.log(arr.sort());
//输入结果：0,1,1,11,2,3,7,8,9
要实现按照数值的大小对数字进行排序，需要使用一个排序函数，如下：
//正序排列
var arr = [1,7,3,8,2,9,0,1,11];
function quickSort(a, b){
return a - b;
}
console.log(arr.sort(quickSort));
//输入结果：0,1,1,2,3,7,8,9,11
//倒序排列
var arr = [1,7,3,8,2,9,0,1,11];
function quickSort(a, b){
return b - a;
}
console.log(arr.sort(quickSort));
//输入结果：11,9,8,7,3,2,1,1,0
6.二分法查找
二分法查找，也称折半查找，是一种在有序数组 中查找特定元素的搜索算法。查找过程可以分为以下步骤：
（1）首先，从有序数组的中间的元素开始搜索，如果该元素正好是目标元素（即要查找的元素），则搜索过程结束，否则进行下一步。
（2）如果目标元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作。
（3）如果某一步数组为空，则表示找不到目标元素。
-
非递归算法
function binary_search(arr, key) { var low = 0; var high = arr.length - 1; while(low <= high) { var mid = parseInt((high + low) / 2); if(key == arr[mid]) { return mid; } else if(key > arr[mid]) { low = mid + 1; } else if(key < arr[mid]) { high = mid - 1; } else { return -1; } } }; var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 23, 44, 86]; var result = binary_search(arr, 44); console.log(result +"--"+ arr[result]); -
递归算法
function binary_search(arr, low, high, key) { if(low > high) { return -1; } var mid = parseInt((high + low) / 2); if(arr[mid] == key) { return mid; }else if(arr[mid] > key) { high = mid - 1; return binary_search(arr, low, high, key); }else if(arr[mid] < key) { low = mid + 1; return binary_search(arr, low, high, key); }else{ return -1; } }; var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 23, 44, 86]; var result = binary_search(arr, 0, 13, 10); console.log(result +"--"+ arr[result]);
