算法图解

小灰的算法

Algorithm /ˈælɡərɪðəm/

Case1

const algorithmPractice_one = (()=>{
  /* 
  给出下图所示的n个整数，其中有两个整数时重复的，要求找出这两个重复的整数。
  Give n integers as shown in the figure below, where there are two integers that 
  are repeated, and ask to find these two repeated integers.
  */
  let arr = [3,1,2,5,4,9,7,2]
  //朴素的方法 simple method
  let simpleMethod = (()=>{
    let result = []
    for (let i = 0; i < arr.length; i++) {
      let count = 0
      for (let j = 0;j < arr.length;j++){
        arr[i] === arr[j] ? count++ : null
        count >= 2 ? result.push(arr[j]) : null
      }
    }
    console.log('simple method result：',result);
  })()
  /* 
  优化的方法：散列表，开辟一定的内存空间来存储有用的数据信息。
  Optimized method: hash table,open up a certain memory space to store useful data information.
  遍历整个数列时，每遍历一个整数，就把该整数存储起来，就像放到字典。当遍历下一个整数时，
  When iterating through an array,each integer is stored,just like in a dictionary.
  不必再慢慢向前回溯比较，直接去“字典”中查找，看看有没有对应的整数。
  Instead of siowly backtracking,just look it up in the "dictionary" to see if there is a corresponding integer.
  */
  let optimizedMethod = (()=>{
    let result = 0
    let space:{key:number,count:number}[] = [] 
    for (let i = 0; i < arr.length; i++) {
      let key = arr[i]
      let count = 1
      //添加前判断是否出现过
      for (let j = 0; j < space.length; j++) {
        //在这里直接修改并不执行后面的push
        space[j].key === key ? count++ : null
      }
      if(count >= 2){
        result = arr[i]
        break;
      }
      space.push({
        key,
        count
      })
    }
    console.log('optimized method result:',result);
  })()
})()

Case2

const ArrayOperation = (()=>{
  //中间插入 The middle insert
  let middleInsertFun = (arr,element,index) =>{
    /* 
      把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。
      Move the insertion position and subsequent elements back to make room, and place the
      element to be inserted in the corresponding array position.
      arr 需要插入的数组，element 插入的元素，index 插入的位置
    */
   let size = arr.length
    if(index < 0 || index > size){
      console.log('错误，超出数组实际元素');
      return
    }
    /* 
      从右向左循环，将元素逐个向右挪1位
      Loop from right to left,moving elements one by one to the right.
    */
    for(let i = size-1; i >= index; i-- ){
      arr[i+1] = arr[i]
    }
    /* 
      腾出的位置加入新元素
      Add new elemends to vacated space.
    */
    arr[index] = element
    return arr
  }
  console.log(
    middleInsertFun([1,2,3,4,8],100,3)
  );
  //删除元素 delete elements
  let deleteElementFun = (arr,index) =>{
    let size = arr.length
    if(index < 0 || index > size){
      console.log('错误，超出数组实际元素');
      return
    }
    let deletedElement = arr[index]
    for(let i = index;i < size-1; i++){
      arr[i] = arr[i+1]
    }
    return deletedElement
  }
  console.log(
    deleteElementFun([1,2,3,4,8],3)
  );
})()

链表

线性的数据结构，通过再链表的每个元素中，保存指向下一个元素的引用，来找到下一个元素。

类型

javascript实现单链表

class Node {
    constructor(value, next = null) {
        this.value = value;
        this.next = next; //对后继节点的引用
    }
}
class LinkedList{
    constructor(value){
        this.head = new Node(value)
    }
    findNode(value){
        //查找节点
        let currentNode = this.head
        while (currentNode.value !== value) {
            currentNode = currentNode.next;
        }
        if(!currentNode){
            return null
        }
        return currentNode;
    }
    insertAfter(value,newValue){
        //指定位置插入新节点
        const newNode = new Node(newValue)
        const currentNode = this.findNode(value);
        newNode.next = currentNode.next;
    }
    append(value){
        //在尾部插入节点
        const newNode = new Node(value);
        let currentNode = this.head
        while(currentNode.next){
            //判断如果currentNode.next的指向为空，则是尾部节点
            currentNode = currentNode.next
        }
        //最后把尾部节点指向新节点
        currentNode.next = newNode
    }
    prepend(value){
        //头部插入节点
        const newNode = new Node(value)
        newNode.next = this.head;
        this.head = newNode;
    }
    remove(value){
        //删除节点
        let currentNode = this.head; //要删除的节点
        let previousNode = null;    //要删除的前置节点
        while (currentNode.value !== value){
            previousNode = currentNode;
            currentNode = currentNode.next;
        }
        if(currentNode === this.head){
            this.head = currentNode.next
        }else{
            //前置节点的next指向直接指向要删除的节点的后置节点即可
            previousNode.next = currentNode.next
        }
    }
    removeHead(){
        //删除头部节点
        this.head = this.head.next;
    }
    removeTail(){
        let currentNode = this.head;
        let previousNode = null;
        while (currentNode.next){
            //如果当前的下个指向为null，则是尾部节点
            previousNode = currentNode;
            currentNode = currentNode.next
        }
        previousNode.next = null; //前置节点的next为null即可
    }
    traverse(){
        let currentNode = this.head;
        while (currentNode){
            console.log(currentNode.value);
            currentNode = currentNode.next
        }
    }
}

栈和队列

栈 stack

一种线性数据结构，栈中的元素只能先入后出（First In Last Out）。最早进入的元素存放的位置叫作栈底（bottom）,最后进入的元素存放的位置叫做栈顶（top）

队列 queue

一种线性数据结构，队列的元素只能先入先出（First in First Out）。队列的出口端叫做队头（front）,队列的入口端叫作队尾（rear）

例题

1、如果现在有段字符串，里面有 ‘aaaaabbbbcccdjkasdjcdddasduidaskfjd’ ，怎么把重复字符合并?

  //使用es6的Set数据容器，首先通过字符串方法split将字符串转换为数组，然后通过new Set进行存储，存储后会自动剔除相同字符串
    letstring = 'aaaaabbbbcccdjkasdjcdddasduidaskfjd'
    letstringSet = newSet(string.split(''))
    console.log(stringSet);