算法二

作者: koala949 | 来源:发表于2020-09-29 16:10 被阅读0次

算法-二分搜索算法
java排序和查找算法
算法
Swift 算法实战二(二叉树、二分搜索)
Swift 算法实战一(集合,字典,链表,栈,队列等算法)
基本KMeans和二分Kmeans的python实现
冒泡算法
二分算法-LeetCode 69
『算法』『数据结构』浅谈二分算法，理解程序员必懂必会的计算机常
数据结构与算法系列——二分查找

递归表达式

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 [];
}

算法-二分搜索算法
算法：二分搜索算法（折半查找算法）时间复杂度：二分搜索算法概述二分搜索算法伪代码二分搜索算法实现二分搜索算...
java排序和查找算法
一、排序算法二、查找算法
算法
一.算法基础--算法的特性二.算法基础--算法的复杂度三.顺序查找和二分查找顺序查找二分查找(前提是有序的...
Swift 算法实战二(二叉树、二分搜索)
Swift 算法实战一(集合,字典,链表,栈,队列等算法) Swift 算法实战二(二叉树、二分搜索) 前言这是...
Swift 算法实战一(集合,字典,链表,栈,队列等算法)
Swift 算法实战一(集合,字典,链表,栈,队列等算法) Swift 算法实战二(二叉树、二分搜索) 前言用 ...
基本KMeans和二分Kmeans的python实现
基本Kmeans算法二分KMeans算法
冒泡算法
一、常用冒泡算法二、优化冒泡算法
二分算法-LeetCode 69
二分算法-LeetCode 69 二分算法二分算法模板, 二分搜索即搜索一个数，如果存在，返回其索引，否则返回-...
『算法』『数据结构』浅谈二分算法，理解程序员必懂必会的计算机常
基本认识二分算法，又名二分查找、折半查找，是一种查找算法，是最基础的，最简单易学且高效实用的算法之一。二分算法的...
数据结构与算法系列——二分查找
二分查找算法的简单介绍今天我们来学习一下二分查找算法，也叫做折半查找算法。使用二分查找算法的前提是数据需要是有序...