常德市建设局网站,写网站编程需要什么,优化大师怎么样,如何做谷歌优化1 栈
概念
栈是⼀个线性结构#xff0c;在计算机中是⼀个相当常⻅的数据结构。栈的特点是只能在某⼀端添加或删除数据#xff0c;遵循先进后出的原则
实现
每种数据结构都可以⽤很多种⽅式来实现#xff0c;其实可以把栈看成是数组的⼀个⼦集#xff0c;所以这⾥使⽤数…1 栈
概念
栈是⼀个线性结构在计算机中是⼀个相当常⻅的数据结构。栈的特点是只能在某⼀端添加或删除数据遵循先进后出的原则
实现
每种数据结构都可以⽤很多种⽅式来实现其实可以把栈看成是数组的⼀个⼦集所以这⾥使⽤数组来实现
class Stack {
constructor() {
this.stack []
}
push(item) {
this.stack.push(item)
}
pop() {
this.stack.pop()
}
peek() {
return this.stack[this.getCount() - 1]
}
getCount() {
return this.stack.length
}
isEmpty() {
return this.getCount() 0
}
}应⽤
匹配括号可以通过栈的特性来完成
var isValid function (s) {
let map {
(: -1,
): 1,
[: -2,
]: 2,
{: -3,
}: 3
}
let stack []
for (let i 0; i s.length; i) {
if (map[s[i]] 0) {
stack.push(s[i])
} else {
let last stack.pop()
if (map[last] map[s[i]] ! 0) return false
}
}
if (stack.length 0) return false
return true
};2 队列
概念
队列⼀个线性结构特点是在某⼀端添加数据在另⼀端删除数据遵循先进先出的原则
实现
这⾥会讲解两种实现队列的⽅式分别是单链队列和循环队列
单链队列
class Queue {
constructor() {
this.queue []
}
enQueue(item) {
this.queue.push(item)
}
deQueue() {
return this.queue.shift()
}
getHeader() {
return this.queue[0]
}
getLength() {
return this.queue.length
}
isEmpty() {
return this.getLength() 0
}
}因为单链队列在出队操作的时候需要 O(n) 的时间复杂度所以引⼊了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度
循环队列
class SqQueue {
constructor(length) {
this.queue new Array(length 1)
// 队头
this.first 0
// 队尾
this.last 0// 当前队列⼤⼩
this.size 0
}
enQueue(item) {
// 判断队尾 1 是否为队头
// 如果是就代表需要扩容数组
// % this.queue.length 是为了防⽌数组越界
if (this.first (this.last 1) % this.queue.length) {
this.resize(this.getLength() * 2 1)
}
this.queue[this.last] item
this.size
this.last (this.last 1) % this.queue.length
}
deQueue() {
if (this.isEmpty()) {
throw Error(Queue is empty)
}
let r this.queue[this.first]
this.queue[this.first] null
this.first (this.first 1) % this.queue.length
this.size--
// 判断当前队列⼤⼩是否过⼩
// 为了保证不浪费空间在队列空间等于总⻓度四分之⼀时
// 且不为 2 时缩⼩总⻓度为当前的⼀半
if (this.size this.getLength() / 4 this.getLength() / 2 ! 0) {
this.resize(this.getLength() / 2)
}
return r
}
getHeader() {
if (this.isEmpty()) {
throw Error(Queue is empty)
}
return this.queue[this.first]
}
getLength() {
return this.queue.length - 1
}
isEmpty() {
return this.first this.last
}
resize(length) {
let q new Array(length)
for (let i 0; i length; i) {
q[i] this.queue[(i this.first) % this.queue.length]
}
this.queue q
this.first 0
this.last this.size
}
}3 链表
概念
链表是⼀个线性结构同时也是⼀个天然的递归结构。链表结构可以充分利⽤ 计算机内存空间实现灵活的内存动态管理。但是链表失去了数组随机读取的优点同时链表由于增加了结点的指针域空间开销⽐较⼤ 实现
单向链表
class Node {
constructor(v, next) {
this.value v
this.next next
}
}
class LinkList {
constructor() {
// 链表⻓度
this.size 0
// 虚拟头部
this.dummyNode new Node(null, null)
}
find(header, index, currentIndex) {
if (index currentIndex) return header
return this.find(header.next, index, currentIndex 1)
}
addNode(v, index) {
this.checkIndex(index)
// 当往链表末尾插⼊时prev.next 为空
// 其他情况时因为要插⼊节点所以插⼊的节点
// 的 next 应该是 prev.next// 然后设置 prev.next 为插⼊的节点
let prev this.find(this.dummyNode, index, 0)
prev.next new Node(v, prev.next)
this.size
return prev.next
}
insertNode(v, index) {
return this.addNode(v, index)
}
addToFirst(v) {
return this.addNode(v, 0)
}
addToLast(v) {
return this.addNode(v, this.size)
}
removeNode(index, isLast) {
this.checkIndex(index)
index isLast ? index - 1 : index
let prev this.find(this.dummyNode, index, 0)
let node prev.next
prev.next node.next
node.next null
this.size--
return node
}
removeFirstNode() {
return this.removeNode(0)
}
removeLastNode() {
return this.removeNode(this.size, true)
}
checkIndex(index) {
if (index 0 || index this.size) throw Error(Index error)
}
getNode(index) {
this.checkIndex(index)
if (this.isEmpty()) return
return this.find(this.dummyNode, index, 0).next
}
isEmpty() {
return this.size 0
}
getSize() {
return this.size
}
}4 树
⼆叉树
树拥有很多种结构⼆叉树是树中最常⽤的结构同时也是⼀个天然的递归结构。⼆叉树拥有⼀个根节点每个节点⾄多拥有两个⼦节点分别为左节点和右节点。树的最底部节点称之为叶节点当⼀颗树的叶数量数量为满时该树可以称之为满⼆叉树
⼆分搜索树
⼆分搜索树也是⼆叉树拥有⼆叉树的特性。但是区别在于⼆分搜索树每个节点的值都⽐他的左⼦树的值⼤⽐右⼦树的值⼩这种存储⽅式很适合于数据搜索。如下图所示当需要查找 6 的时候因为需要查找的值⽐根节点的值⼤所以只需要在根节点的右⼦树上寻找⼤⼤提⾼了搜索效率
实现
class Node {
constructor(value) {
this.value value
this.left null
this.right null
}
}
class BST {
constructor() {
this.root null
this.size 0
}
getSize() {
return this.size
}
isEmpty() {
return this.size 0
}
addNode(v) {
this.root this._addChild(this.root, v)
}
// 添加节点时需要⽐较添加的节点值和当前
// 节点值的⼤⼩
_addChild(node, v) {
if (!node) {
this.size
return new Node(v)
}
if (node.value v) {
node.left this._addChild(node.left, v)
} else if (node.value v) {
node.right this._addChild(node.right, v)
}
return node
}
}以上是最基本的⼆分搜索树实现接下来实现树的遍历。对于树的遍历来说有三种遍历⽅法分别是先序遍历、中序遍历、后序遍历。三种遍历的区别在于何时访问节点。在遍历树的过程中每个节点都会遍历三次分别是遍历到⾃⼰遍历左⼦树和遍历右⼦树。如果需要实现先序遍历那么只需要第⼀次遍历到节点时进⾏操作即可
// 先序遍历可⽤于打印树的结构
// 先序遍历先访问根节点然后访问左节点最后访问右节点。
preTraversal() {
this._pre(this.root)
}
_pre(node) {
if (node) {
console.log(node.value)
this._pre(node.left)
this._pre(node.right)
}
}
// 中序遍历可⽤于排序
// 对于 BST 来说中序遍历可以实现⼀次遍历就
// 得到有序的值
// 中序遍历表示先访问左节点然后访问根节点最后访问右节点。
midTraversal() {
this._mid(this.root)
}
_mid(node) {
if (node) {
this._mid(node.left)
console.log(node.value)
this._mid(node.right)
}
}
// 后序遍历可⽤于先操作⼦节点
// 再操作⽗节点的场景
// 后序遍历表示先访问左节点然后访问右节点最后访问根节点。
backTraversal() {
this._back(this.root)
}
_back(node) {
if (node) {
this._back(node.left)
this._back(node.right)
console.log(node.value)
}
}以上的这⼏种遍历都可以称之为深度遍历对应的还有种遍历叫做⼴度遍历也就是⼀层层地遍历树。对于⼴度遍历来说我们需要利⽤之前讲过的队列结构来完成
breadthTraversal() {
if (!this.root) return null
let q new Queue()
// 将根节点⼊队
q.enQueue(this.root)
// 循环判断队列是否为空为空
// 代表树遍历完毕
while (!q.isEmpty()) {
// 将队⾸出队判断是否有左右⼦树
// 有的话就先左后右⼊队
let n q.deQueue()
console.log(n.value)
if (n.left) q.enQueue(n.left)
if (n.right) q.enQueue(n.right)
}
}接下来先介绍如何在树中寻找最⼩值或最⼤数。因为⼆分搜索树的特性所以最⼩值⼀定在根节点的最左边最⼤值相反
getMin() {
return this._getMin(this.root).value
}
_getMin(node) {
if (!node.left) return node
return this._getMin(node.left)
}
getMax() {
return this._getMax(this.root).value
}
_getMax(node) {
if (!node.right) return node
return this._getMin(node.right)
}向上取整和向下取整这两个操作是相反的所以代码也是类似的这⾥只介绍如何向下取整。既然是向下取整那么根据⼆分搜索树的特性值⼀定在根节点的左侧。只需要⼀直遍历左⼦树直到当前节点的值不再⼤于等于需要的值然后判断节点是否还拥有右⼦树。如果有的话继续上⾯的递归判断
floor(v) {
let node this._floor(this.root, v)
return node ? node.value : null
}
_floor(node, v) {
if (!node) return null
if (node.value v) return v
// 如果当前节点值还⽐需要的值⼤就继续递归
if (node.value v) {
return this._floor(node.left, v)
}
// 判断当前节点是否拥有右⼦树
let right this._floor(node.right, v)
if (right) return right
return node
}排名这是⽤于获取给定值的排名或者排名第⼏的节点的值这两个操作也是相反的所以这个只介绍如何获取排名第⼏的节点的值。对于这个操作⽽⾔我们需要略微的改造点代码让每个节点拥有⼀个 size 属性。该属性表示该节点下有多少⼦节点包含⾃身
class Node {
constructor(value) {
this.value value
this.left null
this.right null
// 修改代码
this.size 1
}
}
// 新增代码
_getSize(node) {
return node ? node.size : 0
}
_addChild(node, v) {
if (!node) {
return new Node(v)
}
if (node.value v) {
// 修改代码
node.size
node.left this._addChild(node.left, v)
} else if (node.value v) {
// 修改代码
node.size
node.right this._addChild(node.right, v)
}
return node
}
select(k) {
let node this._select(this.root, k)
return node ? node.value : null
}
_select(node, k) {
if (!node) return null
// 先获取左⼦树下有⼏个节点
let size node.left ? node.left.size : 0
// 判断 size 是否⼤于 k
// 如果⼤于 k代表所需要的节点在左节点
if (size k) return this._select(node.left, k)
// 如果⼩于 k代表所需要的节点在右节点
// 注意这⾥需要重新计算 k减去根节点除了右⼦树的节点数量
if (size k) return this._select(node.right, k - size - 1)
return node
}接下来讲解的是⼆分搜索树中最难实现的部分删除节点。因为对于删除节点来说会存在以下⼏种情况 需要删除的节点没有⼦树需要删除的节点只有⼀条⼦树需要删除的节点有左右两条树对于前两种情况很好解决但是第三种情况就有难度了所以先来实现相对简单的操作删除最⼩节点对于删除最⼩节点来说是不存在第三种情况的删除最⼤节点操作是和删除最⼩节点相反的所以这⾥也就不再赘述
delectMin() {
this.root this._delectMin(this.root)
console.log(this.root)
}
_delectMin(node) {
// ⼀直递归左⼦树
// 如果左⼦树为空就判断节点是否拥有右⼦树
// 有右⼦树的话就把需要删除的节点替换为右⼦树
if ((node ! null) !node.left) return node.right
node.left this._delectMin(node.left)
// 最后需要重新维护下节点的 size
node.size this._getSize(node.left) this._getSize(node.right) 1
return node
}
delect(v) {
this.root this._delect(this.root, v)
}最后讲解的就是如何删除任意节点了。对于这个操作 T.Hibbard 在 1962 年提出了解决这个难题的办法也就是如何解决第三种情况。当遇到这种情况时需要取出当前节点的后继节点也就是当前节点右⼦树的最⼩节点来替换需要删除的节点。然后将需要删除节点的左⼦树赋值给后继结点右⼦树删除后继结点后赋值给他。你如果对于这个解决办法有疑问的话可以这样考虑。因为⼆分搜索树的特性⽗节点⼀定⽐所有左⼦节点⼤⽐所有右⼦节点⼩。那么当需要删除⽗节点时势必需要拿出⼀个⽐⽗节点⼤的节点来替换⽗节点。这个节点肯定不存在于左⼦树必然存在于右⼦树。然后⼜需要保持⽗节点都是⽐右⼦节点⼩的那么就可以取出右⼦树中最⼩的那个节点来替换⽗节点
_delect(node, v) {
if (!node) return null
// 寻找的节点⽐当前节点⼩去左⼦树找
if (node.value v) {
node.right this._delect(node.right, v)
} else if (node.value v) {
// 寻找的节点⽐当前节点⼤去右⼦树找
node.left this._delect(node.left, v)
} else {
// 进⼊这个条件说明已经找到节点
// 先判断节点是否拥有拥有左右⼦树中的⼀个
// 是的话将⼦树返回出去这⾥和 _delectMin 的操作⼀样
if (!node.left) return node.right
if (!node.right) return node.left
// 进⼊这⾥代表节点拥有左右⼦树
// 先取出当前节点的后继结点也就是取当前节点右⼦树的最⼩值
let min this._getMin(node.right)
// 取出最⼩值后删除最⼩值
// 然后把删除节点后的⼦树赋值给最⼩值节点
min.right this._delectMin(node.right)
// 左⼦树不动
min.left node.left
node min
}
// 维护 size
node.size this._getSize(node.left) this._getSize(node.right) 1
return node
}
