二叉树

哈夫曼
平衡二叉树
树状数组
红黑树
线段树

递归分治笔记

  1. /**
  2.  * https://zhuanlan.zhihu.com/p/37468694
  3.  * @desc  递归
  4.  * 递归和分治很像，和动态规划也像（像即有联系
  5.  * 
  6.  * 递归：
  7.  *     把问题转化为规模缩小了的同类问题的子问题 
  8.  *     有明确的不需要继续进行递归的条件(base case)
  9.  *     有当得到了子问题的结果之后的决策过程 
  10.  *     不记录每一个子问题的解
  11.  * 递归应用：
  12.  *      求一个数的乘方
  13.  *      背包问题
  14.  *      组合：选择一支队伍
  15.  * 消除递归：
  16.  *      递归的使用在方法的调用和返回都会有额外的开销
  17.  *      用递归能实现的，用循环都可以实现\且效率更高，将递归转换为非递归，通常用栈
  18.  * ===> 递归和栈
  19.  * 
  20.  *      尾调用优化？
  21.  * 
  22.  * @desc 分治
  23.  * 分治：
  24.  *      把它分解成几个子问题，
  25.  *      找到求出这几个子问题的解法后，再找到合适的方法，
  26.  *      把它们组合成求整个问题的解法
  27.  *  如：  
  28.  *      递归的二分查找：分为两个对自身的递归调用，分别对应问题的两个部分
  29.  *      将查找范围分成比查找值大的一部分和比查找值小的一部分,
  30.  *      每次递归调用只会有一个部分执行
  31.  * 分治问题：
  32.  *      汉诺塔(当然也可以栈解决)
  33.  *  ===> 分成三步：
  34.  *          从初始塔座A上移动包含n-1个盘子到中介塔座B上、
  35.  *          将初始塔座A上剩余的一个盘子（最大的一个盘子）放到目标塔座C上
  36.  *          将中介塔座B上n-1个盘子移动到目标塔座C上
  37.  *      归并排序
  38.  * 
  39.  * 
  40.  * @desc DP动态规划
  41.  * DP:
  42.  *      从暴力递归中来 
  43.  *      将每一个子问题的解记录下来，避免重复计算 
  44.  *      把暴力递归的过程，抽象成了状态表达 
  45.  *      并且存在化简状态表达，使其更加简洁的可能
  46.  * 
  47.  * 分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案，
  48.  * 而动态规划则是将问题分解成相互依赖的子问题
  49.  * 
  50.  * 
  51.  * 
  52.  * @desc 递归&Dp题反思：
  53.  *     以背包、数组目标元素查找、二维数组最小路径和为例
  54.  * 0、辅助函数
  55.  *      一般需要遍历原数组
  56.  *      辅助函数即是： 前i个数 + 已有的结果 + some辅助条件
  57.  * 1、分析特殊元素，控制可变量
  58.  *      如 二维数组的最短路径之和分为 第一行和第一列的只能走一个方向的特殊判断
  59.  * 
  60.  * 2、找到base-case
  61.  *      确定最终到达点的终点条件
  62.  * 
  63.  * 3、分析题中普通元素的一般规律：
  64.  *      先找状态：
  65.  *          如数组里的目标元素，在数组中的元素对应两个状态：选中与不选中
  66.  *          如背包：这一件物品被选中与不被选中
  67.  *          如二维路径的 向下 / 向右走
  68.  *      确定表达式
  69.  *          选中了怎样？ 加了之后的表达式
  70.  *      依据题意确定最优解
  71.  *          往往是 Math.min(方案1、方案2)
  72.  *          Math.min即是依据题意的选中的策略
  73.  * 
  74.  * 
  75.  * @desc 递归暴栈
  76.  *  递归容易造成爆栈,尾部调用可以解决递归的这个问题，Chrome 的 V8 引擎做了尾部调用优化
  77.  *  递归的爆栈问题可以通过将递归改写成枚举的方式来解决
  78.  * 
  79.  *  优化： 可以傻缓存试试
  80.  */
  83.  /**
  84.  * 1、编号dp
  85.  *      ep:最长递增子序列 [2,1,5,3,6,4,8,9,7] ==-> [1,3,4,8,9]
  86.  *      本类动态规划是基础，一般来说有两种编号的状态：
  87.  *          1、状态i表示前i个元素决策组成的一个状态。
  88.             2、状态i表示用到了第i个状态，和某些在1到i-1之间的元素，
  89.                决策组成了一个状态。
  90.         F[i]：表示前i个元素XXXX
  91.         F[i]:以第i个元素结尾的XXXX
  92.         F[i][j]:前i个元素中恰好有j个XXXX
  94.  * 2、前缀dp
  95.  *      ep:最长公共子序列 str1="1A2B3C",str2="B1D23CA" LCS="123C"
  96.  *      特点是：
  97.  *      f(i)可以由f(i-1)得到，或者
  98.  *      f(i,j)可以由f(i-1,j-1),f(i-1,j),f(i,j-1)得到
  99.  * 
  100.  * 3、划分(区间)dp
  101.  *      f(i,j)={f(i,k)+f(k+1,j)+cost(k)} i<k<j
  102.  * 
  103.  *      例题: 矩阵连乘、石子合并
  104.  * 
  105.  * http://luoshaochuan.com/2017/07/12/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93(%E4%B8%89)/
  106.  * https://blog.csdn.net/trochiluses/article/details/37966729
  107.  * https://blog.csdn.net/zichen_ziqi/article/details/82184495
  108.  */

分治模板

  1. /********
  2.  * 分治： Divide & Conquer
  3.  * 核心思想： 将大问题分解成小问题,然后可能会合并小问题的计算结果绘制成大问题的结果
  4.  * 注意:
  5.  *      子问题与原问题性质完全一样
  6.  *      子问题之间彼此可以独立求解
  7.  *      递归停止的时候 子问题足够的小，可以直接求解出来     
  8.  * 
  9.  * 典型代表：归并排序
  10.  * 与递归的区别： 分治可以递归实现 、也可以迭代实现
  11.  * 但是分治更好的地方是：多线程计算小问题。特别是当小问题之间互不关联的时候
  12.  * 
  13.  * 算法复杂度的分析:递推方程
  14.  * 
  15.  * 分治与减治：
  16.  * 减治法:
  17.  *  大问题分解为小问题，小问题只要递归一个分支，例如：二分查找，幂乘的减治解法
  18.  * 分治:
  19.  *  大问题分解为小问题，小问题都要迭代各个分支，例如：快速排序
  20.  * 
  21.  */
  23. function Divide_Conquer(problem,param1,param2,...arguments){
  24.     // base case
  25.     if(problem==null){
  26.         // 输出结果
  27.         return ;
  28.     }
  30.     // 准备数据、将大问题拆分成小问题 
  31.     let data = prepare_data(problem);
  32.     subproblem = split_problem(problem,data);
  34.     // 处理 subproblem
  35.     subresult1 = Divide_Conquer(subproblem[0],p1,p2);
  36.     subresult2 = Divide_Conquer(subproblem[1],p1,p2);
  37.     subresult3 = Divide_Conquer(subproblem[2],p1,p2);
  38.     // ...
  40.     // 对子结果进行合并、处理 再返回
  41.     result = process_result(subresult1,subresult2,subresult3);
  42. }

递归模板

  1. /*****
  2.  * 递归是一种循环，只是循环的是函数体
  3.  * 复用了函数的逻辑
  4.  * 
  5.  * 可以看做，for循环是横向循环，而递归是竖着的循环
  6.  * 代替for循环终止条件的 就是 递归的 base case
  7.  * 代替for循环的计数的: 递归的当前层 一般是 函数的参数
  8.  * 
  9.  * 递归的思想：复用函数代码、通过函数体进行的循环
  10.  * 
  11.  * 简单的递归：
  12.  * 计算n的阶乘： 一个调用栈
  13.  * 斐波拉契： 一个展开的树
  14.  */
  16. function recursion(level,params1,params2,...arguments){
  17.     // base case
  18.     if(level > MAX_LEVEL){
  19.         //.... 返回结果
  20.         return ;
  21.     }
  23.     // 逻辑 处理data的主要逻辑 
  24.     process_data(level,...arguments);
  26.     // 进入下一层函数 
  27.     recursion(level+1,p1,p2,...arguments);// p1可能是逻辑加工后的params
  29.     // 下一层函数处理完之后返回到此层函数 需要做的事
  30.     somethingtofinished(level)
  31. }

DFS-BFS

剪枝

  1. /****
  2.  * 剪枝:
  3.  * 搜索常用到的策略。
  4.  * 理解: 就是去掉一些不必要的分支判断
  5.  * 
  6.  * 数独：
  7.  * 对于重复的数字怎么有效的进行标记和判重
  8.  * 
  9.  */

回溯

  1. /*****
  2.  * 回溯的基本思想：试图产生所有可能的解决方案，但每次生成解决方案测试如果它满足所有条件，那么只有继续生成后续解决方案。
  3.  * 否则回溯并继续寻找不同路径的解决方案。
  4.  * 
  5.  * 类似于枚举，枚举时所有情况的形成过程是一个逐渐扩大的树
  6.  * 复杂度是呈指数级增长。
  7.  * 回溯基于枚举的优化在于：每次深入到下一层时，会检查当前分支是否满足约束条件，
  8.  * 如果满足，则继续深入。不满足则回溯到他的父节点，继续下一个选择
  9.  * 
  10.  * 
  11.  * 
  12.  * 回溯适用的先决条件：
  13.  *    问题满足 多米诺性质 
  14.  *       P(x1,x2,x3,....,xk+1) ——> P(x1,x2,...,xk) 
  15.  *       k+1维向量满足，那么k维向量肯定也满足
  16.  *    逆否：如果k不满足，那么k+1维肯定也不满足
  17.  * 适用于：求解搜索问题 和 优化问题
  18.  * 
  19.  * 算法设计步骤：
  20.  * 1、向量与每个分量的取值范围
  21.  * 2、在当前层中，确定xk的取值集合 Sk (有可能取值范围会随着深入不断缩小)
  22.  * 3、确定节点儿子的排列规则 
  23.  * 4、判断问题是否满足多米诺性质
  24.  * 5、确定每个分支的约束条件
  25.  * 6、确定搜索策略：深度优先 or 广度优先 等
  26.  * 7、确定存储值：一般存储搜索路径
  27.  * 
  28.  * 经典题：
  29.  * 0、数字的全排列问题
  30.  * 1、N皇后问题
  31.  * 2、0-1背包
  32.  * 3、货郎问题
  33.  */
  35. // 回溯递归模板
  36. /*
  37.     function rebacktrack(n){
  38.         for let k=1 to n
  39.             计算xk，sk // 赋予初值 
  40.         reback(1)
  42.         // 在第k层具体执行
  43.         function reback(k){
  44.             if(k>n) then <x1,x2,x3,....,xk>是解
  45.             // k<n 那么需要对xk进行赋值
  46.             else while(sk != null){// 当前的可供选择尚不为空
  47.                 xk =  sk 的最佳值(与不同的适用策略有关)
  48.                 sk = sk -{xk} // 从sk中剔除用过的xk
  49.                 计算下一层的sk+1 的取值范围是否有变化
  50.                 reback(k+1)
  51.             }
  52.         }
  53.     }
  54. */

动态规划

/**
 * 递归 ——> cache（缓存每次解）——> cache包含的是和形ij有关的结果
 * 那么又可以抽象一个二维格子，每个格子依赖于上一个搭建而成，
 * 最后形成的格子即是最终解
 * 
 * dp 状态转换方程：
 * 动态规划的做法：
 *      1、尝试写出 尝试版本的解答-即暴力递归
 *      2、抛开题意，直接在递归版本上优化，
 *         ===》 改出DP版本。
 * 
 * 基于局部的子最优寻找全局最优，每走一步都是取决于前一步的最优解    
 */

函数式编程

/**
 * 命令式编程：
 *      按部就班地编写程序代码，详细描述要完成的事情以及完成的顺序
 *      【循环、赋值、条件、函数】
 * 函数式编程：
 *      重点关注需要什么，而不是如何描述
 *      函数和数据集合是函数式编程的核心
 *      【函数第一公民、递归】
 * 
 * 函数式工具箱：
 *      map\filter\reduce\
 */