又到周末的学习时间了,今天总结几道手写题,亲自手写并且总结其实现思路是对自己的一种负责,有时候觉得看懂了,未必能正确并很快的写出来,只有能写出来才能成为自己的东西,因此,在此按照自己的记忆方式总结出以下算法题。
看完此篇文章的收货:
- 深度优先和广度优先
- 排序
- 二叉树
- 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 ]
插入排序
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
- 重复步骤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
]
选择排序
思路:每一次从待排序的数组元素中选择最大(最小)的一个元素作为首元素,直到排完为止;取出最小值,并保存下来,往后找更新最小值,既要边找最小值位置,又要边替换值
- 有n个数,需要排序n-1次
- 第一次选择最小值,放在第一位
- 第二次选择最小值,放在第二位
- …..重复该过程
- 第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)
我工作中碰到的算法
根据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)。
应用场景:子有重复性的结构 - 深度优先遍历:
- recursion方式
- 输入值是数组:循环第一层之后再对children递归
- 输入值是对象:直接可以对children遍历
- stack方式(pop输出):先进后出,对children从右往左循环遍历
- 输入值是数组:循环第一层,对每个子元素分别新定义stack,stack.push(data[j])
- 输入值是对象:直接定义一个stack,并stack.push(data)
- 广度优先遍历:
- queue方式(shift输出):先进先出,对children从左往右循环遍历
- 输入值是数组:循环第一层,初始queue是输入值queue = data
- 输入值是对象:直接定义一个queue,并queue.unshift(data)
- 二叉树
-
先序遍历(前序遍历):首先访问根,再先序遍历左(右)子树,最后先序遍历右(左)子树
-
中序遍历:首先中序遍历左(右)子树,再访问根,最后中序遍历右(左)子树
-
后序遍历:首先后序遍历左(右)子树,再后序遍历右(左)子树,最后访问根 (遍历所以子文件夹之后,再访问文件。可用于文件系统的文件夹遍历中)
- 冒泡排序: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中的函数