算法題匯總
- 編寫一個數(shù)組去重的方法
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;
}
- 統(tǒng)計字符串中字母個數(shù)并統(tǒng)計最多字母數(shù)
//思路：構(gòu)建字面量對象
var obj = {a: 1, b: 2};
obj['c'] = 3;
for (o in obj) {
console.log(o +" = "+ obj[o]);
}
//輸出結(jié)果：
//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];
//記錄出現(xiàn)最多的次數(shù)
if(obj[chat] > maxCount){
maxCount = obj[chat];
}
}else{
obj[chat] = 1;
}
}
for(o in obj){
//輸出字母及其出現(xiàn)的次數(shù)
console.log(o +" = "+ obj[o]);
if(obj[o] == maxCount){
//輸出出現(xiàn)次數(shù)最多的字母和次數(shù)
console.log("出現(xiàn)次數(shù)最多的字母：" + o +" = "+ obj[o]);
}
}
//另外一種較復(fù)雜的寫法
//思路：同樣是構(gòu)造字面量對象，但是是對象中嵌套對象
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）在數(shù)據(jù)集之中凝危，選擇一個元素作為"基準(zhǔn)"（pivot）波俄。
（2）所有小于"基準(zhǔn)"的元素，都移到"基準(zhǔn)"的左邊蛾默；所有大于"基準(zhǔn)"的元素懦铺，都移到"基準(zhǔn)"的右邊。
（3）對"基準(zhǔn)"左邊和右邊的兩個子集支鸡，不斷重復(fù)第一步和第二步冬念，直到所有子集只剩下一個元素為止。
function quickSort(arr) {
if(arr.length <= 1) {
return arr;
}
//從中間選擇一個元素作為"基準(zhǔn)"
var pivotIndex = Math.floor(arr.length / 2);
//arr變成除去基準(zhǔn)值的數(shù)據(jù)
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]);
}
}
//遞歸調(diào)用直至排序完成
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）對比第一項(xiàng)和第二項(xiàng)牧挣，如果第一項(xiàng)大于第二項(xiàng)急前，交換他們；
（2）對比第二項(xiàng)和第三項(xiàng)瀑构，如果第二項(xiàng)大于第三項(xiàng)裆针，交換他們；
（3）以此類推直到數(shù)據(jù)結(jié)束寺晌，這樣最后一項(xiàng)就是其中最大的值世吨；
（4）然后排除掉最后一項(xiàng)，重復(fù)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));
//輸入結(jié)果：1,2,3,4,5,6,7
反向冒泡排序算法：
（1）對比第一項(xiàng)和第二項(xiàng)沐祷，如果第一項(xiàng)小于第二項(xiàng)，交換他們攒岛；
（2）對比第二項(xiàng)和第三項(xiàng)赖临，如果第二項(xiàng)小于第三項(xiàng)，交換他們灾锯；
（3）以此類推直到數(shù)據(jù)結(jié)束思杯，這樣最后一項(xiàng)就是其中最小的值；
（4）然后排除掉最后一項(xiàng)，重復(fù)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));
//輸入結(jié)果：7,6,5,4,3,2,1
5.利用sort() 函數(shù)進(jìn)行排序
直接使用時不穩(wěn)定案怯，因?yàn)槠洳粫凑諗?shù)值的大小對數(shù)字進(jìn)行排序，而是按照字符編碼的順序進(jìn)行排序澎办，如下：
var arr = [1,7,3,8,2,9,0,1,11];
console.log(arr.sort());
//輸入結(jié)果：0,1,1,11,2,3,7,8,9
要實(shí)現(xiàn)按照數(shù)值的大小對數(shù)字進(jìn)行排序嘲碱，需要使用一個排序函數(shù)，如下：
//正序排列
var arr = [1,7,3,8,2,9,0,1,11];
function quickSort(a, b){
return a - b;
}
console.log(arr.sort(quickSort));
//輸入結(jié)果：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));
//輸入結(jié)果：11,9,8,7,3,2,1,1,0
6.二分法查找
二分法查找局蚀，也稱折半查找麦锯，是一種在有序數(shù)組 中查找特定元素的搜索算法。查找過程可以分為以下步驟：
（1）首先琅绅，從有序數(shù)組的中間的元素開始搜索扶欣，如果該元素正好是目標(biāo)元素（即要查找的元素），則搜索過程結(jié)束千扶，否則進(jìn)行下一步料祠。
（2）如果目標(biāo)元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半?yún)^(qū)域查找澎羞，然后重復(fù)第一步的操作髓绽。
（3）如果某一步數(shù)組為空，則表示找不到目標(biāo)元素妆绞。
-
非遞歸算法
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]);?
