面试官：super() �?super(props) 有什么区别？

一、ES6 �?

�?ES6 中，通过 extends 关键字实现类的继承，方式如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class sup {
  constructor(name) {
    this.name = name;
  }

  printName() {
    console.log(this.name);
  }
}

class sub extends sup {
  constructor(name, age) {
    super(name); // super代表的事父类的构造函�?    this.age = age;
  }

  printAge() {
    console.log(this.age);
  }
}

let jack = new sub("jack", 20);
jack.printName(); //输出 : jack
jack.printAge(); //输出 : 20

在上面的例子中，可以看到通过 super 关键字实现调用父类，super 代替的是父类的构建函数，使用 super(name) 相当于调�?sup.prototype.constructor.call(this,name)

如果在子类中不使�?super，关键字，则会引发报错，如下�?

报错的原因是 子类是没有自己的 this 对象的，它只能继承父类的 this 对象，然后对其进行加�?
�?super() 就是将父类中�?this 对象继承给子类的，没�?super() 子类就得不到 this 对象

如果先调�?this，再初始�?super()，同样是禁止的行�?

1
2
3
4
5

class sub extends sup {
  constructor(name, age) {
    this.age = age;
    super(name); // super代表的事父类的构造函�?  }
}

所以在子类 constructor 中，必须先代�?super 才能引用 this

二、类组件

�?React 中，类组件是基于 ES6 的规范实现的，继�?React.Component，因此如果用�?constructor 就必须写 super() 才初始化 this

这时候，在调�?super() 的时候，我们一般都需要传�?props 作为参数，如果不传进去，React 内部也会将其定义在组件实例中

1
2
3

// React 内部
const instance = new YourComponent(props);
instance.props = props;

所以无论有没有 constructor，在 render �?this.props 都是可以使用的，这是 React 自动附带的，是可以不写的�?

1
2
3
4
5

class HelloMessage extends React.Component {
  render() {
    return <div>nice to meet you! {this.props.name}</div>;
  }
}

但是也不建议使用 super() 代替 super(props)

因为�?React 会在类组件构造函数生成实例后再给 this.props 赋值，所以在不传�?props �?super 的情况下，调�?this.props �?undefined，如下情况：

1
2
3
4
5
6
7
8

class Button extends React.Component {
  constructor(props) {
    super(); // 没传�?props
    console.log(props);      //  {}
    console.log(this.props); //  undefined
    // ...
  }
}

而传�?props 的则都能正常访问，确保了 this.props 在构造函数执行完毕之前已被赋值，更符合逻辑，如下：

1
2
3
4
5
6
7
8

class Button extends React.Component {
  constructor(props) {
    super(props); // 没传�?props
    console.log(props);      //  {}
    console.log(this.props); //  {}
    // ...
  }
}

三、总结

�?React 中，类组件基�?ES6，所以在 constructor 中必须使�?super

在调�?super 过程，无论是否传�?props，React 内部都会�?porps 赋值给组件实例 porps 属性中

如果只调用了 super()，那�?this.props �?super() 和构造函数结束之间仍�?undefined

参考文�?

• https://overreacted.io/zh-hans/why-do-we-write-super-props/
• https://segmentfault.com/q/1010000008340434

面试官：说说你对算法的理解？应用场景�?

一、是什�?

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机�?
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输�?
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问�?
一个程�?算法+数据结构，数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的，两者不可分�?
因此，算法的设计和选择要同时结合数据结构，简单地说数据结构的设计就是选择存储方式，如确定问题中的信息是用数组存储还是用普通的变量存储或其他更加复杂的数据结构

针对上述，可以得出一个总结：不同的算法可能用不同的时间、空间或效率来完成同样的任务

二、特�?

关于算法的五大特性，有如下：

• 有限性（Finiteness）：一个算法必须保证执行有限步之后结束
• 确切性（Definiteness）： 一个算法的每一步骤必须有确切的定义
• 输入（Input）：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件
• 输出（Output）：一个算法有一个或多个输出。没有输出的算法毫无意义
• 可行性（Effectiveness）：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）

三、应用场�?

在前端领域中，数据结构与算法无法不在，例如现在的vue或者react项目，实现虚拟DOM或者Fiber结构，本质就是一种数据结构，如下一个简单的虚拟DOM�?

1
2
3
4
5
6
7
8
9
10
11

{
  type: 'div',
    props: {
      name: 'lucifer'
    },
      children: [{
        type: 'span',
        props: {},
        children: []
      }]
}

vue与react都能基于基于对应的数据结构实现diff算法，提高了整个框架的性能以及拓展�?
包括在前端javascript编译的时候，都会生成对应的抽象语法树AST，其本身不涉及到任何语法，因此你只要编写相应的转义规则，就可以将任何语法转义到任何语法，也是babel�?PostCSS, prettier�?typescript

除了这些框架或者工具底层用到算法与数据结构之外，日常业务也无处不在，例如实现一个输入框携带联想功能，如下：

如果我们要实现这个功能， 则可以使用前缀树，如下�?

包括前端可能会做一些对字符串进行相似度检测，例如”每日一�?�?js每日一�?两个字符串进行相似度对比，这种情况可以通过“最小编辑距离”算法，如果a和b的编辑距离越小，我们认为越相�?
日常在编写任何代码的都需要一个良好的算法思维，选择好的算法或者数据结构，能让整个程序效率更高

参考文�?

• https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025
• https://lucifer.ren/blog/2019/09/18/algorthimn-fe-1/

面试官：说说你对二分查找的理解？如何实现？应用场景？

一、是什�?

在计算机科学中，二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算�?
想要应用二分查找法，则这一堆数应有如下特性：

• 存储在数组中
• 有序排序

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结�?
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比�?
如果在某一步骤数组为空，则代表找不�?
这种搜索算法每一次比较都使搜索范围缩小一�?
如下图所示：

相比普通的顺序查找，除了数据量很少的情况下，二分查找会比顺序查找更快，区别如下所示：

二、如何实�?

基于二分查找的实现，如果数据是有序的，并且不存在重复项，实现代码如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function BinarySearch(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (target < arr[midIndex]) {
            highIndex = midIndex - 1
        } else if (target > arr[midIndex]) {
            lowIndex = midIndex + 1
        } else {
            // target === arr[midIndex]
            return midIndex
        }
    }
    return -1
}

如果数组中存在重复项，而我们需要找出第一个制定的值，实现则如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

function BinarySearchFirst(arr, target) {
    if (arr.length <= 1) return -1
    // 低位下标
    let lowIndex = 0
    // 高位下标
    let highIndex = arr.length - 1

    while (lowIndex <= highIndex) {
        // 中间下标
        const midIndex = Math.floor((lowIndex + highIndex) / 2)
        if (target < arr[midIndex]) {
            highIndex = midIndex - 1
        } else if (target > arr[midIndex]) {
            lowIndex = midIndex + 1
        } else {
            // �?target �?arr[midIndex] 相等的时候，如果 midIndex �?或者前一个数�?target 小那么就找到了第一个等于给定值的元素，直接返�?            if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex
            // 否则高位下标为中间下标减1，继续查�?            highIndex = midIndex - 1
        }
    }
    return -1
}

实际上，除了有序的数组可以使用，还有一种特殊的数组可以应用，那就是轮转后的有序数组

有序数组即一个有序数字以某一个数为轴，将其之前的所有数都轮转到数组的末尾所�?
例如，[4, 5, 6, 7, 0, 1, 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

  function search (nums, target) { // 如果为空或者是空数组的情况 if (nums == null || !nums.length) { return -1; } // 搜索区间是前闭后�? let begin = 0, end = nums.length - 1; while (begin <= end) { // 下面这样写是考虑大数情况下避免溢�? let mid = begin + ((end - begin) >> 1); if (nums[mid] == target) { return mid; } // 如果左边是有序的 if (nums[begin] <= nums[mid]) { //同时target在[ nums[begin],nums[mid] ]中，那么就在这段有序区间查找 if (nums[begin] <= target && target <= nums[mid]) { end = mid - 1; } else { //否则去反方向查找 begin = mid + 1; } //如果右侧是有序的 } else { //同时target在[ nums[mid],nums[end] ]中，那么就在这段有序区间查找 if (nums[mid] <= target && target <= nums[end]) { begin = mid + 1; } else { end = mid - 1; } } } return -1; };

对比普通的二分查找法，为了确定目标数会落在二分后的哪个部分，我们需要更多的判定条件

三、应用场�?

二分查找法的O(logn)让它成为十分高效的算法。不过它的缺陷却也是比较明显，就在它的限定之上：

• 有序：我们很难保证我们的数组都是有序�?- 数组：数组读取效率是O(1)，可是它的插入和删除某个元素的效率却是O(n)，并且数组的存储是需要连续的内存空间，不适合大数据的情况

关于二分查找的应用场景，主要如下�?

• 不适合数据量太小的数列；数列太小，直接顺序遍历说不定更快，也更简�?- 每次元素与元素的比较是比较耗时的，这个比较操作耗时占整个遍历算法时间的大部分，那么使用二分查找就能有效减少元素比较的次�?- 不适合数据量太大的数列，二分查找作用的数据结构是顺序表，也就是数组，数组是需要连续的内存空间的，系统并不一定有这么大的连续内存空间可以使用

参考文�?

• https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E5%B0%8B%E6%BC%94%E7%AE%97%E6%B3%95#javascript_%E7%89%88%E6%9C%AC
• https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html

面试官：说说你对堆的理解？如何实现？应用场景�?

一、是什�?

�?Heap)是计算机科学中一类特殊的数据结构的统�?
堆通常是一个可以被看做一棵完全二叉树的数组对象，如下图：

总是满足下列性质�?

• 堆中某个结点的值总是不大于或不小于其父结点的�?- 堆总是一棵完全二叉树

堆又可以分成最大堆和最小堆�?

• 最大堆：每个根结点，都有根结点的值大于两个孩子结点的�?- 最小堆：每个根结点，都有根结点的值小于孩子结点的�?

二、操�?

堆的元素存储方式，按照完全二叉树的顺序存储方式存储在一个一维数组中，如下图�?

用一维数组存储则如下�?

1

[0, 1, 2, 3, 4, 5, 6, 7, 8]

根据完全二叉树的特性，可以得到如下特性：

• 数组零坐标代码的是堆顶元�?- 一个节点的父亲节点的坐标等于其坐标除以2整数部分
• 一个节点的左节点等于其本身节点坐标 * 2 + 1
• 一个节点的右节点等于其本身节点坐标 * 2 + 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

class MinHeap {
  constructor() {
    // 存储堆元�?    this.heap = []
  }
  // 获取父元素坐�?  getParentIndex(i) {
    return (i - 1) >> 1
  }

  // 获取左节点元素坐�?  getLeftIndex(i) {
    return i * 2 + 1
  }

 // 获取右节点元素坐�?  getRightIndex(i) {
    return i * 2 + 2
  }

  // 交换元素
  swap(i1, i2) {
    const temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }

  // 查看堆顶元素
  peek() {
    return this.heap[0]
  }

  // 获取堆元素的大小
  size() {
    return this.heap.length
  }
}

涉及到堆的操作有�?

• 插入
• 删除

插入

将值插入堆的底部，即数组的尾部，当插入一个新的元素之后，堆的结构就会被破坏，因此需要堆中一个元素做上移操作

将这个值和它父节点进行交换，直到父节点小于等于这个插入的值，大小为k的堆中插入元素的时间复杂度为O(logk)

如下图所示，22节点是新插入的元素，然后进行上移操作�?

相关代码如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 插入元素
insert(value) {
  this.heap.push(value)
  this.shifUp(this.heap.length - 1)
}

// 上移操作
shiftUp(index) {
  if (index === 0) { return }
  const parentIndex = this.getParentIndex(index)
  if(this.heap[parentIndex] > this.heap[index]){
    this.swap(parentIndex, index)
    this.shiftUp(parentIndex)
  }
}

删除

常见操作是用数组尾部元素替换堆顶，这里不直接删除堆顶，因为所有的元素会向前移动一位，会破坏了堆的结构

然后进行下移操作，将新的堆顶和它的子节点进行交换，直到子节点大于等于这个新的堆顶，删除堆顶的时间复杂度为O(logk)

整体如下图操作：

相关代码如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 删除元素
pop() {
  this.heap[0] = this.heap.pop()
  this.shiftDown(0)
}

// 下移操作
shiftDown(index) {
  const leftIndex = this.getLeftIndex(index)
  const rightIndex = this.getRightIndex(index)
  if (this.heap[leftIndex] < this.heap[index]){
    this.swap(leftIndex, index)
    this.shiftDown(leftIndex)
  }
  if (this.heap[rightIndex] < this.heap[index]){
    this.swap(rightIndex, index)
    this.shiftDown(rightIndex)
  }
}

时间复杂�?

关于堆的插入和删除时间复杂度都是Olog(n)，原因在于包含n个节点的完全二叉树，树的高度不会超过log2n

堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，也就是Olog(n)，插入数据和删除堆顶元素的主要逻辑就是堆化

三、总结

• 堆是一个完全二叉树
• 堆中每一个节点的值都必须大于等于(或小于等�?其子树中每个节点的�?- 对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆�?- 对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆�?- 根据堆的特性，我们可以使用堆来进行排序操作，也可以使用其来求第几大或者第几小的�?

参考文�?

• https://baike.baidu.com/item/%E5%A0%86/20606834
• https://xlbpowder.cn/2021/02/26/%E5%A0%86%E5%92%8C%E5%A0%86%E6%8E%92%E5%BA%8F/

面试官：说说你对链表的理解？常见的操作有哪些�?

一、是什�?

链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，由一系列结点（链表中每一个元素称为结点）组成

每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

节点用代码表示，则如下：

1
2
3
4
5
6

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

• data 表示节点存放的数�?- next 表示下一个节点指向的内存空间

相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)

链表的结构也十分多，常见的有四种形式�?

• 单链表：除了头节点和尾节点，其他节点只包含一个后继指�?- 循环链表：跟单链表唯一的区别就在于它的尾结点又指回了链表的头结点，首尾相连，形成了一个环
• 双向链表：每个结点具有两个方向指针，后继指针(next)指向后面的结点，前驱指针(prev)指向前面的结点，其中节点的前驱指针和尾结点的后继指针均指向空地址NULL
• 双向循环链表：跟双向链表基本一致，不过头节点前驱指针指向尾迹诶单和尾节点的后继指针指向头节�?

二、操�?

关于链表的操作可以主要分成如下：

• 遍历
• 插入
• 删除

遍历

遍历很好理解，就是根据next指针遍历下去，直到为null，如下：

1
2
3
4
5

let current = head
while(current){
 console.log(current.val)
  current = current.next
}

插入

向链表中间插入一个元素，可以如下图所示：

可以看到，插入节点可以分成如下步骤：

• 存储插入位置的前一个节�?- 存储插入位置的后一个节�?
• 将插入位置的前一个节点的 next 指向插入节点
• 将插入节点的 next 指向前面存储�?next 节点

相关代码如下所示：

1
2
3
4
5
6
7
8

let current = head
while (current < position){
  pervious = current;
  current = current.next;
}
pervious.next = node;
node.next = current;

如果在头节点进行插入操作的时候，会实现previousNode节点为undefined，不适合上述方式

解放方式可以是在头节点前面添加一个虚拟头节点，保证插入行为一�?

删除

向链表任意位置删除节点，如下图操作：

从上图可以看到删除节点的步骤为如下：

• 获取删除节点的前一个节�?- 获取删除节点的后一个节�?- 将前一个节点的 next 指向后一个节�?- 向删除节点的 next 指向为null

如果想要删除制定的节点，示意代码如下�?

1
2
3
4
5
6

while (current != node){
  pervious = current;
  current = current.next;
  nextNode = current.next;
}
pervious.next = nextNode

同样如何希望删除节点处理行为一致，可以在头节点前面添加一个虚拟头节点

三、应用场�?

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等

当缓存空间被用满时，我们可能会使用LRU最近最好使用策略去清楚，而实现LRU算法的数据结构是链表，思路如下�?
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头部开始顺序遍历链�?

• 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据的对应结点，并将其从原来的位置删除，并插入到链表头部
• 如果此数据没在缓存链表中
  • 如果此时缓存未满，可直接在链表头部插入新节点存储此数�? - 如果此时缓存已满，则删除链表尾部节点，再在链表头部插入新节点

由于链表插入删除效率极高，达到O(1)。对于不需要搜索但变动频繁且无法预知数量上限的数据的情况的时候，都可以使用链�?

参考文�?- https://zh.wikipedia.org/zh-hans/%E9%93%BE%E8%A1%A8

• https://mah93.github.io/2019/07/19/js-linked/

面试官：说说你对冒泡排序的理解？如何实现？应用场景？

一、是什�?

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法

冒泡排序的思想就是在每次遍历一遍未排序的数列之后，将一个数据元素浮上去（也就是排好了一个数据）

如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序�?
假如我们要把 12�?5�?9�?8�?6 �?5 个数从大到小进行排序，那么数越大，越需要把它放在前�?
思路如下�?

• 从后开始遍历，首先比较 18 �?76，发�?76 �?18 大，就把两个数交换顺序，得到 12�?5�?9�?6�?8
• 接着比较 76 �?99，发�?76 �?99 小，所以不用交换顺�?- 接着比较 99 �?35，发�?99 �?35 大，交换顺序
• 接着比较 99 �?12，发�?99 �?12 大，交换顺序

最终第 1 趟排序的结果变成�?99�?2�?5�?6�?8，如下图所示：

上述可以看到，经过第一趟的排序，可以得到最大的元素，接下来第二趟排序则对剩下的�?个元素进行排序，如下图所示：

经过�?2 趟排序，结果�?99�?6�?2�?5�?8

然后开始第3趟的排序，结果为99�?6�?5�?2�?8

然后第四趟排序结果为99�?6�?5�?8�?2

经过 4 趟排序之后，只剩一�?12 需要排序了，这时已经没有可比较的元素了，这时排序完�?

二、如何实�?

如果要实现一个从小到大的排序，算法原理如下：

• 首先比较相邻的元素，如果第一个元素比第二个元素大，则交换它们
• 针对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这样，最后的元素回事最大的�?- 针对所有的元素重复以上的步骤，除了最后一�?- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比�?
  

用代码表示则如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13

function bubbleSort(arr) {
    const 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]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

可以看到：冒泡排序在每一轮排序中都会使一个元素排到一趟， 也就是最终需�?n-1 轮这样的排序

而在每轮排序中都需要对相邻的两个元素进行比较，在最坏的情况下，每次比较之后都需要交换位置，此时时间复杂度为O(n^2)

优化

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交�?
如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程

可以设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置，由于pos位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到pos位置即可，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function bubbleSort1(arr){
 const i=arr.length-1;//初始�?最后位置保持不�? 
 while(i>0){
  let pos = 0;//每趟开始时,无记录交�?  for(let j = 0; j < i; j++){
   if(arr[j] > arr[j+1]){
        let tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
    pos = j;//记录最后交换的位置  
   }   
  }
  i = pos;//为下一趟排序作准备
 }
 return arr;
}

在待排序的数列有序的情况下，只需要一轮排序并且不用交换，此时情况最好，时间复杂度为O(n)

并且从上述比较中看到，只有后一个元素比前面的元素大（小）时才会对它们交换位置并向上冒出，对于同样大小的元素，是不需要交换位置的，所以对于同样大小的元素来说，相对位置是不会改变的，因此�?冒泡排序是稳定的

三、应用场�?冒泡排的核心部分是双重嵌套循环，

时间复杂度是 O(N 2 )，相比其它排序算法，这是一个相对较高的时间复杂度，一般情况不推荐使用，由于冒泡排序的简洁性，通常被用来对于程序设计入门的学生介绍算法的概�?

参考文�?

• https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/4602306
• https://www.runoob.com/w3cnote/bubble-sort.html
• http://data.biancheng.net/view/116.html
• https://dsb123dsb.github.io/2017/03/07/js%E5%AE%9E%E7%8E%B0%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F%E4%BB%A5%E5%8F%8A%E4%BC%98%E5%8C%96/

面试官：说说你对分而治之、动态规划的理解？区别？

一、分而治�?

分而治之是算法设计中的一种方法，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合�?
关于分而治之的实现，都会经历三个步骤：

• 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问�?- 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问�?- 合并：将各子问题的解合并为原问题的解

实际上，关于分而治之的思想，我们在前面已经使用，例如归并排序的实现，同样经历了实现分而治之的三个步骤�?

• 分解：把数组从中间一分为�?- 解决：递归地对两个子数组进行归并排�?
• 合并：将两个字数组合并称有序数组

同样关于快速排序的实现，亦如此�?

• 分：选基准，按基准把数组分成两个字数�?- 解：递归地对两个字数组进行快速排�?- 合：对两个字数组进行合并

同样二分搜索也能使用分而治之的思想去实现，代码如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13

function binarySearch(arr,l,r,target){
    if(l> r){
        return -1;
    }
    let mid = l + Math.floor((r-l)/2)
    if(arr[mid] === target){
        return mid;
    }else if(arr[mid] < target ){
        return binarySearch(arr,mid + 1,r,target)
    }else{
        return binarySearch(arr,l,mid - 1,target)
    }
}

二、动态规�?

动态规划，同样是算法设计中的一种方法，是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方�?
常常适用于有重叠子问题和最优子结构性质的问�?
简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解�?
然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法�?
一般这些子问题很相似，可以通过函数关系式递推出来，例如斐波那契数列，我们可以得到公式：当 n 大于 2的时候，F(n) = F(n-1) + F(n-2) �?
f(10)= f(9)+f(8),f(9) = f(8) + f(7)…是重叠子问题，当n = 1�?的时候，对应的值为2，这时候就通过可以使用一个数组记录每一步计算的结果，以此类推，减少不必要的重复计算

适用场景

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规�?
比如一些求最值的场景，如最长递增子序列、最小编辑距离、背包问题、凑零钱问题等等，都是动态规划的经典应用场景

关于动态规划题目解决的步骤，一般如下：

• 描述最优解的结�?- 递归定义最优解的�?- 按自底向上的方式计算最优解的�?- 由计算出的结果构造一个最优解

三、区�?

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，而分而治之的子问题是相互独立�?
若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时�?
综上，可得：

• 动态规划：有最优子结构和重叠子问题

• 分而治之：各子问题独立

参考文�?

• https://baike.baidu.com/item/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/529408
• https://juejin.cn/post/6951922898638471181

面试官：说说你对贪心算法、回溯算法的理解？应用场景？

一、贪心算�?

贪心算法，又称贪婪算法，是算法设计中的一种思想

其期待每一个阶段都是局部最优的选择，从而达到全局最优，但是结果并不一定是最优的

举个零钱兑换的例子，如果你有1元�?元�?元的钱币数张，用于兑换一定的金额，但是要求兑换的钱币张数最�?
如果现在你要兑换11元，按照贪心算法的思想，先选择面额最大的5元钱币进行兑换，那么就得�?1 = 5 + 5 + 1 的选择，这种情况是最优的

但是如果你手上钱币的面额�?�?�?，想要兑�?元，按照贪心算法的思路，我们会 6 = 4 + 1 + 1这样选择，这种情况结果就不是最优的选择

从上面例子可以看到，贪心算法存在一些弊端，使用到贪心算法的场景，都会存在一个特性：

一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办�?
至于是否选择贪心算法，主要看是否有如下两大特性：

• 贪心选择：当某一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次做出的选择可以依赖以前做出的选择，但不需要依赖后面需要做出的选择
• 最优子结构：如果一个问题的最优解包含其子问题的最优解，则此问题具备最优子结构的性质。问题的最优子结构性质是该问题是否可以用贪心算法求解的关键所�?

二、回溯算�?

回溯算法，也是算法设计中的一种思想，是一种渐进式寻找并构建问题解决方式的策略

回溯算法会先从一个可能的工作开始解决问题，如果不行，就回溯并选择另一个动作，知道将问题解�?
使用回溯算法的问题，有如下特性：

• 有很多路，例如一个矩阵的方向或者树的路�?- 在这些的路里面，有死路也有生路，思路即不符合题目要求的路，生路则符合
• 通常使用递归来模拟所有的�?
  常见的伪代码如下�?

  1 2 3 4 5 6 7 8 9 10

  result = [] function backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 of 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择

重点解决三个问题�?

• 路径：也就是已经做出的选择
• 选择列表
• 结束条件

例如经典使用回溯算法为解决全排列的问题，如下�?
一个不含重复数字的数组 nums ，我们要返回其所有可能的全排列，解决这个问题的思路是：

• 用递归模拟所有的情况
• 遇到包含重复元素的情况则回溯
• 收集到所有到达递归终点的情况，并返回�?
  

用代码表示则如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

var permute = function(nums) {
    const res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;
    
    function backtracking(n, k, used) {
        if(path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < k; i++ ) {
            if(used[i]) continue;
            path.push(n[i]);
            used[i] = true; // 同支
            backtracking(n, k, used);
            path.pop();
            used[i] = false;
        }
    }
};

三、总结

前面也初步了解到分而治之、动态规划，现在再了解到贪心算法、回溯算�?
其中关于分而治之、动态规划、贪心策略三者的求解思路如下�?

其中三者对应的经典问题如下图：

参考文�?

• https://zh.wikipedia.org/wiki/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95
• https://leetcode-cn.com/problems/permutations/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-mfrp/
• https://cloud.tencent.com/developer/article/1767046

面试官：说说你对图的理解？相关操作有哪些�?

一、是什�?

在计算机科学中，图是一种抽象的数据类型，在图中的数据元素通常称为结点，V是所有顶点的集合，E是所有边的集�?
如果两个顶点v, w，只能由v向w，而不能由w向v，那么我们就把这种情况叫做一个从 v �?w 的有向边。v 也被称做初始点，w也被称为终点。这种图就被称做有向�?
如果v和w是没有顺序的，从v到达w和从w到达v是完全相同的，这种图就被称为无向�?
图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系

常见表达图的方式有如下：

• 邻接矩阵

• 邻接�?

邻接矩阵

通过使用一个二维数组G[N][N]进行表示N个点到N-1编号，通过邻接矩阵可以立刻看出两顶点之间是否存在一条边，只需要检查邻接矩阵行i和列j是否是非零值，对于无向图，邻接矩阵是对称的

邻接�?

存储方式如下图所示：

在javascript中，可以使用Object进行表示，如下：

1
2
3
4
5
6
7
8
9

const graph = {
  A: [2, 3, 5],
  B: [2],
  C: [0, 1, 3],
  D: [0, 2],
  E: [6],
  F: [0, 6],
  G: [4, 5]
}

图的数据结构还可能包含和每条边相关联的数值（edge value），例如一个标号或一个数值（即权重，weight；表示花费、容量、长度等�?

二、操�?

关于的图的操作常见的有：

• 深度优先遍历
• 广度优先遍历

首先构建一个图的邻接矩阵表示，如下面的图：

用代码表示则如下�?

1
2
3
4
5
6
7

const graph = {
  0: [1, 4],
  1: [2, 4],
  2: [2, 3],
  3: [],
  4: [3],
}

深度优先遍历

也就是尽可能的往深处的搜索图的分�?
实现思路是，首先应该确定一个根节点，然后对根节点的没访问过的相邻节点进行深度优先遍�?
确定�?0 为根节点，然后进行深度遍历，然后遍历1，接着遍历 2，然�?，此时完成一条分支0 - 1- 2- 3的遍历，换一条分支，也就�?�?后面因为3已经遍历过了，所以就不访问了

用代码表示则如下�?

1
2
3
4
5
6
7
8
9

const visited = new Set()
const dfs = (n) => {
  console.log(n)
  visited.add(n) // 访问过添加记�?  graph[n].forEach(c => {
    if(!visited.has(c)){ // 判断是否访问呢过
      dfs(c)
    }
  })
}

广度优先遍历

先访问离根节点最近的节点，然后进行入队操作，解决思路如下�?

• 新建一个队列，把根节点入队
• 把队头出队并访问
• 把队头的没访问过的相邻节点入�?- 重复二、三步骤，知道队列为�?
  用代码标识则如下�?

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  const visited = new Set() const dfs = (n) => { visited.add(n) const q = [n] while(q.length){ const n = q.shift() console.log(n) graph[n].forEach(c => { if(!visited.has(c)){ q.push(c) visited.add(c) } }) } }

三、总结

通过上面的初步了解，可以看到图就是由顶点的有穷非空集合和顶点之间的边组成的集合，分成了无向图与有向图

图的表达形式可以分成邻接矩阵和邻接表两种形式，在javascript中，则可以通过二维数组和对象的形式进行表达

图实际是很复杂的，后续还可以延伸出无向图和带权图，对应如下图所示：

参考文�?

• https://zh.wikipedia.org/wiki/%E5%9B%BE_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)
• https://www.kancloud.cn/imnotdown1019/java_core_full/2159607

面试官：说说你对插入排序的理解？如何实现？应用场景？

一、是什�?

插入排序（Insertion Sort），一般也被称为直接插入排序。对于少量元素的排序，它是一个有效、简单的算法

其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据

插入排序的工作方式像许多人排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下

然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置，该正确位置需要从右到左将它与已在手中的每张牌进行比较

例如一个无序数�?3�?�?�?�?�?�?�?，将其升序的结果则如下：

一开始有序表中无数据，直接插�?

从第二个数开始，插入一个元�?，然后和有序表中记录3比较�?<3，所以插入到记录 3 的左�?

向有序表插入记录 7 时，同有序表中记�?3 进行比较�?<7，所以插入到记录 3 的右�?

向有序表中插入记�?5 时，同有序表中记�?7 进行比较�?<7，同�?5>3，所以插入到 3 �?7 中间

照此规律，依次将无序表中的记�?4�? �?6插入到有序表�?

二、如何实�?

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列�?
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置

如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后�?

用代码表示则如下�?

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function insertionSort(arr) {
    const len = arr.length;
    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(n)

最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+�?N-1，所以，插入排序最坏情况下的时间复杂度为O(n^2)

通过上面了解，可以看到插入排序是一种稳定的排序方式

三、应用场�?

插入排序时间复杂度是 O(n2)，适用于数据量不大，算法稳定性要求高，且数据局部或整体有序的数列排�?

参考文�?

• https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/7214992
• http://data.biancheng.net/view/65.html