算法模式

快速和慢速指针方法也被称为 Hare & Tortoise 算法,该算法会使用两个在数组(或序列/链表)中以不同速度移动的指针。该方法在处理循环链表或数组时非常有用。 通...

算法模式

• 递归
  • 定义
    • 种解决问题的方法
    • 通常涉及函数调用自身
  • JavaScript调用栈大小的限制
    • 如果无限递归会造成栈溢出错误
  • 斐波那契数列
  • 优劣势
    • 优势：容易理解，代码量少
    • 劣势：性能慢
    • 性能慢解决：ES6引入尾调用优化
• 动态规划
  • 定义：将复杂问题分解成更小的子问题来解决的优化技术
  • 解决的问题
    • 最少硬币找零问题
      • 给出要找零的钱数，以及可用的硬币面额及其数量找到
        • 所需的最少的硬币个数
    • 背包问题
      • 一个组合优化问题
      • 给定一个固定大小、能够携重W的背包，以及一组有价值和重量的物品，
        • 找出一个最佳解决方案，使得装入背包的物品总重量不超过W，且总值最大
    • 最长公共子序列
      • 找出两个字符串序列的最长子序列的长度
      • 最长子序列是指：在两个字符串序列中以相同顺序出现，但不要求连
        • 续（非字符中子串）的字符串序列
    • 矩阵列相乘
      • 找出一组矩阵相乘的最佳方式(顺序)
    • 图的全源最短路径
      • 对所有顶点对（u,v），找出从顶点u到顶点v的最短路径
      • Floyd-Warshall算法解决此问题
• 贪心算法
  • 定义
    • 遵循一种近似解决问题的技术，期盼通过每个阶段的局部最优选择（当前最好的解），
      • 从而达到全局的最优（全局最优解）
  • 应用
    • 最少硬币找零问题
    • 分数背包问题
• 函数式编程
  • 函数式与命令式编程的区别
    • 函数式编程主要是描述数据以及要对数据应用的转换
    • 程序执行的顺序的重要性很低，在命令式编程中，步骤和顺序非非常重要的
    • 函数和数据集合是函数式编程的核心
    • 在函数式编程中，我们可以使用和溢用函数和递归；
      • 而在命令式编程中，则使用循环、赋值、条件和函数
  • ES6和函数式编程
    • 利用新功能
    • 函数式工具箱
      • map
      • filter
      • reduce