js 算法题

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

1. 冒泡排序

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

冒泡排序最好的时间复杂度为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