雖說我們很多時候前端很少有機會接觸到算法,但對算法的理解和掌握是一個優(yōu)秀工程師的評價標準之一,而且當我們面對較為復雜的問題,這些基礎知識的積累可以幫助我們更好的優(yōu)化解決思路。在一段時間的學習之后,我總結羅列了前端中常見見的幾個算法:
一:排序算法
排序算法是比較開發(fā)的算法之一,方法種類較多,在此列舉兩種簡單的排序算法:冒泡排序和快速排序。冒泡排序其實就是通過比較相鄰位置的元素大小,如果左邊比右邊大,就交換位置,繼續(xù)比較,實際上就是每輪比較都得出一個最大值(或者最小值)。然后通過n-1輪比較,就能得出一個排好序的序列(通過設置一個flag,當數(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;
}
快速排序簡單來講就是我們選定一個數(shù),然后比它小的都放在它左邊,大于等于它的都放在它右邊,那么這個時候對這個數(shù)來講他的位置已經(jīng)排到了正確的地方了,接下來要做的就是在它的左右兩邊分別再進行類似操作。
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;
//遞歸調用
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;
}
三:回文字符串判斷
如果一個字符串忽略標點符號、大小寫和空格,正著讀和反著讀一模一樣,那么這個字符串就是palindrome(回文)。
function palindrome(str) {
// 刪除字符串中不必要的字符
var re = /[W_]/g;
// 將字符串變成小寫字符
var lowRegStr = str.toLowerCase().replace(re, '');
// 如果字符串lowRegStr的length長度為0時,字符串即是palindrome
if (lowRegStr.length === 0) {
return true;
}
// 如果字符串的第一個和最后一個字符不相同,那么字符串就不是palindrome
if (lowRegStr[0] !== lowRegStr[lowRegStr.length - 1]) {
return false;
} else {
return palindrome(lowRegStr.slice(1, lowRegStr.length - 1));
}
}
四:翻轉字符串算法
function reverseString(str) {
var tmp = "";
for (var i = str.length - 1; i >= 0; i--) {
tmp += str.charAt(i);
}
return tmp;
}
第二種翻轉字符串算法:
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ù)組去重算法
主要考察程序員對Object的使用,利用key來進行篩選。
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;
}
七:隨機指定長度字符串
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)計字符串中次數(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ù)列,指的是這樣一個數(shù)列:0、1、1、2、3、5、8、13、21、34、……在數(shù)學上,斐波納契數(shù)列主要考察遞歸的調用。通過定義fibo = fibo[i-1]+fibo[i-2];來生成斐波那契數(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;
}
以上幾個前端中經(jīng)常會出現(xiàn)的小算法是學習中的練習和總結,整理此文如果有錯誤希望小伙伴們積極指正,有更好更簡潔的算法知識也希望不吝分享,以求共同進步。
作者:
黑馬程序員前端與移動開發(fā)培訓學院首發(fā):
http://cloud.itheima.cn/