這次騰訊面試的失利，讓我深刻明白了這一點：想進大公司，必須把算法學(xué)習好。為此開一篇文章，記錄下面試過程中經(jīng)常會出現(xiàn)的算法筆試題。

Q1. 去掉一組整型數(shù)組中重復(fù)的值

該題目的解法有好幾種，下面列舉幾種常見的解法。

Object.assign(Array.prototype, {
    unique() {
        let newArr = [this[0]]; 
        for(let i of Object.keys(this)) {
            let value = this[i];
            if (newArr.indexOf(value) === -1) {
                newArr.push(value);
            }
        }
        return newArr;
    }
});

上面那種解法是我們最容易想到的解法，在查找重復(fù)元素的過程中使用了indexOf方法，如果不使用的話，也可以使用循環(huán)解決如下：

Object.assign(Array.prototype, {
    unique() {
        let newArr = [this[0]]; 
        for(let i of Object.keys(this)) {
            let value1 = this[i];
            let repeat = false;
            for(let j of Object.keys(newArr)) {
                let value2 = newArr[j];
                if (value1 === value2) {
                    repeat = true;
                    break;
                }
            }
            if (!repeat) {
                newArr.push(value1);
            }
        }
        return newArr;
    }
});

除了使用indexOf和循環(huán)去重，我們還可以使用Object對象判斷是否重復(fù)，下面這種解法是作者比較推薦的一種解法。

Object.assign(Array.prototype, {
    unique() {
        let newArr = [this[0]]; 
        let obj = {
            [this[0]]: true
        };
        for(let i of Object.keys(this)) {
            let value = this[i];
            if (obj[value] === undefined) {
                obj[value] = true;
                newArr.push(value);
            }
        }
        return newArr;
    }
});

最后還有一種方法，使用了sort（）對數(shù)組進行了排序，這樣去重之后原數(shù)組的索引對應(yīng)元素的值都發(fā)生的變化，如果不考慮這一點，可以使用這種解決方案。

Object.assign(Array.prototype, {
    unique() {
        this.sort();
        let newArr = [this[0]]; 
        for(let i of Object.keys(this)) {
            let value = this[i];
            if (value !== newArr[newArr.length - 1]) {
                newArr.push(value);
            }
        }
        return newArr;
    }
});

Q2. 統(tǒng)計一個字符串出現(xiàn)最多的字母

其實就是統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù)，最后從中找到出現(xiàn)次數(shù)最多的字符。

Object.assign(String.prototype, {
    findMaxDuplicateChar() {
        if (str.length == 1) {
            return str;
        } 
        let charObj = {};
        for(let i of Object.keys(this)) {
            let c = this[i];
            if (charObj[c] === undefined) {
                charObj[c] = 1;
            } else {
                charObj[c]++;
            }
        }
        let maxChar = '';
        let maxNum = 0;
        for(let i of Object.keys(charObj)) {
            let num = charObj[i];
            if (num > maxNum) {
                maxNum = num;
                maxChar = i;
            }
        }
        return maxChar;
    }
});

Q3. 排序算法

冒泡排序

Object.assign(Array.prototype, {
    bubbleSort() {
        for(let i = 0, l = this.length;i < l - 1;i++) {
            for (let j = i + 1;j < l - 1;j++) {
                if (this[i] > this[j]) {
                    [this[i], this[j]] = [this[j], this[i]];
                }
            }
        }
    }
});

快速排序

let quickSort = arr => {
    if (arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor((arr.length - 1) / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i of Object.keys(arr)) {
        let v = arr[i];
        if (v <= pivot) {
            left.push(v);
        } else {
            right.push(v);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

插入排序

let searchIndex = (arr, x) => {
    if (x <= arr[0]) {
        return 0;
    }
    if (x >= arr[arr.length - 1]) {
        return arr.length;
    }
    let i = 0;
    for (;i < arr.length;i++) {
        if (arr[i] <= x && x <= arr[i+ 1] ) {
            break;
        }
    }
    return i + 1;
}
let insertSort = arr => {
    let sortArr = [arr[0]];
    for (let i = 1;i < arr.length;i++) {
        let index = searchIndex(sortArr, arr[i]);
        sortArr.splice(index, 0, arr[i]);
    }
    return sortArr;
}

Q4. 斐波那契數(shù)列

斐波那契數(shù)列就是形如0,1,1,2,3,5,8.....的數(shù)列。

let getFibonacci = n => {
    let arr = [];
    for(let i = 0;i < n - 1;i++) {
        if (i <= 1) {
            arr.push(i);
        } else {
            arr.push(arr[i - 1] + arr[i - 2]);
        }
    }
    return arr;
}

Q5. 速度創(chuàng)建1-100的數(shù)組

ES5的寫法

var a = Array.prototype.map.call(Array(101).join('0').split(''), function() {
    return arguments[1] + 1;
});

ES6的寫法

let arr = Array.from(Array(100), (value, index) => index + 1);//from會將空位轉(zhuǎn)成undefined
//或者
let arr = Array.from({length: 100}, (value, index) => index + 1);

Q6. 洗牌算法

這道題是我去富途面試CTO問我的一道題，我聽到之后一臉懵比（后面的題目也做的不好），結(jié)果直接game over，面試之后查閱了下百度自己寫了出來

let swap = a => {
  let b = [];
  for(var i = a.length;i > 0;) {
        var index = Math.floor(Math.random() * i);
    b.push(a[index]);
    a[index] = a[--i];
  }
  return b;
}