[面试专题]数据结构和算法JS之魂

标签（空格分隔）： 未分类

数据结构:

• 栈：一种遵从先进后出 (LIFO) 原则的有序集合；新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端为栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

class Stack {
constructor() {
this.items = []
}
push(element) {
this.items.push(element)
}
pop() {
return this.items.pop()
}
clear() {
this.items = []
}
print() {
console.log(this.items.toString())
}
// 属性
get peek() {
return this.items[this.items.length - 1]
}
get size() {
return this.items.length
}
}

• 队列：与上相反，一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；队列在尾部添加新元素，并从头部移除元素。最新添加的元素必须排在队列的末尾。

class Queue {
constructor(items) {
this.items = items || []
}
// 普通队列
enqueue(element) {
this.items.push(element)
}
// 优先队列的构造方法
// enqueue(element, priority) {
// const queueElement = { element, priority }
// if (this.isEmpty) {
// this.items.push(queueElement)
// } else {
// const preIndex = this.items.findIndex((item) => queueElement.priority // if (preIndex > -1) {
// this.items.splice(preIndex, 0, queueElement)
// } else {
// this.items.push(queueElement)
// }
// }
// }
dequeue() {
return this.items.shift()
}
front() {
return this.items[0]
}
clear() {
this.items = []
}
print() {
console.log(this.items.toString())
}
get size() {
return this.items.length
}
get isEmpty() {
return !this.items.length
}
}
// 循环队列,要点在于index的计算
class LoopQueue extends Queue {
constructor(items) {
super(items)
}
getIndex(index) {
const length = this.items.length
return index > length ? (index % length) : index
}
find(index) {
return !this.isEmpty ? this.items[this.getIndex(index)] : null
}
}

• 链表：存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的；每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（指针/链接）组成。

class linkNode {
constructor(ele) {
this.element = ele;
this.next = null;
}
}
class singLinkList {
constructor() {
this.item = [];
this.head = null;
this.length = 0;
}
append(ele) {
const node = new linkNode(ele);
let current = null;
if (this.head) {
this.head = node;
} else {
current = this.head;
while (current.next) {
current = current.next;
};
current.next = node;
}
this.length++;
}
insert(pos, ele) {
if (pos > 0 && pos <= this.length) {
const node = new linkNode(ele);
let current = this.head;
let previous = null;
let index = 0;
if (pos === 0) {
this.head = node;
} else {
while (index index++;
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
this.length++;
}
}
removeAt(pos) {
if (pos > -1 && pos let current = this.head
let previous = null
let index = 0
if (pos === 0) {
this.head = current.next
} else {
while (index++ previous = current
current = current.next
}
previous.next = current.next
}
this.length--;
return current.element
}
}
findIndex(element) {
let current = this.head
let index = -1
while (current) {
if (element === current.element) {
return index + 1
}
index++
current = current.next
}
return -1
}
remove(element) {
const index = this.indexOf(element)
return this.removeAt(index)
}
size() {
return this.length
}
}

• 集合：由一组无序且唯一（即不能重复）的项组成；这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。ES6 中已内置了 Set 类型,实现的要点在于查找是否已存在.

• 字典：以 [键，值]对为数据形态的数据结构，其中键名用来查询特定元素，类似于 Javascript 中的Object。

• 散列：根据关键码值（Key,value）直接进行访问的数据结构；它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度；这个映射函数叫做散列函数，存放记录的数组叫做散列表。

  • 处理散列表中的冲突:分离链接、线性探查和双散列法。

  • 分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的 最简单的方法，但是它在 HashTable 实例之外还需要额外的存储空间。

  • 线性探查:当想向表中某个位置加人一个新元素的时候，如果索引为 index 的位置已经被占据了，就尝试 index+1的位置。如果index+1 的位置也被占据了，就尝试 index+2 的位置，以此类推。

  class HashTable {
constructor() {
this.table = []
}
// 散列函数
static loseloseHashCode(key) {
let hash = 0
for (let codePoint of key) {
hash += codePoint.charCodeAt()
}
return hash % 37
}
// 使用链表处理冲突
put(key, value) {
const position = HashTable.loseloseHashCode(key)
if (this.table[position] === undefined) {
this.table[position] = new LinkedList()
}
this.table[position].append({ key, value })
}
get(key) {
const position = HashTable.loseloseHashCode(key)
if (this.table[position] === undefined) return undefined
const getElementValue = node => {
if (!node && !node.element) return undefined
if (Object.is(node.element.key, key)) {
return node.element.value
} else {
return getElementValue(node.next)
}
}
return getElementValue(this.table[position].head)
}
remove(key) {
const position = HashTable.loseloseHashCode(key)
if (this.table[position] === undefined) return undefined
const getElementValue = node => {
if (!node && !node.element) return false
if (Object.is(node.element.key, key)) {
this.table[position].remove(node.element)
if (this.table[position].isEmpty) {
this.table[position] = undefined
}
return true
} else {
return getElementValue(node.next)
}
}
return getElementValue(this.table[position].head)
}
// // 使用线性探查
// put(key, value) {
// const position = HashTable.loseloseHashCode(key)
// if (this.table[position] === undefined) {
// this.table[position] = { key, value }
// } else {
// let index = position+1;
// while (this.table[index] !== undefined) {
// index++
// }
// this.table[index] = { key, value }
// }
// }
// get(key) {
// const position = HashTable.loseloseHashCode(key)
// const getElementValue = index => {
// if (this.table[index] === undefined) return undefined
// if (Object.is(this.table[index].key, key)) {
// return this.table[index].value
// } else {
// return getElementValue(index + 1)
// }
// }
// return getElementValue(position)
// }
}


• 树：由 n（n>=1）个有限节点组成一个具有层次关系的集合；把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，基本呈一对多关系，树也可以看做是图的特殊形式。

  • 节点

    • 根节点

    • 内部节点：非根节点、且有子节点的节点

    • 外部节点/页节点：无子节点的节点

  • 子树：就是大大小小节点组成的树

  • 深度：节点到根节点的节点数量

  • 高度：树的高度取决于所有节点深度中的最大值

  • 层级：也可以按照节点级别来分层

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这些定 义有助于我们写出更高效的向/从树中插人、查找和删除节点的算法。二叉树在计算机科学中的 应用非常广泛。
二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值， 在右侧节点存储（比父节点）大（或者等于）的值。

class binNode {
constructor(key) {
this.key = key
this.left = null
this.right = null
}
}
class BinarySearchTree {
constructor() {
this.root = null
}
insert(key) {
const newNode = new binNode(key)
const insertNode = (node, newNode) => {
if (newNode.key if (node.left === null) {
node.left = newNode
} else {
insertNode(node.left, newNode)
}
} else {
if (node.right === null) {
node.right = newNode
} else {
insertNode(node.right, newNode)
}
}
}
if (!this.root) {
this.root = newNode
} else {
insertNode(this.root, newNode)
}
}
}


• 图：图是网络结构的抽象模型；图是一组由边连接的节点（顶点）；任何二元关系都可以用图来表示，常见的比如：道路图、关系图，呈多对多关系。

算法

• 排序算法

  • 冒泡排序：比较任何两个相邻的项，如果第一个比第二个大，则交换它们；元素项向上移动至正确的顺序，好似气泡上升至表面一般，因此得名。

  • 选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，以此循环，直至排序完毕。

  • 插入排序：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，此算法适用于少量数据的排序，时间复杂度为 O(n^2)。

  • 归并排序：将原始序列切分成较小的序列，只到每个小序列无法再切分，然后执行合并，即将小序列归并成大的序列，合并过程进行比较排序，只到最后只有一个排序完毕的大序列，时间复杂度为 O(n log n)。

  • 快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行上述递归排序，以此达到整个数据变成有序序列，时间复杂度为 O(n log n)。
    搜索算法

  • 顺序搜索：让目标元素与列表中的每一个元素逐个比较，直到找出与给定元素相同的元素为止，缺点是效率低下。

  • 二分搜索：在一个有序列表，以中间值为基准拆分为两个子列表，拿目标元素与中间值作比较从而再在目标的子列表中递归此方法，直至找到目标元素。

• 贪心算法：在对问题求解时，不考虑全局，总是做出局部最优解的方法。

• 动态规划：在对问题求解时，由以求出的局部最优解来推导全局最优解。

• 复杂度概念：一个方法在执行的整个生命周期，所需要占用的资源，主要包括：时间资源、空间资源。

参考:
数据结构
前端数据结构