前端中經(jīng)常出現(xiàn)的算法總結(jié)

雖說(shuō)我們很多時(shí)候前端很少有機(jī)會(huì)接觸到算法，但對(duì)算法的理解和掌握是一個(gè)優(yōu)秀工程師的評(píng)價(jià)標(biāo)準(zhǔn)之一，而且當(dāng)我們面對(duì)較為復(fù)雜的問(wèn)題，這些基礎(chǔ)知識(shí)的積累可以幫助我們更好的優(yōu)化解決思路。在一段時(shí)間的學(xué)習(xí)之后，我總結(jié)羅列了前端中常見(jiàn)見(jiàn)的幾個(gè)算法：

一：排序算法

排序算法是比較開(kāi)發(fā)的算法之一，方法種類較多，在此列舉兩種簡(jiǎn)單的排序算法：冒泡排序和快速排序。冒泡排序其實(shí)就是通過(guò)比較相鄰位置的元素大小，如果左邊比右邊大，就交換位置，繼續(xù)比較，實(shí)際上就是每輪比較都得出一個(gè)最大值（或者最小值）。然后通過(guò)n-1輪比較，就能得出一個(gè)排好序的序列（通過(guò)設(shè)置一個(gè)flag，當(dāng)數(shù)組基本有序的時(shí)候其實(shí)不一定需要比較到n-1輪）。

function bubbleSort(arr){
     for(var i=1;i<arr.length;i++){
         for(var j=0;j<arr.length-i;j++){
             var temp;
             if(arr[j]>arr[j+1]){
                 temp=arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=temp;
             }
         }
     }
     return arr;
}

快速排序簡(jiǎn)單來(lái)講就是我們選定一個(gè)數(shù)，然后比它小的都放在它左邊，大于等于它的都放在它右邊，那么這個(gè)時(shí)候?qū)@個(gè)數(shù)來(lái)講他的位置已經(jīng)排到了正確的地方了，接下來(lái)要做的就是在它的左右兩邊分別再進(jìn)行類似操作。

function quickSort(arr,l,r){
    var i,j,x;
    if(l<r){
        i=l;
        j=r;
        x=arr;
        while(i<j){
            while(i<j&&arr[j]>=x){
                j--;
            }
            if(i<j){
                arr=arr[j];
            }
            while(i<j&&arr<x){
                i++;
            }
            if(i<j){
                arr[j]=arr;
            }
        }
        arr=x;
        //遞歸調(diào)用
        quickSort(arr,i+1,r);
        quickSort(arr,l,i-1);
    }
    return arr;
}


二：階乘算法

function factorialize(num) {
    var result = num;
    if (num < 0) {
        return -1;
    } else if (num === 0 || num === 1) {
        return 1;
    } else {
        while (num > 1) {
            num--;
            result *= num;
        }
    }
    return result;
}


三：回文字符串判斷

如果一個(gè)字符串忽略標(biāo)點(diǎn)符號(hào)、大小寫和空格，正著讀和反著讀一模一樣，那么這個(gè)字符串就是palindrome(回文)。

function palindrome(str) {
    // 刪除字符串中不必要的字符
    var re = /[W_]/g;
    // 將字符串變成小寫字符
    var lowRegStr = str.toLowerCase().replace(re, '');
    // 如果字符串lowRegStr的length長(zhǎng)度為0時(shí)，字符串即是palindrome
    if (lowRegStr.length === 0) {
        return true;
    }
    // 如果字符串的第一個(gè)和最后一個(gè)字符不相同，那么字符串就不是palindrome
    if (lowRegStr[0] !== lowRegStr[lowRegStr.length - 1]) {
        return false;
    } else {
        return palindrome(lowRegStr.slice(1, lowRegStr.length - 1));
    }
}


四：翻轉(zhuǎn)字符串算法

function reverseString(str) { 
    var tmp = ""; 
    for (var i = str.length - 1; i >= 0; i--) { 
        tmp += str.charAt(i); 
    } 
    return tmp; 
} 
第二種翻轉(zhuǎn)字符串算法：

function reverseString(s) {
    var arr = s.split('');
    var i = 0, j = arr.length - 1;
    while (i < j) {
        var t = arr;
        arr = arr[j];
        arr[j] = t;
        i++;
        j--;
    }
    return arr.join('');
}


五：整型數(shù)組去重算法

主要考察程序員對(duì)Object的使用，利用key來(lái)進(jìn)行篩選。

function unique(arr) 
     var hashTable = {};
     var data = [];
     for(var i = 0, l = arr.length; i < l; i++) {
         if(!hashTable[arr]) {
             hashTable[arr] = true;
             data.push(arr);
         }
     }
     return data;
}

六：數(shù)組中最大差值

function getMaxProfit(arr) {
    var minPrice = arr[0];
    var maxProfit = 0;
    for (var i = 0; i < arr.length; i++) {
        var currentPrice = arr;
        minPrice = Math.min(minPrice, currentPrice);
        var potentialProfit = currentPrice - minPrice;
        maxProfit = Math.max(maxProfit, potentialProfit);
    }
    return maxProfit;
}

七：隨機(jī)指定長(zhǎng)度字符串

function randomString(n) {
    var str = 'abcdefghijklmnopqrstuvwxyz9876543210';
    var tmp = '';
    var l = str.length;
    for(var i = 0; i < n; i++) {
        tmp += str.charAt(Math.floor(Math.random() * l));
    }
    return tmp;
}

八：統(tǒng)計(jì)字符串中次數(shù)最多字母

function findMaxDuplicateChar(str) {
    if(str.length == 1) {
        return str;
    }
    var charObj = {};
    for(var i = 0; i < str.length; i++) {                       
        if(!charObj[str.charAt(i)]) {
            charObj[str.charAt(i)] = 1;
        } else {
            charObj[str.charAt(i)] += 1;
        }
    }
    var maxChar = '',
        maxValue = 1;
    for(var k in charObj) {
        if(charObj[k] >= maxValue) {
            maxChar = k;
            maxValue = charObj[k];
        }
    }
    return maxChar;
}

九：生成菲波那切數(shù)列數(shù)組

斐波那契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列主要考察遞歸的調(diào)用。通過(guò)定義fibo = fibo[i-1]+fibo[i-2];來(lái)生成斐波那契數(shù)組。

function getFibonacci(n) {
    var fibarr = [];
    var i = 0;
    while(i < n) {
        if(i <= 1) {
            fibarr.push(i);
        } else {
            fibarr.push(fibarr[i - 1] + fibarr[i - 2])
        }
        i++;
    }
    return fibarr;
}
以上幾個(gè)前端中經(jīng)常會(huì)出現(xiàn)的小算法是學(xué)習(xí)中的練習(xí)和總結(jié)，整理此文如果有錯(cuò)誤希望小伙伴們積極指正，有更好更簡(jiǎn)潔的算法知識(shí)也希望不吝分享，以求共同進(jìn)步。

作者：黑馬程序員前端與移動(dòng)開(kāi)發(fā)培訓(xùn)學(xué)院
首發(fā)：http://cloud.itheima.cn/