手写10+道必须要知道的算法并总结其思路

136 阅读12分钟

又到周末的学习时间了,今天总结几道手写题,亲自手写并且总结其实现思路是对自己的一种负责,有时候觉得看懂了,未必能正确并很快的写出来,只有能写出来才能成为自己的东西,因此,在此按照自己的记忆方式总结出以下算法题。

看完此篇文章的收货:

  • 深度优先和广度优先
  • 排序
  • 二叉树
  • EventBus
  • Promise
  • flat
  • reduce
  • bind
  • new
  • 工作中碰到的算法

深度优先和广度优先

为实例提供的数据:

//数组
const data = [
  {
    name: 'a',
    children: [
      { name: 'b', children: [{ name: 'e' }] },
      { name: 'c', children: [{ name: 'f' }] },
      { name: 'd', children: [{ name: 'g' }] },
    ],
  },
  {
    name: 'a2',
    children: [
      { name: 'b2', children: [{ name: 'e2' }] },
      { name: 'c2', children: [{ name: 'f2' }] },
      { name: 'd2', children: [{ name: 'g2' }] },
    ],
  }
]
// 对象
const data1 =
    {
      name: 'root',
      children: [
        {
          name: 'a',
          children: [
            { name: 'b', children: [{ name: 'e' }] },
            { name: 'c', children: [{ name: 'f' }] },
            { name: 'd', children: [{ name: 'g' }] },
          ],
        },
        {
          name: 'a2',
          children: [
            { name: 'b2', children: [{ name: 'e2' }] },
            { name: 'c2', children: [{ name: 'f2' }] },
            { name: 'd2', children: [{ name: 'g2' }] },
          ],
        }
      ],
    }

深度优先算法DFS(二叉树先序遍历)

recursion方式

data是数组

function getNameForDeepRecursion(data,result) {
  data.forEach((item)=>{
    const map = data => {
      result.push(data.name)
      let children = data.children;
      if(children){
        children.forEach((child)=>{
          map(child,result) //是使用map而不是getNameForDeep,第一次不用遍历
        })
      }
      // data.children && data.children.forEach(child => map(child));
    }
    map(item);
  })
  return result
}

console.log(getNameForDeepRecursion(data,[]))
>  [
  'a',  'b',  'e',  'c',
  'f',  'd',  'g',  'a2',
  'b2', 'e2', 'c2', 'f2',
  'd2', 'g2'
]

data是对象

function getNameForDeepRecursion1(data,result) {
    result.push(data.name)
    let children = data.children;
    if(children){
      children.forEach((child)=>{
        getNameForDeep1(child,result)
      })
    }
    return result
}
console.log(getNameForDeepRecursion1(data1,[]))
> 
 [
  'root', 'a',  'b',
  'e',    'c',  'f',
  'd',    'g',  'a2',
  'b2',   'e2', 'c2',
  'f2',   'd2', 'g2'
]

stack方式

data是数组

function getNameForDeepStack(data) {
  let result = [];
  if (data !== null) {
    // 从左到右,第一个遍历是因为没有children,所以不用stack
    // for(let j=data.length-1;j>=0;j--){
    for(let j=0;j<data.length;j++){ 
      let stack = []
      stack.push(data[j])
      while(stack.length>0){
        let item = stack.pop()
        result.push(item.name)
        let children = item.children;
        if(children){
          // 从右到左
          for(let i=children.length - 1; i>=0; i--){ 
            stack.push(children[i])
          }
        }
      }
    }
  }
  return result
}

console.log(getNameForDeepStack(data))

>  [
  'a',  'b',  'e',  'c',
  'f',  'd',  'g',  'a2',
  'b2', 'e2', 'c2', 'f2',
  'd2', 'g2'
]

data是对象

function getNameForDeepStack1(data) {
  let result = [];
  let stack = [];
  if (data !== null) {
    stack.push(data)
    while(stack.length>0){
      let item = stack.pop()
      result.push(item.name)
      let children = item.children;
      if(children){
        // 因为栈是先进后出,所以子从右往右压栈,输出是从左往右
        for(let i=children.length - 1;i>=0;i--){  
          stack.push(children[i])
        }
      }
    }
  }
  return result
}
console.log(getNameForDeepStack1(data))

> 
 [
  'root', 'a',  'b',
  'e',    'c',  'f',
  'd',    'g',  'a2',
  'b2',   'e2', 'c2',
  'f2',   'd2', 'g2'
]

广度优先算法BFS

data是数组

function getNameForBreath(data) {
  let result = [];
  if (data !== null) { //保证是1位
    let queue = data;
    while (queue.length > 0) {
      [...queue].forEach(item => { 
        // queue.forEach(item => { //应该对queue进行深拷贝,不然执行queue.shift()会影响原数组,所以不能直接用queue  
        queue.shift();
        result.push(item.name);
        // 压入子,父已经在queue中
        let children = item.children
        // if (children) {
        //   for (let i=0 ; i < children.length; i++) {
        //     queue.push(children[i])
        //   }
        // }
        children && (queue.push(...children)); //直接push进一排,所以可以直接用扩展运算符
      })
    }
  }
  return result;
}

>
[
  'a',  'a2', 'b',  'c',
  'd',  'b2', 'c2', 'd2',
  'e',  'f',  'g',  'e2',
  'f2', 'g2'
]

data是对象

function getNameForBreath1(data) {
  let result = [];
  if (data !== null) { //保证是1位
    let queue = [];
    queue.unshift(data);  //其实这步push也可以
    while (queue.length > 0) {
      let item = queue.shift();
      result.push(item.name);
      let children = item.children
      if (children) {
        for (let i = 0; i < children.length; i++) {
          queue.push(children[i])
        }
      }
    }
  }
  return result;
}
console.log(getNameForBreath(data1))

>
 [
  'root', 'a',  'a2',
  'b',    'c',  'd',
  'b2',   'c2', 'd2',
  'e',    'f',  'g',
  'e2',   'f2', 'g2'
]

两者的区别

  • 深度优先不需要记住所有的节点, 所以占用空间小;而广度优先需要先记录所有的节点占用空间大
  • 深度优先有回溯的操作(没有路走了需要回头),所以相对而言时间会长一点;深度优先是一层一层输出,时间短点
  • 深度优先采用的是堆栈的形式, 即先进后出;广度优先则采用的是队列的形式, 即先进先出

二叉树

设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有三种情况:
DLR(称为先根次序遍历),根左右
LDR(称为中根次序遍历),左根右
LRD(称为后根次序遍历),左右根

先序遍历(前序遍历):首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树

中序遍历:首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树

后序遍历:首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根 (遍历所以子文件夹之后,再访问文件。可用于文件系统的文件夹遍历中)

class Node {
  constructor(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  show() {
    return this.data;
  }
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  // 插入:小的插入左边,大的插入右边
  insert(data) {
    let n = new Node(data, null, null);
    if (!this.root) {
      return this.root = n;
    }
    let currentNode = this.root;
    let parent = null;
    while (1) {
      parent = currentNode;
      if (data < currentNode.data) {
        currentNode = currentNode.left;
        if (currentNode === null) {
          parent.left = n;
          break;
        }
      } else {
        currentNode = currentNode.right;
        if (currentNode === null) {
          parent.right = n;
          break;
        }
      }
    }
  }
// 删除叶子节点:把叶子节点置为空
  remove(data) {
    this.root = this.removeNode(this.root, data)
  }

  removeNode(node, data) {
    if (node == null) {
      return null;
    }

    if (data == node.data) {
      // no children node
      if (node.left == null && node.right == null) {
        return null;
      }
      if (node.left == null) {
        return node.right;
      }
      if (node.right == null) {
        return node.left;
      }

      let getSmallest = function (node) {
        if (node.left === null && node.right == null) {
          return node;
        }
        if (node.left != null) {
          return node.left;
        }
        if (node.right !== null) {
          return getSmallest(node.right);
        }

      }
      let temNode = getSmallest(node.right);
      node.data = temNode.data;
      node.right = this.removeNode(temNode.right, temNode.data);
      return node;

    } else if (data < node.data) {
      node.left = this.removeNode(node.left, data);
      return node;
    } else {
      node.right = this.removeNode(node.right, data);
      return node;
    }
  }
  // 查找某一个节点:从根节点触发,根节点比较,再左,比较,再右,比较
  find(data) {
    var current = this.root;
    while (current != null) {
      if (data == current.data) {
        break;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right
      }
    }
    return current.data;
  }
// 查找最大值节点:从根节点触发,看右子树是否有右孩子,继续查找右孩子,如果没右孩子,就是此节点
  findMax() {
    var current = this.root;
    while (current.right != null) {
      current = current.right;
    }
    return current.data;
  }
// 查找最小值节点:从根节点触发,查找左子树是否有左孩子,继续查找左孩子,如果没左孩子,就是此节点
  findMin() {
    var current = this.root;
    while (current.left != null) {
      current = current.left;
    }
    return current.data;
  }
  // 中序遍历:首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树
  inOrder(node) {
    if (!this.inOrderArr) {
      this.inOrderArr = [];
    }
    if (node !== null) {
      this.inOrder(node.left);
      this.inOrderArr.push(node.data);
      this.inOrder(node.right);
    }
  }
   //1,3,4,6,7,8,10,13,14
  // 先序遍历:首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树
  preOrder(node) {
    if (!this.preOrderArr) {
      this.preOrderArr = [];
    }
    if (node !== null) {
      this.preOrderArr.push(node.data);
      this.preOrder(node.left);
      this.preOrder(node.right);
    }
  }
  // 8,3,1,6,4,7,10,14,13
  // 后序遍历:首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根
  postOrder(node) {
    if (!this.postOrderArr) {
      this.postOrderArr = [];
    }
    if (node !== null) {
      this.postOrder(node.left);
      this.postOrder(node.right);
      this.postOrderArr.push(node.data);
    }
  }
  //1,4,7,6,3,13,14,10,8
}

let datas = [8,3,10,1,6,14,4,7,13];
let bst = new BinarySearchTree();
datas.forEach(data => {
    bst.insert(data)
})
 
console.log(bst.findMax()) 
>14
console.log(bst.findMin()) 
>1
console.log(bst.postOrder(bst.root)) 
console.log(bst.postOrderArr)
>
[
   1,  4,  7, 6, 3,
   13, 14, 10, 8
 ]
console.log(bst.preOrder(bst.root)) 
console.log(bst.preOrderArr)
>
[
   8,  3,  1,  6, 4,
   7, 10, 14, 13
 ]

console.log(bst.inOrder(bst.root)) 
console.log(bst.inOrderArr)
>
[
   1,  3,  4,  6, 7,
   8, 10, 13, 14
]

二分法查找法

二分法查找法,也就是折半查找,它是一种在有序数组查找特定元素的搜索算法。

思想:从数组中开始查找,如果该元素是要搜索的目标元素,则循环结束,如果不是继续下一步,如果目标元素大于或者小于中间元素,则在数组大于或者小于中间元素的那一半区域进行查找,进而重复上面操作。如果数组是空的,则找不到该目标元素。

let arr = [1, 2, 3, 5, 8, 9]

function findArr(arr, ele) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2)
    if (ele > arr[mid]) {
      left = mid + 1 //大于中间值,所以左边的往右
    } else if (ele < arr[mid]) {
      right = mid - 1 //小于中间值,所以右边的往左
    } else {
      return mid
    }
  }
  return -1
}

console.log(findArr(arr, 8))
> 4

二分法快速排序

该方案特别消耗内存,不推荐

var arr2 = [1, 2, 3, 5, 8, 9, 4, 7]
function bisectionQuickSort(arr) {
  let len = arr.length
  if (len <= 1) {
    return arr;
  }
  let index = Math.floor(len / 2);
  var pivot = arr[0];
  let left = []
  let right = []
  for (let i = 0; i < len; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else if (arr[i] > pivot) {
      right.push(arr[i])
    }
  }
  return bisectionQuickSort(left).concat(pivot, bisectionQuickSort(right))
}
bisectionQuickSort(arr2)
console.log( arr2)
> 
[1, 2, 3, 4, 5, 7, 8, 9 ]

冒泡排序

var arr2 = [1, 2, 3, 5, 8, 9, 4, 7]
function bubble(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i; j++) {  //记得要减少长度len-i
      if (arr[j] > arr[j + 1]) { // 4,9 位置交换,只是相邻的交换,大的左边的不一定比右边的大
        let temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
        // 试试其他交换方式
      }
    }
    // 获取一个最大值排在最右边
  }
  console.log(arr)
}
bubble(arr2)
> 
[1, 2, 3, 4, 5, 7, 8, 9 ]

上面冒泡排序,数组前半段数字偶然情况下出现未排已排的情况,为避免不必要的重复劳动,排除前半段数据,只针对未排部分执行左右遍历的逐位交换

function betterBubble(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    let isOrdered = true; //前段数字已排序
    for (let j = 0; j < len - i; j++) {  //记得要减少长度len-i
      if (arr[j] > arr[j + 1]) { // 4,9 位置交换,只是相邻的交换,大的左边的不一定比右边的大
        let temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
        isOrdered = false //发生位置交换,即前段数字未排序
      }
    }
    if (isOrdered) {//前段数字已排序
      break;
    }
    // 获取一个最大值排在最右边
  }
  console.log(arr)
}
betterBubble(arr2)
> 
[1, 2, 3, 4, 5, 7, 8, 9 ]

数组中段数字偶然情况下也出现未排已排的情况,为避免不必要的重复劳动,排除中段数据,只针对未排部分执行左右遍历的逐位交换

function betterBubble2(arr) {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    let isOrdered = true; //假设前段数字已排序
    let index = 0; //后端数字下标初始化
    for (let j = 0; j < len - i; j++) {  //记得要减少长度len-i
      if (arr[j] > arr[j + 1]) { // 4,9 位置交换,只是相邻的交换,大的左边的不一定比右边的大
        let temp = arr[j + 1]
        arr[j + 1] = arr[j]
        arr[j] = temp
        isOrdered = false //发生位置交换,即前段数字未排序
        index = j + 1 //后面已经排过序的就不再参与排序
      }
    }
    if (isOrdered) {//过滤掉前段数字已排序
      break;
    }
    end = index; //更新长度
    // 获取一个最大值排在最右边
  }
  console.log(arr)
}
betterBubble2(arr2)
> 
[1, 2, 3, 4, 5, 7, 8, 9 ]

插入排序

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 重复步骤2~5
function insertSort(arr) {
  let len = arr.length
  for (let i = 0; i < len; i++) { //思路:不断往后遍历新元素
    let preIndex = i - 1; //已经排序的元素 (左边)
    let cur = arr[i] //比较新元素
    while (preIndex >= 0 && arr[preIndex] > cur) {
      arr[preIndex + 1] = arr[preIndex] //交换顺序, arr[preIndex]往后移动一位
      preIndex--;  //跟左边的比较,并且是从右往左扫描
    }
    arr[preIndex + 1] = cur //获取到最终的preIndex,把要插入的值放入它之后
  }
  return arr
}
var insertArr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
console.log('insertSort:', insertSort(insertArr))
>
[
  -2, -1, 0, 1, 2,
   3,  4, 6, 7, 7,
   9
]

选择排序

思路:每一次从待排序的数组元素中选择最大(最小)的一个元素作为首元素,直到排完为止;取出最小值,并保存下来,往后找更新最小值,既要边找最小值位置,又要边替换值

  1. 有n个数,需要排序n-1次
  2. 第一次选择最小值,放在第一位
  3. 第二次选择最小值,放在第二位
  4. …..重复该过程
  5. 第n-1次选择最小值,放在第n-1位

选择排序和插入排序要比冒泡排序快,插入排序是这三种算法中最快的。

function selectSort(arr) {
  let len = arr.length;
  let tempIndex = 0
  for (let i = 0; i < len; i++) {
    tempIndex = i //最小值
    // 往右边遍历
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[tempIndex])  //右边的比左边的小,交换最小值位置
        tempIndex = j;
    }
    // 每一趟保证第i位为最小值
    if (tempIndex !== i) {
      [arr[i], arr[tempIndex]] = [arr[tempIndex], arr[i]] //
    }
  }
}

自定义EventBus

class Bus {
  constructor() {
    // callbackMap是对象,键名是eventName,键值是事件数组
    this.callbackMap = {} 
  }
  $on(eventName, callback) {
    // 1.判断callbackMap是否保存过相同的事件
    if (!this.callbackMap[eventName]) {
      this.callbackMap[eventName] = []// 没有,就设置一个保存的容器
    }
    this.callbackMap[eventName].push(callback)
  }
  $emit(eventName, ...rest) {
    // 1.按照名字取出所有的回调
    const callbackArr = this.callbackMap[eventName]
    if (!callbackArr) {
      return// 没有监听的回调
    }
    // 2.一个一个调用回调,并且传参
    callbackArr.map(callbackItem => {
      callbackItem(...rest) // 根据参数执行函数
    })
  }
  $off(eventName, callback) {
    if(!this.callbackMap[eventName]){
      return 
    }
    if (!eventName) {
      this.callbackMap[eventName] = []
    }
    if (callback) callback() 
  }
}
let bus = new Bus();
// 先调用on为了push函数,再调用emit
bus.$on('test',(data)=>{
  console.log('bus:',data)
  // bus: I am a fe-engineer
})
bus.$emit('test','I am a fe-engineer')
bus.$off('test')

LazyMan

class LazyMan {
  constructor() {
    this.tasks = [];
    this.timer = null;
    this.t = '';
    this.t1 = ''
  }
  run() {
    if (this.timer) {
      clearTimeout(this.timer)
    }
    // 如果每个函数返回this,而不表示run(),则需要有个最终函数执行,所以放在setTimeout中
    // setTimeout执行顺序是最后,所以是所有函数的数组
    console.log(1)
    this.timer = setTimeout(async () => {
      for (let tast of this.tasks) { //this.tasks数组根据压入的东西执行
        await tast()
      }
      console.log(2)
      this.tasks.length = 0;
      this.timer = null;
    })
    return this

  }

  // 往后压任务
  sleep(second) {
    this.tasks.push(async () => {
      console.log(`Sleep ${second} s`)
      return await new Promise(resolve => {
        setTimeout(resolve, second * 1e3);
      })
    });
    return this.run();
  }
  // 往前压任务
  sleepFirst(second) {
    this.tasks.unshift(async () => {
      console.log(`Sleep first ${second} s`)
      return await new Promise(resolve => {
        setTimeout(resolve, second * 1e3);
      })
    });
    return this.run();
  }
  async _timeout(second) {
    await new Promise(resolve => {
      setTimeout(resolve, second * 1e3);
    })
  }
  eat(food) {
    this.tasks.push(async () => console.log(`Eat ${food}`));
    return this.run();
  }
  sayHi(name) {
    this.tasks.push(async () => console.log(`Hi, this is ${name}`));
    return this.run();
  }
}
let lazyman = new LazyMan()
lazyman.eat('eat').sayHi('say hi').sleep(1).sleepFirst(1)

>
1
1
1
1
Sleep first 1 s
Eat eat
Hi, this is say hi
Sleep 1 s
2

myFlat

var arr1 = [1, 2, 3, 5, 8, 9, [1, 2, [1, 2], 3]]
//res写在全局中
let res = []
function myFlat(arr){
  for(let i=0,len=arr.length; i<len; i++){
    if(Array.isArray(arr[i])){
       myFlat(arr[i])
    } else {
      res.push(arr[i])
    }
  }
}
myFlat(arr)
console.log(res)

//res写在参数中
function myFlat(arr, res) {
  for (let i = 0, len = arr.length; i < len; i++) {
    if (Array.isArray(arr[i])) {
     // res = myFlat(arr[i], res) 也可以
      myFlat(arr[i], res)
    } else {
      res.push(arr[i])
    }
  }
  return res
}
console.log(myFlat(arr1, []))
>
[
  1, 2, 3, 5, 8,
  9, 1, 2, 1, 2,
  3
]

reduce

Array.prototype.myReduce =  function(callback,initVal){
  if (this == undefined) {
    throw new TypeError('this is null or not defined');
  }
  if (typeof callback !== 'function') {
    throw new TypeError(callbackfn + ' is not a function');
  }
  const self = this;
  let accumulation = initVal ? initVal : self[0];
  const startIndex = initVal ? 0 : 1 
	// 注意startIndex和accumulation
  for(let i=startIndex; i<self.length; i++){
    accumulation = callback.call(null, accumulation, self[i], i, self)
  }
  return accumulation
}

let arr = [1,2,4,6]

let result = arr.myReduce((acc, val, index)=>{
  acc+= val
  return acc
})
console.log(result) //13

bind

Function.prototype.myBind = function (context, ...args) {
  let _self = this //this表示的就是被调用的函数
  if (typeof this !== 'function') {
    return
  }
  let arg1 = [].slice.call(arguments, 1);//第二个参数截取,获取被调用函数的参数
  let fBound = function () {
    let arg2 = [].slice.call(arguments);//因为bind返回一个函数,所以后面可能还会带有参数
    // 如果当前函数的this指向的是构造函数中的this 则判定为new 操作,也就是this是实例对象
    let realObj = this instanceof _self ? this : obj  //绑定的调用函数也能被new操作法创建对象,此时this会被忽略
    return _self.apply(realObj, [...args, ...arg2])
  }
  // 定义一空函数,作为中间桥梁
  let emptyFun = function () { } //创建空函数作为中间人,承接原函数的原型丢给绑定函数
  //维护原型关系
  if (this.prototype) {
    emptyFun.prototype = this.prototype; //this是原函数,也就是foo
  }
  fBound.prototype = new emptyFun() //fBound继承emptyFun的原型链
  return fBound
}

function foo(name) {
  this.name = name;
}
var obj = {};  //空对象,指向window
var bar = foo.myBind(obj);
bar('hannie');
console.log(obj.name);  // hannie    obj拥有了name属性

var g = new bar('gh');
console.log(obj.name);  // hannie     //realObj是obj(上下文)
console.log(g.name); //gh 

new

function myNew() {
  // 1. 获取构造函数,并且删除 arguments 中的第一项
  let ConF = [].shift.call(arguments);
  if (typeof ConF !== 'function') {
    throw new TypeError('Type Error');
  }
  // 2. 创建一个空的对象并链接到构造函数的原型,使它能访问原型中的属性
  let obj = Object.create(ConF.prototype);
  // 3. 使用apply改变构造函数中this的指向实现继承,使obj能访问到构造函数中的属性
  let ref = ConF.apply(obj, arguments);
  // 4. 优先返回构造函数返回的对象
  return ref instanceof Object ? ref : obj
}
function Person(name) {
  this.name = name;
}

let p = myNew(Person, 'hannie')
console.log(p) //Person { name: 'hannie' }

Promise(all | race | any | catch | then | resolve | reject)

看这篇:手写Promise源码深入了解其原理

我工作中碰到的算法

根据parentId对回复数组重排

let list = [  {    commentRelaId: "1",    commentId: "1",    replayList: [      {        commentRelaId: "12",        parentId: "11",        comment: '回复12'      },      {        commentRelaId: "14",        parentId: "13",        comment: '回复14'      },      {        commentRelaId: "11",        parentId: "1",        comment: '回复11'      },      {        commentRelaId: "13",        parentId: "12",        comment: '回复13'      }    ],
  },
  {
    commentRelaId: "2",
    commentId: "2",
    replayList: [
      {
        commentRelaId: "22",
        parentId: "21",
        comment: '回复22'
      },
      {
        commentRelaId: "24",
        parentId: "23",
        comment: '回复24'
      },
      {
        commentRelaId: "21",
        parentId: "2",
        comment: '回复21'
      },
      {
        commentRelaId: "23",
        parentId: "22",
        comment: '回复23'
      }
    ],
  }
]
function handleReplyOrder(list) {
  for (let i = 0, len = list.length; i < len; i++) {
    let replayL = list[i].replayList
    let newArr = []
    let temp = {}
    let index = -1
    for (let j = 0, len = replayL.length; j < len; j++) {
      if (replayL[j].parentId === list[i].commentRelaId) {
        newArr.push(replayL[j])
        temp = replayL[j]
        index = j
        break;
      }
    }
    replayL.splice(index, 1);
    function traverse(arr) {
      if (arr.length > 1) {
        for (let j = 0, len = arr.length; j < len; j++) {
          if (arr[j].parentId === temp.commentRelaId) {
            newArr.push(arr[j])
            temp = arr[j]
            index = j
            break;
          }
        }
        arr.splice(index, 1);
        traverse(arr)
      } else {
        newArr.push(arr[0])
      }
    }
    replayL.length > 0 && traverse(replayL)
    list[i].replayList = newArr
  }
  return list
}
console.log(handleReplyOrder(list))
>
[  {    commentRelaId: '1',    commentId: '1',    replayList: [{      commentRelaId: "11",      parentId: "1",      comment: '回复11'    }, {      commentRelaId: "12",      parentId: "11",      comment: '回复12'    }, {      commentRelaId: "13",      parentId: "12",      comment: '回复13'    },    {      commentRelaId: "14",      parentId: "13",      comment: '回复14'    }    ]
  },
  {
    commentRelaId: '2',
    commentId: '2',
    replayList: [{
      commentRelaId: "21",
      parentId: "2",
      comment: '回复21'
    }, {
      commentRelaId: "22",
      parentId: "21",
      comment: '回复22'
    }, {
      commentRelaId: "23",
      parentId: "22",
      comment: '回复23'
    },
    {
      commentRelaId: "24",
      parentId: "23",
      comment: '回复24'
    }
    ]
  }
]

总结

  • 递归:最终结果值result,可以写在全局(不需要return),可以写在参数中(需要return)。
    应用场景:子有重复性的结构
  • 深度优先遍历:
  1. recursion方式
    • 输入值是数组:循环第一层之后再对children递归
    • 输入值是对象:直接可以对children遍历
  2. stack方式(pop输出):先进后出,对children从右往左循环遍历
    • 输入值是数组:循环第一层,对每个子元素分别新定义stack,stack.push(data[j])
    • 输入值是对象:直接定义一个stack,并stack.push(data)
  • 广度优先遍历:
  1. queue方式(shift输出):先进先出,对children从左往右循环遍历
    • 输入值是数组:循环第一层,初始queue是输入值queue = data
    • 输入值是对象:直接定义一个queue,并queue.unshift(data)
  • 二叉树
  1. 先序遍历(前序遍历):首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树

  2. 中序遍历:首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树

  3. 后序遍历:首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根 (遍历所以子文件夹之后,再访问文件。可用于文件系统的文件夹遍历中)

  • 冒泡排序:2层循环(1层数据遍历+1层交换位置),右边已经排好序的不再拍,所以要再第二层循环中跟新length
  • 插入排序:2层循环(1层数据遍历+1层找到最小值),循环更新得到最小值的位置,把要插入的值放入它之后
  • 选择排序:2层循环(1层数据遍历+1层获取最小值指引),更新最小值index
  • 快速排序:初始化一参考值,分成两边,递归两边,组合起来
  • 二分法查找法:初始化left=0和right = arr.length - 1,根据目标值更新left和right,从而更新mid(let mid = Math.floor((left + right) / 2))
  • EventBus:on中push函数,emit调用函数,off删除函数,记住是emit触发on中的函数