web面试题精选

# 八.前端算法

# 1.位运算

在进入正题之前，我们先来学习一下位运算的内容。因为位运算在算法中很有用，速度可以比四则运算块很多。

在学习位运算之前应该知道十进制如何转二进制，二进制如何转十进制。

  • 十进制33可以看成是32+1,并且33应该是六位二进制的(因为33近似32，而32是 2 的五次方，所以是六位 )，那么十进制33就是100001,只要是 2 的次方，那么就是 1 否则都为 0
  • 那么二进制100001同理，首位是2^5，末位是2^0,相加得出 33

# 2.左移 <<

10 << 1 // ->20
1

左移就是将二进制全部往左移动，10在二进制中表示为1010,左移一位后变为10100,转换为十进制也就是 20,所以基本可以吧左移看成以下公式a*(2^b)

# 3.算数右移 >>

10 >> 1 // ->5
1

算数右移就是将二进制全部往右移动并去除多余的右边，10在二进制中表示为1010,右移一位后变为101,转换成十进制也就是 5，所以基本可以把右移看成以下公式int v = a /(2^b)

右移很好用，比如可以用在二分算法中取中间值

13 >> 1 // -> 6
1

# 4.按位操作

按位与

每一位都为 1，结果才为 1

8 & 7 // ->0
1

按位或

其中一位为 1，结果就是 1

8 | 7 // ->15
1

按位异或

每一位不同，结果才为 1

8 ^ 7 // ->15
8 ^ 8 //->0
1
2

# 5. 十大排序

    1. 冒泡排序

    • 重复走访要排序的数列，依次比价两个元素，如果他们的顺序错误就把他们交换过来

    • 实现过程

      • 1.比较相邻的元素，如果第一个比第二个大，就交换他们两个
      • 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会使最大的数
      • 3.针对所有的元素重复以上的步骤，除了最后一个
      • 4.重复步骤 1-3,直到排序完成
      • 手写冒泡排序
      function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      let preData = arr[i]
      let nextData = arr[j]
      if (preData > nextData) {
        arr[i] = nextData
        arr[j] = preData
      }
    }
  }
  return arr
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      • 优化一个冒泡排序
      function bubbleSort(data) {
  let finish = false
  for (let pre = 0; pre < data.length - 1; pre++) {
    for (let next = pre + 1; next < datalength; next++) {
      let preData = data[pre]
      let nextData = data[next]
      if (preData > nextData) {
        finish = false
        data[pre] = nextData
        data[next] = preData
      }
      if (finish) {
        break
      } else {
        finish = true
      }
    }
  }
  return data
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20

  • 2.选择排序

    • 首先在未排序序列中找到最小值，放在排序序列的起始位置，然后，在从剩下未排序元素中继续寻找最小值，然后放在排序序列的末尾
    • 实现过程

  • 3.插入排序

    • 构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置插入
    • 实现过程
      • 1.从第一个元素开始，该元素可以认为已经被排序
      • 2.取出下一个元素，在已排序的元素序中从后向前扫描
      • 3.如果该元素（已排序）大于新元素，将元素向后移一位
      • 4.在取出一个元素，比较之前的，知道找到自己合适的位置

  • 4.桶排序

    • 将数据分布到有限数量的桶里，每个桶再分别排序

  • 5.快速排序

    • 快速排序使用分治法把一个串（list）分成两个子串（sub-lists）

    • 实现过程

      • 1.从数组中挑出一个元素，成为一个基准
      • 2.重新排序数组，所有元素比基准小的摆在基准前面，所有比基准大的摆在基准后面，这个分区退出之后，该基准就处于数列的中间位置，成为分区操作
      • 3.递归的把小于基准值的子数列和大于基准元素的子数列排序
      function quickSory(arr){
    if(arr.length <=1>){
        return false
    }
    var destIndex=Math.floor(arr.length/2)
    var left=[],right=[]
    var dest=arr.splice(destIndex,1)[0]
    for(var i=0;i<arr.length;i++>){
        if(arr[i]<dest){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([dest],quickSort(right))
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var pivotIndex = Math.floor(arr.length / 2)
  var pivot = arr.splice(pivotIndex, 1)[0]
  var left = []
  var right = []
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
    return quickSort(left).concat([pivot], quickSort(right))
  }
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      function quickSort(data) {
  let left = []
  let right = []
  let point = (data.length / 2) | 0
  let pointData = data.splice(point, 1)[0]
  for (let i = 0; i < data.length; i++) {
    data[i] > pointData ? left.push(data[i]) : right.push(data[i])
  }
  return [...quickSort(left), pointData, ...quickSort(right)]
}
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10

  • 6.堆排序

    • 利用对这种数据结构所涉及的一种排序算法，堆积是一个近乎完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或大于）它的父节点
    • 实现过程

# 6. 两个栈实现一个队列，两个队列实现一个栈

// 队列
function Queue() {
  var items = []
  this.enqueue = function (element) {
    //向队列尾部添加一个新的项
    items.push(element)
  }
  this.dequeue = function () {
    // 移除队列的第一项，并返回被移除的元素
    return items.shift()
  }
  this.front = function () {
    // 返回队列的第一个元素
    return items[0]
  }
  this.isEmpty = function () {
    //检查队列中是否有元素，返回true或false
    return items.length == 0
  }
  this.size = function () {
    return items.length
  }
  this.print = function () {
    console.log(items.toString())
  }
}

// 使用Queue类
var queue = new Queue()
console.log(queue.isEmpty())
queue.enqueue("John")
queue.enqueue("Jack")
queue.enqueue("Camial")
queue.print()
queue.dequeue()
queue.print()

//优先队列

// 1.设置优先级，然后在正确的位置添加元素
// 2.用入列操作添加元素，然后按照优先级移除他们。

function priorityQueue() {
  var items = []
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  this.enqueue = function (element, priority) {
    var queueElement = new QueueElement(element, priority)

    if (this.isEmpty()) {
      items.push(queueElement)
    } else {
      var added = false
      for (var i = 0; i < items.length; i++) {
        if (queueElement.priority < items[i].priority) {
          items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
      if (!added) {
        items.push(queueElement)
      }
    }
  }
}

var priorityQueue = new priorityQueue()
priorityQueue.enqueue("john", 2)
priorityQueue.enqueue("jack", 1)
priorityQueue.enqueue("camila", 1)
priorityQueue.print()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# 7. 红黑树（解决二叉树依次插入多个节点时的线性排列）

// 二叉树多次插入新节点导致不平衡。二叉树查找的思想：查找所需的最大次数等同于二叉树的高度

// 红黑树，

// 1.节点是红色和黑色 // 2.根节点是褐黑色 // 3.每个叶子节点都是黑色的空节点(NIL 节点) // 4.每个红色节点的两个子节点都是黑色(从每个叶子到跟的所有路经不能有两个连续的红色节点) // 5.从任意节点到其每个叶子的所有路经都包含相同数目的黑色节点

// 红黑树从根节点到叶子的最长路经不会超过最短路经的 2 倍

// 变色 旋转（左旋转和有旋转）

# 8. 最小栈的实现（查找最小元素，用两个栈配合栈内元素的下标）

//栈  先进先出
function Stack() {
  var items = []
  this.push = function (element) {
    //添加一个(或几个)新元素到栈顶
    items.push(element)
  }
  this.pop = function () {
    //移除栈顶元素，同时返回被删除的元素
    return items.pop()
  }
  this.peek = function () {
    //返回栈顶元素，不对栈做任何修改
    return items[items.length - 1]
  }
  this.isEmpty = function () {
    //如果栈里没有任何元素就返回true
    return items.length == 0
  }
  this.clear = function () {
    //移除栈里的所有元素
    return (items = [])
  }
  this.size = function () {
    //返回栈里的元素个数
    return items.length
  }
  this.print = function () {
    console.log(items.toString())
  }
}
// 使用Stack类
var stack = new Stack()
console.log(stack.isEmpty())
stack.push(5)
stack.push(8)
console.log(stack.peek())
console.log(stack.isEmpty())

//栈的运用
//  1. 从十进制到二进制   十进制数字和二进制整除（二进制满二进一），知道结果为0
function divideBy2(decNumber) {
  var remStack = new Stack(),
    rem,
    binaryString = ""
  while (decNumber > 0) {
    rem = Math.floor(decNumber % 2)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / 2)
  }
  while (!remStack.isEmpty()) {
    binaryString += remStack.pop().toString()
  }
  return binaryString
}
console.log(divideBy2(233))

// 十进制转换成任意进制的基数为参数
function baseConverter(decNumber, base) {
  var remStack = new Stack(),
    rem,
    baseString = "",
    digits = "0123456789ABCDEF"
  while (decNumber > 0) {
    rem = Math.floor(decNumber % base)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / base)
  }
  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()]
  }
  return baseString
}
console.log(baseConverter(100345, 2))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# 9. 二分查找（有序数组的查找）

  • 二分查找可以解决已排序数组的查找问题，即只要数组中包含 T（要查找的值），那么通过不断的缩小包含 T 的数据范文，就可以找到最终要找到的数
  • 1.一开始，数据范围覆盖整个数组
  • 2.将数组的中间项与 T 进行比较，如果 T 比数组的中间项小，则到数组的前半部分继续查找，反之，则到数组的后半部分查找
  • 3.就这样，每次查找都可以排除一半元素，相当于范围缩小一半，这样反复比较，反复缩小范围，最终会在数组中找到 T
function binarySearch(data, dest, start, end) {
  var end = end || data.length - 1
  var start = start || 0
  var m = Math.floor((start + end) / 2)
  if (dest < data[m]) {
    return binarySearch(data, dest, 0, m - 1)
  } else if (dest > data[m]) {
    return binarySearch(data, dest, m + 1, end)
  } else {
    return data[m]
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
上次更新: 2022/6/29 上午12:09:44

← 九.前端手写 →