前端算法

1. 常用算法： dfs-深度优先查找, bfs-广度优先查找
2. 数组查找
3. 链表查找

深度优先查找(dfs)

1. 常见场景：多维数组递归查找， 调用栈

递归

1. 递归定义：调用自身函数
2. 条件：递归条件(继续调用自身的条件)、基线条件(不继续递归的条件)
3. 递归优化用法：尾递归

示例

递归

function recursionFun(i) {
    //基线条件
    if(i>10){
        console.log("结束递归");
        return i;
    }
    //递归条件
    if (i) {
        i++;
        console.log(i)
        recursionFun(i)
    }else{
        console.log('error')
    }
    return i
}

尾递归

function recursionFun(arr, result) {
    //基线条件
    if(!arr.length){
        console.log("结束递归");
        return result;
    }
    //递归条件
    if (arr[0]?.children?.length) {
        result.push([...arr[0].children])
        arr.shift()
        recursionFun(arr, result)
    }else{
        console.log(arr[0])
    }
    return result
}

调用栈

1. 定义： 同栈的概念(压入、弹出)
2. 特点： 栈很高，容易占用大量的内存

迭代

function* logArr(currArr) {
    while (currArr.length) {
      yield console.log({currArr});
      yield currArr.shift()
    }
}
const logObj = logArr(['1','3','7','55'])
logObj.next()

广度优先查找(bfs)

1. 优先在顶点中查找，然后弹出顶点，直到查找到目标

示例

const arr = [
  {
    id: "1",
    na: "no1",
    children: [
      {
        id: "1-1",
        na: "no1-1",
        children: [{ id: "1-1-1", na: "no1-1-1" }],
      },
    ],
  },
  {
    id: "2",
    na: "no2",
    children: [{ id: "2-1", na: "no2-1", children: [] }],
  },
];
function SearchInBreadth(arr){
  const result = [];
  const queue = [];
  if(!queue)return result;
  // 注意：原文中 queue.push(...Arr); 应为 queue.push(...arr);
  queue.push(...arr);
  while (queue.length) {
    //取顶点
    const firstNode = queue.shift();
    /* 查找目标元素的条件 */
    result.push(firstNode);
    /* 查找目标元素的条件 end*/
    //将叶子节点加入队列，注意修正了原文中的 item 为 firstNode
    queue.push(...(firstNode.children ?? []))
  }
  return result;
}
const result = SearchInBreadth(arr);
console.log({ result });