面试发现自己的算法知识有不足，因此参考了多篇文章学习总结。

 

冒泡排序

 

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

 

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

 

针对所有的元素重复以上的步骤，除了最后一个。

 

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

 

冒泡排序最好的时间复杂度为O(n),是一种稳定排序算法。

 

let arr = [16, 31, 12, 1, 9, 12, 10];

 

function bubbleSort (arr) {

 

    let len = arr.length;

 

    for (let i = 0; i < len - 1; i++){

 

        for (let j = 0; j < len - 1 - i; j++){

 

            if (arr[j] > arr[j+1]){

 

                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]

 

            }

 

        }

 

    }

 

    return arr;

 

}

 

bubbleSort(arr);

 

2. 快速排序

 

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

 

快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。快速排序的平均时间复杂度为O（n×log（n））

 

let arr = [16, 31, 12, 1, 9, 12, 10];

 

function quickSort (arr) {

 

    if (arr.length <= 1){

 

return arr;

 

    }

 

let middleIndex = Math.floor(arr.length / 2);

 

let middle = arr.splice(middleIndex, 1);

 

let left = [];

 

let right = [];

 

arr.forEach(v => {

 

if(v < middle) {

 

left.push(v);

 

} else {

 

right.push(v);

 

}

 

})

 

return quickSort(left).concat(middle, quickSort(right));

 

}

 

quickSort(arr1);

 

3. 不指定算法的数组排序

 

let arr = [16, 31, 12, 1, 9, 12, 10];

 

arr.sort((a, b) => a - b); // 从小到大

 

4. 找出整型数组中乘积最大的三个数

 

let unsortedArray = [-10, 7, 29, 30, 5, -10, -70];

 

// 乘积最大的只有可能是两种情况：

 

// 1. 最大的三个数的乘积

 

// 2. 最大的数和最小的两个数的乘积

 

function multiply (unSortedArr) {

 

    let arr = unSortedArr.sort((a, b) => a - b);

 

    let len = arr.length;

 

    let result1 = arr[len - 1] * arr[len - 2] * arr[len - 3];

 

    let result2 = arr[len - 1] * arr[0] * arr[1];

 

    return result1 > result2 ? result1 : result2;

 

}

 

multiply(unsortedArray);

 

5. 寻找连续数组中的缺失数

 

给定某无序数组，其包含了 n 个连续数字中的 n - 1 个，已知上下边界，要求以O(n)的复杂度找出缺失的数字。

 

const arrayOfIntegers = [2, 5, 1, 4, 9, 6, 3, 7];

 

const upperBound = 9;

 

const lowerBound = 1;

 

function findMissingNumber(arr, upper, lower) {

 

  // 计算当前数组的和

 

  // 这里用了 reduce

 

  const sumOfArr = arr.reduce((pre, cur) => pre + cur, 0);

 

  // 以高斯求和公式计算理论上的数组和

 

  // 高斯求和公式：[(N * (N + 1)) / 2] - [(M * (M - 1)) / 2];

 

  // N 是上边界，M 是下边界

 

  const theoreticalSum = (upper * (upper + 1)) / 2 - (lower * (lower - 1)) / 2;

 

  return theoreticalSum - sumOfArr; // 理论和减实际和求出丢失的数字

 

}

 

findMissingNumber(arrayOfIntegers, upperBound, lowerBound); //8

 

6. 数组去重

 

给定某无序数组，要求去除数组中的重复数字并且返回新的无重复数组。

 

const arr = [1, 2, '1', null, undefined, null, undefined]

 

// ES6 Set 和 Spread 操作符

 

function uniqueArray (arr) {

 

  return [...new Set(arr)]

 

}

 

// ES5

 

function uniqueArray (arr) {

 

  return arr.filter((v, i) => arr.indexOf(v) === i)

 

}

 

uniqueArray(arr) // [1, 2, '1', null, undefined]

 

7. 数组中元素最大差值计算

 

给定某无序数组，求取任意两个元素之间的最大差值，注意，这里要求差值计算中较小的元素下标必须小于较大元素的下标。譬如[7, 8, 4, 9, 9, 15, 3, 1, 10]这个数组的计算值是 11 ( 15 - 4 ) 而不是 14 (15 - 1)，因为 15 的下标小于 1。

 

const arr = [7, 8, 4, 9, 9, 15, 3, 1, 10]

 

function findLargestDifference(array) {

 

  const len = array.length

 

  // 如果数组仅有一个元素，则直接返回 -1

 

  if (len <= 1) return -1

 

  // current_min 指向当前的最小值

 

  let currentMin = array[0]

 

  let currentMaxDifference = 0

 

  let i = 1

 

  // 遍历整个数组以求取当前最大差值，如果发现某个最大差值，则将旧的值覆盖

 

  // 同时也会追踪当前数组中的最小值

 

  while (i < len) {

 

    const cur = array[i]

 

    if (cur > currentMin && (cur - currentMin > currentMaxDifference)) {

 

      currentMaxDifference = cur - currentMin

 

    } else if (cur <= currentMin) {

 

      currentMin = cur

 

    }

 

    i++

 

  }

 

  return currentMaxDifference

 

}

 

findLargestDifference(arr) // 11

 

8. 数组交集

 

给定两个数组，要求求出两个数组的交集，注意，交集中的元素应该是唯一的。

 

const firstArray = [2, 2, 4, 1]

 

const secondArray = [1, 2, 0, 2]

 

function intersection(arr1, arr2) {

 

  const hashmap = {}

 

  const intersectionArray = []

 

  arr1.forEach(v => {

 

    hashmap[v] = 1

 

  })

 

  arr2.forEach(v => {

 

    if (hashmap[v] === 1) {

 

      intersectionArray.push(v)

 

      hashmap[v]++

 

    }

 

  })

 

  return intersectionArray

 

}

 

intersection(firstArray, secondArray) // [1, 2]

 

9. 回文字符串的判定

 

function isPalindrome(word) {

 

  return word === word.split('').reverse().join('')

 

}

 

isPalindrome('racecar') // true

 

10. 使用两个栈实现入队与出队

 

function Queue () {

 

  this.inputStack = []

 

  this.outputStack = []

 

}

 

Queue.prototype.enqueue = function (item) {

 

  return this.inputStack.push(item)

 

}

 

Queue.prototype.dequeue = function () {

 

  if (this.outputStack.length <= 0) {

 

    // reverse stack to outputStack

 

    while(this.inputStack.length > 0)

 

      this.outputStack.push(this.inputStack.pop())

 

  }

 

  return this.outputStack.pop()

 

}

 

const q = new Queue()

 

q.enqueue(1)

 

q.enqueue(2)

 

q.dequeue() // 1

 

q.dequeue() // 2

 

q.dequeue() // undefined

 

11. 查找字符串中各字母的出现次数

 

function countLetter (s) {

 

  const result = {}

 

  s.split('').forEach(v => {

 

    if (result[v]) result[v]++

 

    else result[v] = 1

 

  })

 

  return result

 

}

 

countLetter('abaabba') // {a: 4, b: 3}

 

12. 原型链、原型继承

 

function O (name) {

 

  this.name = name

 

  O.prototype.count++

 

}

 

O.prototype.count = 0

 

const a = new O('a')

 

a.name  // 'a'

 

a.count // 1

 

const b = new O('b')

 

b.name  // 'b'

 

b.count // 2

 

a.count // 2