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

# 10.字符串

  • 判断回文子符串：（递归的思想）
    • 1.字符串分割，倒转，聚合
[...obj].reverse().join("");
1
  • 2.字符串头部和尾部，逐次向中间检查
function isPalindrome(line) {
  line += "";
  for (var i = 0, j = line.length - 1; i < j; i++, j--) {
    if (line.chartAt(i) !== line.chartAt(j)) {
      return false;
    }
  }
}
1
2
3
4
5
6
7
8
  • 3.递归
上次更新: 2024/7/13 上午9:32:29

← 九.前端手写 →