算法二

递归表达式

n! = n*(n-1)! (0!=1)

fn  =  {
      1, n=1,
      2, n=2,
      f(n-1)+f(n-2), n>2
 }

递归经常需要初始条件以及递归表达式。

// 错误写法：
function fibonacci(n) {
  return n == 1 || n == 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
// 对性能的思考：转换成树
// f(5)f(4)执行了1次
// f(3)执行了2次
// f(2)执行了3次
// f(1)执行了2次

// 递归次数：N>=1+2+4+8+...+2^(n-2)=(1- 2^(n-1))/(2^(n-1) -1)
// 2^10=1024
// 2^20= 1048576

从低端构造递归，斐波拉契数列， reduce和for循环两种写法，本质一样。

1.
function fibonacci(n) {
  let [a, b] = [0, 1];
  for (let i = 0; i < n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}
2.
function fibonacci(n) {
  return Array(n)
    .fill()
    .reduce(
      ([a, b], _) => {
        return [b, a + b];
      },
      [0, 1]
    )[1];
}

深度拷贝

function clone(obj) {
  if (obj == null || typeof obj !== "object") return obj;
  const newObj = new obj.constructor();
  for (let key in Object.getOwnPropertyDescriptors(obj)) {
    newObj[key] = clone(obj[key]);
  }
  return newObj;
}

深度比较

function deepCompare(a, b) {
  if (
    a === null ||
    typeof a !== "object" ||
    b === null ||
    typeof b !== "object"
  ) {
    return a === b;
  }
  const propsA = Object.getOwnPropertyDescriptors(a);
  const propsB = Object.getOwnPropertyDescriptors(b);
  if (Object.keys(propsA).length !== Object.keys(propsB).length) {
    return false;
  }
  return Object.keys(propsA).every((key) => deepCompare(a[key], b[key]));
}

树的算法和前端

  • DOM
  • 选择器
  • JSON
  • 虚拟DOM
  • 文本查找和输入提示

树的递归表示

T: v, [T1,...Tk] 数含有值V和一个子树的列表

class Tree {
  constructor(v, children) {
    this.v = v;
    this.children = children || null;
  }
}

const tree = new Tree(10, [
  new Tree(5),
  new Tree(3, [new Tree(7), new Tree(11)]),
  new Tree(2),
]);

树的遍历（先序）

function tree_transverse(tree){
    console.log(tree.v)
    tree.children && tree.children.forEach(tree_transverse)
} // => 10, 5, 3, 7, 11, 2

树的遍历（后序）

function tree_transverse(tree){
    tree.children && tree.children.forEach(tree_transverse)
    console.log(tree.v)
}    // => 5 7 11 3 2 10

树的遍历（中序）

/**
* ord：根节点打印的位置
**/
function tree_transverse_m(tree, ord = 0) {
  let trans = false;
  if (!tree.children) {
    console.log(tree.v);
    return;
  }
  tree.children.forEach((child, i) => {
    if (i === ord) {
      trans = true;
      console.log(tree.v);
    }
    tree_transverse_m(child, ord);
  });
  !trans && console.log(tree.v);
}

tree_transverse_m(tree, 0) //=> 10 5 3 7 11 2
tree_transverse_m(tree, 3) //=> 5  7 11 3 2 10（后序）
tree_transverse_m(tree, 1) //=> 5 10 7 3 11 2

树的查找


function find(tree, prediction) {
  return [...tree_transverse(tree).find(prediction)];
}

function find(tree, prediction) {
  for (let node of tree_transverse(tree)) {
    if (prediction(node)) return node;
  }
}

find(tree, (node) => node.v === 2);

树方法：

/**
 * 映射树状结构数据(类似数组的map方法)
 * @param {object[]} tree - 树状结构的数据
 * @param {function} iteratee - 映射单个节点的方法
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @param {object[]} acc - 当前节点的所有父节点集合
 * @returns {object[]}
 */
export function mapTree(tree, iteratee, { childrenName = 'children' } = {}, acc = []) {
  return tree.map((node) => {
    const children = node[childrenName];
    if (children && children.length) {
      return iteratee.call(null, {
        node,
        acc,
        hasChildren: true,
        children: mapTree(children, iteratee, { childrenName }, acc.concat(node)),
      });
    }
    return iteratee.call(null, {
      node,
      acc,
      hasChildren: false,
    });
  });
}

/**
 * 遍历树状结构数据(类似数组的forEach方法)
 * @param {object[]} tree - 树状结构的数据
 * @param {function} iteratee - 处理单个节点的方法
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @param {object[]} acc - 当前节点的所有父节点集合
 * @returns {object[]}
 * @example
 * forEachTree((arr, ({ node, acc })) => console.log(node, acc))
 */
export function forEachTree(tree, iteratee, { childrenName = 'children' } = {}, acc = []) {
  tree.forEach((node) => {
    iteratee.call(null, { node, acc });
    const children = node[childrenName];
    if (children && children.length) {
      forEachTree(children, iteratee, { childrenName }, acc.concat(node));
    }
  });
}

/**
 * 过滤树状结构数据(类似数组的filter方法)
 * @param {*} tree - 树状结构的数据
 * @param {*} iteratee - 匹配目标节点的方法
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @returns {object[]}
 */
export function filterTree(tree, iteratee, { childrenName = 'children' } = {}) {
  function filter(list, acc) {
    const res = [];
    list.forEach((one) => {
      const children = one[childrenName];
      const _children = children && children.length ? filter(children, acc.concat(one)) : [];

      let tmp;
      if (_children && children && _children.length === children.length) {
        tmp = one;
      } else {
        tmp = {
          ...one,
          [childrenName]: _children,
        };
      }

      if (iteratee.call(null, one, acc) || _children.length) {
        res.push(tmp);
      }
    });
    return res;
  }
  return filter(tree, []);
}

/**
 * 将树状结构数据转化成数组
 * @param {*} tree - 树状结构的数据
 * @param {*} iteratee - 转化单个节点的数据
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @returns {object[]}
 * @example
 * // returns [1,2,3,4,5]
 * treeToList(arr, node => node.id)
 */
export function treeToList(tree, iteratee, { childrenName = 'children' } = {}) {
  const acc = [];
  forEachTree(
    tree,
    ({ node }) => {
      if (isFunction(iteratee)) node = iteratee.call(null, node);
      acc.push(node);
    },
    { childrenName },
  );
  return acc;
}

/**
 * 查找节点(类似数组的find方法)
 * @param {*} tree - 树状结构的数据
 * @param {*} iteratee - 匹配目标节点的方法
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @returns {{ node, acc }}
 * @example
 * // returns { node, acc }
 * findTree(arr, node => node.id == '1')
 */
export function findTree(tree, iteratee, { childrenName = 'children' } = {}) {
  let _node = null;
  let _acc = [];
  try {
    forEachTree(
      tree,
      ({ node, acc }) => {
        if (iteratee.call(null, node, acc)) {
          _node = node;
          _acc = acc.concat(node);
          throw new Error();
        }
      },
      { childrenName },
    );
  } catch (e) {
    // do nothing
  }
  if (!_node) return { node: null, acc: [] };
  return { node: _node, acc: _acc };
}

/**
 * 数组转换成树状结构(已废弃)
 * @param {object[]} list - 数组
 * @param {function} isTopNode - 返回是否为顶层节点
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @param {function} param2.sortRule - 同级元素的排序规则
 * @returns {object[]}
 */
export function listToTree2(
  list,
  isTopNode,
  { childrenName = 'children', sortRule, id = 'id', parentId = 'parentId' } = {},
) {
  if (!isArray(list)) return [];
  // 获取所有id
  const idSet = new Set();
  list.forEach((one) => one[id] && idSet.add(one[id]));

  const _isTopNode = (node) => {
    if (isFunction(isTopNode)) return isTopNode(node);
    return (
      isNullOrUndefined(node[parentId]) ||
      !idSet.has(node[parentId]) ||
      node[parentId] === -1 ||
      node[parentId] === '-1'
    );
  };
  const firstLevelNodes = list.filter(_isTopNode);
  function findChildren(node) {
    const children = list.filter((one) => one[parentId] === node[id]);
    return transform(children);
  }
  function transform(list) {
    const _list = list.map((one) => ({
      ...one,
      children: findChildren(one),
    }));
    if (isFunction(sortRule)) return _list.sort(sortRule);
    return _list;
  }
  return transform(firstLevelNodes);
}

/**
 * 数组转换成树状结构
 * @param {object[]} list - 数组
 * @param {function} isTopNode - 返回是否为顶层节点
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @param {function} param2.sortRule - 同级元素的排序规则
 * @returns {object[]}
 */
export function listToTree(
  list,
  isTopNode,
  { childrenName = 'children', sortRule, id = 'id', parentId = 'parentId' } = {},
) {
  if (!isArray(list)) return [];
  const _isTopNode = (node) => {
    if (isFunction(isTopNode)) return isTopNode(node);
    return node[parentId] === -1 || node[parentId] === '-1' || isNullOrUndefined(node[parentId]);
  };

  const idMapping = list.reduce((acc, current) => {
    acc[current[id]] = current;
    return acc;
  }, {});

  const firstLevelNodes = [];
  list.forEach((one) => {
    if (_isTopNode(one)) {
      firstLevelNodes.push(one);
    }
    const parentEl = idMapping[one[parentId]];
    if (parentEl) {
      parentEl[childrenName] = [...(parentEl[childrenName] || []), one];
    }
  });

  function sort(list) {
    if (!isArray(list)) return [];
    const _list = list.map((one) => ({
      ...one,
      [childrenName]: sort(one[childrenName]),
    }));
    return _list.sort(sortRule);
  }

  if (isFunction(sortRule)) return sort(firstLevelNodes);
  return firstLevelNodes;
}

/**
 * 查找目标节点的上一节点
 * @param {*} tree - 树状结构的数据
 * @param {*} iteratee - 匹配目标节点的方法
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @returns {null|object}
 */
export function findPrevNode(tree, iteratee, { childrenName = 'children' } = {}) {
  if (!isArray(tree)) return null;
  function _findPrevNode(data) {
    let prevNode = null;
    const res = data.some((one) => {
      if (iteratee.call(null, one)) {
        return true;
      }
      const children = one[childrenName];
      if (children && children.length) {
        const [success, _prevNode] = _findPrevNode(children);
        if (success) {
          // 从当前节点的子节点中找到目标节点，则返回目标节点前一个
          // 若目标节点为子节点中的第一个，则返回当前节点
          prevNode = _prevNode || one;
          return true;
        }
        // 如果子节点中未找到目标节点，将子节点中的最后一个节点设置为上一节点
        prevNode = _prevNode;
        return false;
      }
      // 不匹配目标节点，且没有子节点，将当前节点设置为上一节点
      prevNode = one;
      return false;
    });
    return [res, prevNode];
  }
  return _findPrevNode(tree)[1];
}

/**
 * 查找目标节点的下一节点
 * @param {*} tree - 树状结构的数据
 * @param {*} iteratee - 匹配目标节点的方法
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @returns {null|object}
 */
export function findNextNode(tree, iteratee, { childrenName = 'children' } = {}) {
  if (!isArray(tree)) return null;
  function _findNextNode(data) {
    let nextNode = null;
    const res = data.some((one, index) => {
      const children = one[childrenName];
      if (iteratee.call(null, one)) {
        // 匹配到目标节点
        if (children && children.length) {
          // 有子节点，取子节点中的第一个
          nextNode = children[0];
        } else {
          // 无子节点，取下一个同级节点
          nextNode = data[index + 1];
        }
        return true;
      }
      if (children && children.length) {
        const [success, _nextNode] = _findNextNode(children);
        if (success) {
          // 从当前节点的子节点中找到目标节点
          // 如果子节点中的目标节点存在下一节点，则取下一节点
          // 如果子节点中的目标节点为最后一个节点，则取当前节点的下一同级节点
          nextNode = _nextNode || data[index + 1];
          return true;
        }
      }
      return false;
    });
    return [res, nextNode];
  }
  return _findNextNode(tree)[1];
}

/**
 * 查找目标节点的所有兄弟节点（包括自身）
 * @param {*} tree - 树状结构的数据
 * @param {*} iteratee - 匹配目标节点的方法
 * @param {object} param2
 * @param {string} param2.childrenName - 挂载子节点的字段名
 * @returns {object[]}
 */
export function findSiblings(tree, iteratee, { childrenName = 'children' } = {}) {
  if (!isArray(tree)) return [];
  function _findSiblings(data) {
    let res = null;
    data.some((one) => {
      if (iteratee.call(null, one)) {
        res = data;
        return true;
      }
      const children = one[childrenName];
      if (children && children.length) {
        res = _findSiblings(children);
        return Boolean(res);
      }
      return false;
    });
    return res;
  }
  return _findSiblings(tree);
}

/**
 * 查找目标节点的所有父级节点（包括自身）
 * @param {*} tree - 树状结构的数据
 * @param {*} iteratee - 匹配目标节点的方法
 * @returns {object[]}
 */
export function treeFindPath(
  tree,
  id,
  { idName = 'id', parentId = 'parentId', childrenName = 'children' } = {},
) {
  if (tree && id) {
    let parentItems = [];
    let forFn = function (arr, id) {
      for (let i = 0; i < arr.length; i++) {
        let item = arr[i];
        if (item[idName] === id) {
          parentItems.push(item);
          forFn(tree, item[parentId]);
          break;
        } else {
          if (item[childrenName]) {
            forFn(item[childrenName], id);
          }
        }
      }
    };
    forFn(tree, id);
    return parentItems;
  }
  return [];
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,294评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,493评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,790评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,595评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,718评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,906评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,053评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,797评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,250评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,570评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,711评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,388评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,018评论 3赞 316
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,796评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,023评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,461评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,595评论 2赞 350