左神NB

1. 贪心算法

• 1、最自然智慧的算法
• 2、用一种局部最功利的标准，总是做出在当前看来最好的选择
• 3、难点在于证明局部最功利的标准可以得到全局最优解
• 4、对于贪心算法的学习主要以增加阅历为主

2. 暴力递归

• 暴力递归就是尝试
• 1、把问题转换为规模缩小了的同类问题的子问题
• 2、有明确的不需要继续进行递归的条件（base case)
• 3、有当得到了子问题的结果之后的决策过程
• 4、不记录每一个子问题的解

3. 动态规划

从暴力递归到动态规划

• 1、树立常识：

  • 动态规划是结果，不是原因，动态规划从暴力规划优化而来
  • 学会尝试是解决动态规划最本质的能力

• 2、技巧：

  • 什么暴力递归可以继续优化？

    • 有重复调用同一个子问题的解，这种递归可以优化

  • 如果每一个子问题都是不同的解，无法优化也不用优化

  • 递归优化：分析可变参数的变化范围

  • 暴力递归和动态规划的关系：

    • 某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
      任何动态规划问题，都一定对应着某一个有重复过程的暴力递归
      但不是所有的暴力递归，都一定对应着动态规划

  • 面试题和动态规划的关系

    • 解决一个问题，可能有很多尝试方法
      可能在很多尝试方法中，又有若干个尝试方法有动态规划的方式
      一个问题可能有若干种动态规划的解法

  • 如何找到某个问题的动态规划方式？

    • 1）设计暴力递归：重要原则+4种常见尝试模型！重点！

  • 2）分析有没有重复解：套路解决

  • 3）用记忆化搜索->用严格表结构实现动态规划：套路解决

  • 4）看看能否继续优化：套路解决

  • 面试中设计暴力递归过程的原则：
    1）每一个可变参数的类型，一定不要比int类型更加复杂
    2）原则1)可以违反，让类型突破到一维线性结构，那必须是单一可变参数
    3）如果发现原则1)被违反，但不违反原则2),只需要做到记忆化搜索即可
    4）可变参数的个数，能少则少

  • 知道了面试中设计暴力递归过程的原则，然后呢？

    • 一定要逼自己找到不违反原则情况下的暴力尝试！
      如果你找到的暴力尝试，不符合原则，马上舍弃！找新的！
      如果某个题目突破了设计原则，一定极难极难，面试中出现概率低于5%!

• 3、模型：

  • 常见的4种尝试模型
    1. 从左往右的尝试模型 从左往右进行可能性分析
    2. 范围上的尝试模型 从L 到R的某个范围上进行分析
    3. 多样本位置全对应的尝试模型 对多样本的最后一个位置进行可能性分析
    4. 寻找业务限制的尝试模型 业务范围分析
  • 如何分析有没有重复解：
    列出调用过程，可以只列出前几层
    有没有重复解，一看便知
  • 暴力递归到动态规划的套路：
    1. 你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
    2. 找到哪些参数的变化会影响返回值，对每一个列出变化范围
    3. 参数间的所有的组合数量，意味着表大小
    4. 记忆化搜索的方法就是傻缓存，非常容易得到
    5. 规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
    6. 对于有枚举行为的决策过程，进一步优化**
  • 动态规划的进一步优化
    1. 空间压缩
    2. 状态化简
    3. 四边形不等式
    4. 其他优化技巧

4、算法题

1. 位运算

• 数组元素交换，写法简单
• 异或操作，求出现奇数次数的数，使用了异或运算的性质：0 ^ N = N N^N = 0
• 其他数出现了m次，只有一种数出现了少于m次。用到了去最右侧的1 a & (~a+1) 和异或运算

2. 排序

• 选择排序、冒泡排序、插入排序
• 归并排序
• 快速排序

3. 链表：

• 反转链表
• 删除链表节点
• 返回中点
• 判断单链表是否为回文
• 单链表划分小于区、等于区、大于区
• 两个可能有环链表的相交点

4. 堆

• 堆的插入方法 和 堆化方法

• • 插入：用于大根堆添加元素，向上调整，调整成大根堆的结构
  • 堆化：用于大根堆删除元素，向下调整，调整成大根堆的结构
  • 大根堆的成员变量：
• • • 存储元素的数组： heap
    • 数组的容量，即当前堆的最大容量： limit
    • 堆的元素数量：heapSize
• • 大根堆的成员方法：
• • • 判断是否为空
    • 判断是否为满
    • 添加元素
    • 删除元素

• 加强堆

• • 普通的堆只能方便的获取第一个元素，删除某个值时，需要遍历对比后才能删除
  • 需要加强堆：
• • • 反向索引表
    • 可以根据值删除元素、查找元素
• • 加强堆的结构，是给堆增加一个反向索引表HashMap<T, Interger> indexMap
• • • indexMap，以元素的值为键，以元素在数组中的索引为值

• 堆排序

• • 实现步骤：
• • • 1、把数组从底向上用heapify转换成大根堆
    • 2、遍历：取第一个最大值与堆的末尾交换，此时交换后的末尾位置就排好序了，然后再调整成大根堆的结构。

5. 树

• 二叉树前、中、后序遍历

• • 折纸问题

• 树的性质

• 树形DP套路

• • 判断完全二叉树
  • 判断平衡二叉树
  • 判断二叉搜索树
  • 判断满二叉树

6. 图

• 图结构、图的转换

• • 自己的图结构：
• • • 边：
• • • • Node from
      • Node to
      • int Weight
• • • 点：
• • • • int value
      • int in
      • int out
      • List<Node> nexts 单向的，下一个相邻节点
      • List<Edge> edges 单向的，下一个相邻边
• • • 生成自己的图结构：
• • • • 组装边集
      • 组装点集

• 深度、宽度遍历

• • 深度优先搜索：栈结构遍历
• • • 元素入栈时打印
• • 宽度优先搜索：队列结构遍历
• • • 元素出队时打印

• 拓扑排序

• • 循环遍历入度为0的点

• 最小生成树算法 k p

• • 最小生成树-Prim算法和Kruskal算法
  • k算法：侧重于边
• • • 始终找权重最小的边，然后判断该边的两个点是否已经联通了，已联通就不要这个边，未联通就要这个边。
• • p算法：侧重于点
• • • 以点为主，找点关联的边中权重最小的。

• 最短路径算法

• • 贪心算法
  • 找最短的路径，然后用当前最短的路径去更新未到达的路径中最短的点，直到遍历完所有点。

7. 并查集

• 并查集，合并和查询的集合

• • 查询：查询两个元素是否属于同一集合
  • 合并：将两个不同的集合合并成一个，设置新的集合大小，删除合并掉的集合大小
  • 找父节点：基础方法，设置好路径上所有节点的父节点

8. 滑动窗口

• 想象出来的数据结构，基于双端队列

• 有左右边界，两个边界只能往右走

• 基础使用：

• • 使用linkedlist作为窗口
  • 遍历到数组i位置：
• • • arr[i] 与窗口右边界的值比较，删除不合规则的窗口值
    • i进入窗口
    • 判断左边界是否已过期，过期了就删除
    • 当i >= w-1时，窗口填好值了，可以使用左边界来打印需要的结果

9. 单调栈

• 想象出来的结构，基于栈
• 可以找到比当前位置小的最近的左右两个元素
• 栈中元素，从底网上是由小到大
• 进栈，比栈顶元素大就压栈
• 出栈，比栈顶元素小就弹出栈顶，此时弹出的栈顶元素的左边的小于值是栈顶，右边的小于值是正在判断的元素

10. 动态规划

• 基本解题步骤：暴力递归 => 动态参数组成严格表结构 => 组装dp动态数组【一般是二维的】

• • 1、写出暴力解法
  • 2、找出可变参数，作为dp数组
  • 3、根据暴力解法，填充dp数组

• 常用的套路：

• • 1、从左往右尝试模型
  • 2、范围上的尝试模型
  • 3、多样本位置全对应的尝试模型
  • 4、寻找业务限制的尝试模型

11. 字符串处理

• kmp算法
• 最长子串
• 括号匹配