js算法题有哪些

这篇文章给大家分享的是有关js算法题有哪些的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

冒泡排序

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

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

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

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

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

感谢各位的阅读！关于“js算法题有哪些”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！