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算法題有哪些”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！