基础

时间复杂度

当前代码块执行了多少遍，多个代码块并排时（O(n)+O(1)=O(n)），去最大的时间复杂度，嵌套时则复杂度x相乘O(n)*O(n)=O(n^2)

// 时间复杂度O(logN)
// log(2)N 表示2的多少次数为N
let i = 1
while(i<n){
  console.log(i);
  i *=2;
}

空间复杂度

算法在运行过程中临时占用存储空间的大小，也有O来表示

数据结构

栈

特点：后进先出（push，pop）

栈的定义：

const stack=[];
stack.push(1); //进栈
const item=stack.pop(); //出栈

队列

特点：先进先出

队列的定义：

const queue=[];
queue.push(1); //进队
queue.shift(); //出队

链表

特点：多元素组成，存储不连续，用next指针连在一起

优点：队列在增减非首尾元素时，需要移动过多元素，而链表只需要更改next

链表的定义：

const a ={val:'a'}
const b ={val:'b'}
const c ={val:'c'}
const d ={val:'d'}

a.next = b;
b.next = c;
c.next = d;

// 遍历
let p = a;
while(p){
  console.log(p.val);
  p = p.next;
}
// 插入e
const e = {val:'e'}
e.next = d;
c.next = e;
// 删除e
c.next = d;（e被回收）

构造函数形式定义

function ListNode(){
  this.val=val;
  this.next=null;
}

//node为ListNode的实例

//删除 时间O(1) 空间O(1)
var del = node => {
  node.val=node.next.val;
  node.next=node.text.next;
}
//反转 时间O(n) 空间O(1)
var reverseList = head => {
  let p1 = head;
  let p2 = null;
  while(p1){
    const tmp = p1.next
    p1.next = p2;
    p2 = p1;
    p1 = tmp;
  }
  return p2;
}

使用场景：

// 使用链表指针获取json节点值
const json={
  a:{b:{c:1}},
  d:{e:2}
}
const path=['a','b','c']

//获取方式
let p = json;
path.forEach(k=>{
  p=p[k];
});
console.log(p);

集合

特点：无序且唯一

集合的定义：

const set = new Set();
set.add(value) //添加元素
set.clear() //清空集合
set.delete(value) //删除元素
set.has(value) //判断是否存在
set.size() //元素个数
// 迭代
for(let item of set) consle.log(item)
for(let item of set.keys()) consle.log(item)
for(let item of set.values()) consle.log(item)
for(let [key,value] of set.entries()) consle.log(item)
// set Array 转换
const arr = [...set]
const arr = Array.from(set)
const set = new Set(arr)

使用场景：

// 去重
const arr=[1,1,2,3];
const arr2 = [...new Set(arr)];

// 判断元素是否在集合中
const set = new Set([1,2,3]);
const has = set.has(2)

// 求交集
const set1 = new Set([1,2,3]);
const set2 = new Set([2,3,4]);
const set3 = new Set([...set1].filter(item=>set2.has(item)))

字典

特点：类似集合，通过键值对来存储

字典的定义：

const map = new Map();

// 增
map.set('key','value')
// 删
map.delete('key')
map.clear()
// 改
map.set('key','val')
// 查
map.get('key')

使用场景：

// 求交集
var intersection = function(num1,num2){
  const map = new Map();
  num1.forEach(n=>{
    map.set(n,true)
  })
  const res = [];
  num2.forEach(n => {
    if(map.get(n)){
      res.push(n)
      map.delete(n)
    }
  })
  return res;
}

// 代替if语句
if(t==="a" || t==="b" || t==="c") return
map.set("a",true)
map.set("b",true)
map.set("c",true)
if(map.has(t)) return

// 代替二维映射关系 （多组例如“xwx”对应21的数据）
if(a==="xwx" && b===21) return
map.set("xwx",21)
if(map.get("xwx")===21) return

树

特点：

深度优先遍历：先遍历到一棵树的最底端，再遍历第二棵

广度优先遍历：现遍历距离当前节点最近的节点

先中后序遍历：先中后指的是什么时候遍历根节点，例如先序遍历指的是先遍历根节点

树的定义：

// 数据结构
const tree = {
  val:'value',
  children:[],
}

// 深度优先遍历【1、访问根节点。2、对根节点每个children进行深度优先遍历】
const dfs = (root) => {
  console.log(root.val);
  root.children.forEach(dfs)
}

// 广度优先遍历【1、新建一个队列，把根节点入队。2、把队头出队并访问。3、把队头的children挨个入队。4、重复二、三步，知道队列为空】
const bfs = (root) => {
  const q = [root];
  while(q.length>0){
    const n = q.shift();
    console.log(v.val);
    n.children.forEach(child => {
      q.push(child)
    })
  }
}

// 二叉树数据结构
const binaryTree = {
  val: 'value',
  left: null,
  right: null,
}

// 以下遍历分为递归版遍历和非递归版遍历(利用栈的数据结构)
// 先序遍历【1、访问根节点。2、对根节点的左子树进行先序遍历。3、对根节点的右子树进行先序遍历】
const preorder = (root) => {
  if(!root) return;
  console.log(root.val);
  preorder(root.left);
  perorder(root.right);
}
const preorder = (root) => {
  if(!root) return;
  const stack = [root];
  while(stack.length){
  	const n = stack.pop();
  	console.log(n.val);
  	if (n.right) stack.push(n.right);
  	if (n.left) stack.push(n.left);
  }
}
// 中序遍历【1、对根节点的左子树进行中序遍历。2、访问根节点。3、对根节点的右子树进行中序遍历。】
const inorder = (root) => {
  if(!root) return;
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
}
const inorder = (root) => {
  if(!root) return;
  const stack = [];
  let p = root;
  while(stack.length || p){
    while(p){
    	stack.push(p);
    	p = p.left;
  	}
  	const n = stack.pop();
  	console.log(n.val);
  	p = n.right;
  }
}
// 后序遍历【1、对根节点的左子树进行后序遍历。2、对根节点的右子树进行后序遍历。3、访问根节点。】
const postorder = (root) => {
  if(!root) return;
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
}
const postorder = (root) => {
  // 利用先序遍历入栈，然后倒着输出
  if(!root) return;
  const outputStack = [];
  const stack = [root];
  while(stack.length){
    const n = stack.pop();
    outputStack(n);
    if(n.left) stack.push(n.left)
    if(n.right) stack.push(n.right) 
  }
  while(outputStack.length){
    const n = outputStack.pop();
    console.log(n.val);
  }
}

// 二叉树最大深度【利用深度优先遍历】
// 时间复杂度: O(n)
// 空间复杂度: 最优O(logN) 最差O(n)
const maxDepth = (root) => {
  let res = 0;
  const dfs = (n,l) => {
    if(!n) return;
    (!n.left && !n.right) && res = Math.max(res,l)
    dfs(n.left,l++);
    dfs(n.left,l++)
  }
  return res;
}

// 二叉树的最小深度【利用广度优先遍历】
// 时间复杂度: O(n);
// 空间复杂度: O(n)
const minDepth = (root) => {
  if(!root) return 0;
  const q = [[root,1];
  while(q.length){
    const n =q.shift();
    if(!n.left && !n.right) return l;
    if(n.left) q.push([n.left,l++])
    if(n.right) q.push([n.right,l++])
  }
  
}

使用场景：

// 渲染Antd中的树组件

const json = [{title:'',key:'',children:[]}];
const Com = () => {
  const dfs = (n) => (
  	<TreeNode title={n.title} key={n.key}>
    	{n.children.map(dfs)}
  	</TreeNode>
	)
	return <Tree>{json.map(dfs)}</Tree> 
}

堆

特点：

• 堆是一种特殊的完全二叉树，特殊在所有节点都大于等于它的子节点或者都小于等于它的子节点（最大堆、最小堆）。
• 因为他是完全二叉树，所以在JS中可以用数组来表示堆
• 左侧子节点的位置是2*index+1（index从0开始计）
• 右侧子节点的位置是2*index+2
• 父节点的位置(index-1)/2
• 因为是数组的原因，所以可以很快的找到某个节点的关系节点。堆可以高效快速的找到最大最小值，即时间复杂度为O(1)。

堆的定义：

// 最小堆列及其插入、删除堆顶、获取堆顶、获取堆的大小
class MinHeap{
  constructor(){
    this.heap = [];
  }
  getLeftIndex(i){
    return i * 2 + 1
  }
  getRightIndex(i){
    return i * 2 + 2
  }
  getParentIndex(i){
    return (i - 1) >> 1;// 除2取商
  }
  swap(i1,i2){
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  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);
    }
  }
  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);
    }
  }
  insert(value) {
    //时间复杂度O(logK) k为堆的大小
    this.heap.push(value);
    this.shiftUp(this.heap.length-1);
  }
  pop(){
    // 删除堆顶的时候通过将末尾元素替换顶元素，然后下移替换后的顶元素 时间复杂度O(logK) k为堆的大小
    this.heap[0] = this.heap.pop();
    this.shiftDown(0)
  }
  peek(){
    return this.heap[0];
  }
  size(){
    teturn this.heap.length;
  }
}

// 第k个最大元素
// 1、构建一个最小堆，并依次插入堆中
// 2、当堆的容量超过k，就删除堆顶元素
// 3、插入结束，堆顶就是第k个最大元素
const findKthLargest = (nums,k) => {
  // 时间复杂度 O(N*logK)
  // 空间复杂度 O(K)
  const h = new MinHeap();
  nums.forEach(n => {
    h.insert(n);
    h.size>k && h.pop 
  })
  return h.peek();
}

排序

冒泡排序

遍历n-1遍，比较相邻元素，将最大的冒泡到最后面

时间复杂度：O(n*2)

空间复杂度：O(1)

Array.prototype.bubbleSort = function() {
    for(let i=0;i<this.length-1;i++){
        for(let j=0;j<this.length-1-i;j++){
            if(this[j]>this[j+1]){
                const tem=this[j];
                this[j]=this[j+1];
                this[j+1]=tem;
            }
        }
    }
    return arr 
}

选择排序

遍历n-1遍，每一遍遍历完成后将最小的置于最前面

时间复杂度：O(n*2)

空间复杂度：O(1)

Array.prototype.selectionSort = function() {
    for(let i=0;i<this.length-1;i++){
        const min=i;
        for(let j=i;j<this.length;j++){
            if(this[j]<this[min]){
                min = j;
            }
        }
        if(min !== i){
        	const temp = this[i];
        	this[i] = this[min];
        	this[min] = temp;
        }
    }
}

插入排序

进行n-1轮，第二个数开始和前面的每个数相比比，比他大就往后排，一次类推进行到最后一个数。

时间复杂度：O(n^2)

Array.prototype.insertSort = function(){
    for(let i=1;i<this.length;i++){
        const temp = this[i];
        let j = i;
        while(j>0){
            if(this[j-1]>temp){
               this[j]=temp[j-1]
            }else{
                break;
            }
            j--;
        }
        this[j]=temp;
    }
}

归并排序

（分）把数组劈成两半，再分别对子数组进行分的操作，知道分成一个个单独的数。（合）把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组合并为一个完整数组。

新建一个空数组res，用域存放最终排序后的数组，比骄傲两个有序数组的头部，较小者出队推入 res，如果两个数组还有数值，就重复比较头部的步骤。

时间复杂度：O(n*logN)

Array.prototype.mergeSort = function () {
    const rec = (arr) => {
        if (arr.length === 1) return arr
        const mid = Math.floor(arr.length / 2);
        const left = arr.slice(0,mid);
        const right = arr.slice(mid,arr.length);
        const orderLeft = rec(left);
        const orderRight = rec(right);
        const res= [];
        while (orderLeft.length || orderRight.length) {
        	if (orderLeft.length && orderRight.length){
                res.push(orderLeft[0]<orderRight?orderLeft[0]:orderRight[0])
            } else if (orderLeft.length){
            	res.push(orderLeft.shift())
            } else if (orderRiight.length){
                res.push(orderRight.shift())
            }       
        }
    }
    const res = rec(this);
    res.forEach((n,i) => this[i]=n);
}

快速排序

数组中任意选择一个“基准”，所有比基准小的放在基准前面，比基准大的放到它的后面。递归实现上述操作。

时间复杂度：O(n*logN)

Array.prototype.quickSort = function(){
  const rec = () => {
    if(arr.length === 1){return arr;}
    const left = [];
    const right = [];
    const mid = arr[0];
    for(let i = 1;i<add.length;i++){
      if(arr[i]<mid){
        left.push(arr[i]);
      }else{
        right.push(arr[i])
      }
    }
    return [...rec(left),mid,...rec(right)]
  };
  const res=rec(this);
  res.for((n,i)=>{this[i]=n})
}

搜索

顺序搜索

遍历数组

时间复杂度：O(n)

Array.prototype.sequentialSearch = function (item){
    for(let i = 0; i<this.length; i++){
        if(this[i] === item){
        	return i;   
        }
    }
    return -1
}

二分搜索（折半搜索）

搜索数组必须有序，从中间元素开始，如果中概念元素正好是目标值，则搜索结束。如果目标大于或小于中间元素，则在大于或者小于中间元素的那一半继续进行上述过程。

时间复杂度：O(logN)

Array.prototype.binarySearch = function(item){
    let low = 0;
    let high = this.length - 1;
    while(low<=high){
    	const mid = Math.floor((low+high)/2);
        const element = this[mid];
        if(element<item){
            low=mid+1;
        }else if(element>item){
            high=mid-1;
        }else {
            return mid;
        }
    }
    return -1;
}