# 计算机基础

classStack{constructor(){this.stack=[]}push(item){this.stack.push(item)}pop(){this.stack.pop()}peek(){returnthis.stack[this.getCount()-1]}getCount(){returnthis.stack.length}isEmpty(){returnthis.getCount()===0}}

varisValid=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)returnfalse}}if(stack.length>0)returnfalsereturntrue};

classQueue{constructor(){this.queue=[]}enQueue(item){this.queue.push(item)}deQueue(){returnthis.queue.shift()}getHeader(){returnthis.queue[0]}getLength(){returnthis.queue.length}isEmpty(){returnthis.getLength()===0}}

classSqQueue{constructor(length){this.queue=newArray(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]= itemthis.size++this.last=(this.last+1)%this.queue.length}deQueue(){if(this.isEmpty()){throwError('Queue is empty')}let r=this.queue[this.first]this.queue[this.first]=nullthis.first=(this.first+1)%this.queue.lengththis.size--// 判断当前队列大小是否过小// 为了保证不浪费空间，在队列空间等于总长度四分之一时// 且不为 2 时缩小总长度为当前的一半if(this.size===this.getLength()/4&&this.getLength()/2!==0){this.resize(this.getLength()/2)}return r}getHeader(){if(this.isEmpty()){throwError('Queue is empty')}returnthis.queue[this.first]}getLength(){returnthis.queue.length-1}isEmpty(){returnthis.first===this.last}resize(length){let q=newArray(length)for(let i=0; i< length; i++){      q[i]=this.queue[(i+this.first)%this.queue.length]}this.queue= qthis.first=0this.last=this.size}}

classNode{constructor(v, next){this.value= vthis.next= next}}classLinkList{constructor(){// 链表长度this.size=0// 虚拟头部this.dummyNode=newNode(null,null)}find(header, index, currentIndex){if(index=== currentIndex)return headerreturnthis.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=newNode(v, prev.next)this.size++return prev.next}insertNode(v, index){returnthis.addNode(v, index)}addToFirst(v){returnthis.addNode(v,0)}addToLast(v){returnthis.addNode(v,this.size)}removeNode(index, isLast){this.checkIndex(index)    index= isLast? index-1: indexlet prev=this.find(this.dummyNode, index,0)let node= prev.next    prev.next= node.next    node.next=nullthis.size--return node}removeFirstNode(){returnthis.removeNode(0)}removeLastNode(){returnthis.removeNode(this.size,true)}checkIndex(index){if(index<0|| index>this.size)throwError('Index error')}getNode(index){this.checkIndex(index)if(this.isEmpty())returnreturnthis.find(this.dummyNode, index,0).next}isEmpty(){returnthis.size===0}getSize(){returnthis.size}}

// 先序遍历可用于打印树的结构// 先序遍历先访问根节点，然后访问左节点，最后访问右节点。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)returnnulllet q=newQueue()// 将根节点入队  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(){returnthis._getMin(this.root).value}_getMin(node){if(!node.left)return nodereturnthis._getMin(node.left)}getMax(){returnthis._getMax(this.root).value}_getMax(node){if(!node.right)return nodereturnthis._getMin(node.right)}

floor(v){let node=this._floor(this.root, v)return node? node.value:null}_floor(node, v){if(!node)returnnullif(node.value=== v)return v// 如果当前节点值还比需要的值大，就继续递归if(node.value> v){returnthis._floor(node.left, v)}// 判断当前节点是否拥有右子树let right=this._floor(node.right, v)if(right)return rightreturn node}

classNode{constructor(value){this.value= valuethis.left=nullthis.right=null// 修改代码this.size=1}}// 新增代码_getSize(node){return node? node.size:0}_addChild(node, v){if(!node){returnnewNode(v)}if(node.value> v){// 修改代码    node.size++    node.left=this._addChild(node.left, v)}elseif(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)returnnull// 先获取左子树下有几个节点let size= node.left? node.left.size:0// 判断 size 是否大于 k// 如果大于 k，代表所需要的节点在左节点if(size> k)returnthis._select(node.left, k)// 如果小于 k，代表所需要的节点在右节点// 注意这里需要重新计算 k，减去根节点除了右子树的节点数量if(size< k)returnthis._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)+1return node}

delect(v){this.root=this._delect(this.root, v)}_delect(node, v){if(!node)returnnull// 寻找的节点比当前节点小，去左子树找if(node.value< v){    node.right=this._delect(node.right, v)}elseif(node.value> v){// 寻找的节点比当前节点大，去右子树找    node.left=this._delect(node.left, v)}else{// 进入这个条件说明已经找到节点// 先判断节点是否拥有拥有左右子树中的一个// 是的话，将子树返回出去，这里和 `_delectMin` 的操作一样if(!node.left)return node.rightif(!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)+1return node}

classMaxHeap{constructor(){this.heap=[]}size(){returnthis.heap.length}empty(){returnthis.size()==0}add(item){this.heap.push(item)this._shiftUp(this.size()-1)}removeMax(){this._shiftDown(0)}getParentIndex(k){returnparseInt((k-1)/2)}getLeftIndex(k){return k*2+1}_shiftUp(k){// 如果当前节点比父节点大，就交换while(this.heap[k]>this.heap[this.getParentIndex(k)]){this._swap(k,this.getParentIndex(k))// 将索引变成父节点      k=this.getParentIndex(k)}}_shiftDown(k){// 交换首位并删除末尾this._swap(k,this.size()-1)this.heap.splice(this.size()-1,1)// 判断节点是否有左孩子，因为二叉堆的特性，有右必有左while(this.getLeftIndex(k)<this.size()){let j=this.getLeftIndex(k)// 判断是否有右孩子，并且右孩子是否大于左孩子if(j+1<this.size()&&this.heap[j+1]>this.heap[j]) j++// 判断父节点是否已经比子节点都大if(this.heap[k]>=this.heap[j])breakthis._swap(k, j)      k= j}}_swap(left, right){let rightValue=this.heap[right]this.heap[right]=this.heap[left]this.heap[left]= rightValue}}

functionsum(a, b){if(a==0)return bif(b==0)return alet newA= a^ blet newB=(a& b)<<1returnsum(newA, newB)}

functionbubble(array){checkArray(array);for(let i= array.length-1; i>0; i--){// 从 0 到 `length - 1` 遍历for(let j=0; j< i; j++){if(array[j]> array[j+1])swap(array, j, j+1)}}return array;}

functioninsertion(array){checkArray(array);for(let i=1; i< array.length; i++){for(let j= i-1; j>=0&& array[j]> array[j+1]; j--)swap(array, j, j+1);}return array;}

functionselection(array){checkArray(array);for(let i=0; i< array.length-1; i++){let minIndex= i;for(let j= i+1; j< array.length; j++){      minIndex= array[j]< array[minIndex]? j: minIndex;}swap(array, i, minIndex);}return array;}

functionsort(array){checkArray(array);mergeSort(array,0, array.length-1);return array;}functionmergeSort(array, left, right){// 左右索引相同说明已经只有一个数if(left=== right)return;// 等同于 `left + (right - left) / 2`// 相比 `(left + right) / 2` 来说更加安全，不会溢出// 使用位运算是因为位运算比四则运算快let mid=parseInt(left+((right- left)>>1));mergeSort(array, left, mid);mergeSort(array, mid+1, right);let help=[];let i=0;let p1= left;let p2= mid+1;while(p1<= mid&& p2<= right){    help[i++]= array[p1]< array[p2]? array[p1++]: array[p2++];}while(p1<= mid){    help[i++]= array[p1++];}while(p2<= right){    help[i++]= array[p2++];}for(let i=0; i< help.length; i++){    array[left+ i]= help[i];}return array;}

mergeSort(data,0,6)// mid = 3mergeSort(data,0,3)// mid = 1mergeSort(data,0,1)// mid = 0mergeSort(data,0,0)// 遇到终止，回退到上一步mergeSort(data,1,1)// 遇到终止，回退到上一步// 排序 p1 = 0, p2 = mid + 1 = 1// 回退到 `mergeSort(data, 0, 3)` 执行下一个递归mergeSort(2,3)// mid = 2mergeSort(3,3)// 遇到终止，回退到上一步// 排序 p1 = 2, p2 = mid + 1 = 3// 回退到 `mergeSort(data, 0, 3)` 执行合并逻辑// 排序 p1 = 0, p2 = mid + 1 = 2// 执行完毕回退// 左边数组排序完毕，右边也是如上轨迹

functionsort(array){checkArray(array);quickSort(array,0, array.length-1);return array;}functionquickSort(array, left, right){if(left< right){swap(array,, right)// 随机取值，然后和末尾交换，这样做比固定取一个位置的复杂度略低let indexs=part(array,parseInt(Math.random()*(right- left+1))+ left, right);quickSort(array, left, indexs[0]);quickSort(array, indexs[1]+1, right);}}functionpart(array, left, right){let less= left-1;let more= right;while(left< more){if(array[left]< array[right]){// 当前值比基准值小，`less` 和 `left` 都加一	++less;++left;}elseif(array[left]> array[right]){// 当前值比基准值大，将当前值和右边的值交换// 并且不改变 `left`，因为当前换过来的值还没有判断过大小swap(array,--more, left);}else{// 和基准值相同，只移动下标      left++;}}// 将基准值和比基准值大的第一个值交换位置// 这样数组就变成 `[比基准值小, 基准值, 比基准值大]`swap(array, right, more);return[less, more];}

varsortColors=function(nums){let left=-1;let right= nums.length;let i=0;// 下标如果遇到 right，说明已经排序完成while(i< right){if(nums[i]==0){swap(nums, i++,++left);}elseif(nums[i]==1){      i++;}else{swap(nums, i,--right);}}};

varreverseList=function(head){// 判断下变量边界问题if(!head||!head.next)return head// 初始设置为空，因为第一个节点反转后就是尾部，尾部节点指向 nulllet pre=nulllet current= headlet next// 判断当前节点是否为空// 不为空就先获取当前节点的下一节点// 然后把当前节点的 next 设为上一个节点// 然后把 current 设为下一个节点，pre 设为当前节点while(current){        next= current.next        current.next= pre        pre= current        current= next}return pre};

functionTreeNode(val){this.val= val;this.left=this.right=null;}vartraversal=function(root){if(root){// 先序    console.log(root);traversal(root.left);// 中序// console.log(root);traversal(root.right);// 后序// console.log(root);}};

functionpre(root){if(root){let stack=[];// 先将根节点 push    stack.push(root);// 判断栈中是否为空while(stack.length>0){// 弹出栈顶元素      root= stack.pop();      console.log(root);// 因为先序遍历是先左后右，栈是先进后出结构// 所以先 push 右边再 push 左边if(root.right){        stack.push(root.right);}if(root.left){        stack.push(root.left);}}}}

functionmid(root){if(root){let stack=[];// 中序遍历是先左再根最后右// 所以首先应该先把最左边节点遍历到底依次 push 进栈// 当左边没有节点时，就打印栈顶元素，然后寻找右节点// 对于最左边的叶节点来说，可以把它看成是两个 null 节点的父节点// 左边打印不出东西就把父节点拿出来打印，然后再看右节点while(stack.length>0|| root){if(root){        stack.push(root);        root= root.left;}else{        root= stack.pop();        console.log(root);        root= root.right;}}}}

functionpos(root){if(root){let stack1=[];let stack2=[];// 后序遍历是先左再右最后根	// 所以对于一个栈来说，应该先 push 根节点// 然后 push 右节点，最后 push 左节点    stack1.push(root);while(stack1.length>0){      root= stack1.pop();      stack2.push(root);if(root.left){        stack1.push(root.left);}if(root.right){        stack1.push(root.right);}}while(stack2.length>0){      console.log(s2.pop());}}}

functionpredecessor(node){if(!node)return// 结论 1if(node.left){returngetRight(node.left)}else{let parent= node.parent// 结论 2 3 的判断while(parent&& parent.right=== node){      node= parent      parent= node.parent}return parent}}functiongetRight(node){if(!node)return  node= node.rightwhile(node) node= node.rightreturn node}

functionsuccessor(node){if(!node)return// 结论 1if(node.right){returngetLeft(node.right)}else{// 结论 2let parent= node.parent// 判断 parent 为空while(parent&& parent.left=== node){      node= parent      parent= node.parent}return parent}}functiongetLeft(node){if(!node)return  node= node.leftwhile(node) node= node.leftreturn node}

varmaxDepth=function(root){if(!root)return0return Math.max(maxDepth(root.left),maxDepth(root.right))+1};