35、算法基础

算法基础

数组

数组相关声明式方法都是高阶函数，都没有改变原数组

• 数组静态方法
  • from
  • of
  • isArray

//from    从一个类数组，或者可迭代对象创建一个新的，浅拷贝的数组实例
const set = new Set(['foo','smile','yqp'])
console.log(Array.from(set))        //['foo','smile','yqp']

//of    创建一个可变数量参数的数组实例，所有参数列表作为元素，创建一个新数组
console.log(Array.of(3))        //[3]
console.log(Array.of(3,5,7,8))        //[3,5,7,8]

//isArray    判断是否是数组
console.log(Array.isArray([1,2,3]))    //true
console.log(Array.isArray({1,2,3,4}))        //false

• 数组更新的方法
  • push
  • pop
  • unshift
  • shift
  • sort
  • reverse
  • splice

const arr = [1,2,4,7,9,3]

//push    
//1、数组最后添加6
arr.push(6)        //[1,2,4,7,9,3,6]
//2、数组最后一次添加8和9
arr.push(8,8)        // [1,2,4,7,9,3,8,9]
//2、数组最后添加包含8和9的数组
arr.push([8,9])        // [1,2,4,7,9,3,[8,9]]

//pop    删除数组最后一个元素
arr.pop()        //9 pop方法返回的是删除的最后一个元素的值  原数组变成[1,2,4,7,9]

//unshift  
//1、在数组最前面添加2
arr.unshift(2)        //[2,1,2,4,7,9,3]
//2、在数组最前面添加4和3
arr.unshift(4,3)        //[4,3,1,2,4,7,9,3]

//shift 删除数组的第一个元素
arr.shift()        //1 返回被删元素值    原数组变成[2,4,7,9,3]

//sort 数组降序排列;sort的回调函数返回值为数值，分为dayu0，等于0，小于0；大于0item2放在左边
arr.sort((item1,item2)=>{return item2 -item1})    //sort改变原数组；返回值也是改变之后排序的数组

//splice    
//1、删除第三个元素;两个参数，第一个index第二个是个数 
arr.splice(2,1)
//2、删除第将第三个元素替换为10
arr.splice(2,1，10)
//3、将11插入为数组的第三个元素
arr.splice(2,0,11)

• 数组遍历相关的声明式方法
  • forEach
  • map
  • reduce
  • filter
  • find
  • findIndex
  • some
  • every
  • slice返回一个新的数组，包含从 start 到 end。不会修改数组，而是返回一个子数组。arrayObject.slice(start,end)
• 数组的其他方法
  • length
  • join
  • contact被合并的可以是数组也可以是元素。arr.concat([1,3],4)，如果是数组就把数组中的元素取出来
  • indexOf，找到元素下标
  • lastIndexOf

自定义栈Stack

• 栈的几个功能方法
  • 进栈（压栈）push
  • 出栈pop
  • 产看栈顶peek
  • 栈中元素个数size
  • 是否空栈isEmpty

function Stack(){
  //用于保存元素数据的数组
  const arr = [];

  this.push = function(element){
    arr.push(element)
  }

  this.pop = function(){
    arr.pop()
  }

  this.peek = function(){
    return arr[arr.length-1]
  }

  this.size = function(){
    return arr.length
  }

  this.isEmpty = function(){
    return arr.length === 0 ?true:false
  }  
}

export default Stack;

• 栈应用（栈十进制转二进制：除2取余，倒序排列，高位补0）。数组实现十进制转二进制。

function edc2bin(decNum){
  //创建一个用于保存二进制的array。Array改为Stack就是栈应用
  const arr = new Array();    
  while(decNum>0){
    const remainder = decNum % 2;        //取余
    arr.push(remainder);        
    decNum = Math.floor(decNum / 2);     //向下取整数
  }
  //依次
  let result = ''
  while(arr.length !== 0){
    result = result + arr.pop() 
  }
  return result;
}

队列Queue

function Queue(){
  const arr = [];

  this.enqueue = function(element){
    arr.push(element)
  }

  this.dequeue = function(){
    arr.shift()        //删除数组的第一个元素并且返回
  }

  this.front = function(){        //查看队列第一个
    return arr[0]
  }
   this.size = function(){
    return arr.length
  }

  this.isEmpty = function(){
    return arr.length === 0 ?true:false
  }  
}

export default Queue;

• 队列击鼓传花（队列头依次放到后面去；并且删除指定的第几个 ）
  • 创建一个空queue
  • 将数组中的所有元素依次放入queue
  • 将队列中num-1元素依次转移到队列最后，将队头部元素删除（只要队列的size>1就不断做，直到剩下最后一个，就是目标元素 ）

function passGame(names,num){
  //创建一个空queue
  const queue = new Queue();

  //将数组中的所有元素(name和index)依次放入queue
  names.forEach((name,index)=>{
  console.log(name,index)
    queue.enqueue({name,index})
  })

  while(queue.size() > 1){
    for(let i = 0;i < num;i++){
      queue.enqueue(queue.dequeue())
    }
    //删除头部元素
    queue.dequeue(queue.front())
  }
  const {name,index} = queue.front()
  return `${name}是最后一个，它的index是第${index}个`
}

var names = ['a','b','c','d','e']
passGame(names,3)

• 优先级队列
  • 传入值优先级。标记优先级，优先级高的先出

链表(单项链表->只有next、双向链表->有front和next)

树（dom树）

二叉树BT：一个节点有最多两个子节点

二叉搜索树BST：满足二叉树的基础上，值左边小，右边大

集合

元素唯一不能重复。ES6中集合的实现是用数组实现的。当然集合也可以用Object实现

字典

哈希列表/散列表

图