/zuoshen-algorithm

左神算法

Primary LanguageJava

左神算法班笔记

可借鉴的笔记及源码解析链接：https://github.com/renyujie518/StrcuctandAlgorithm/tree/master/StructandAlgorithm/src

视频地址：https://www.bilibili.com/video/BV13g41157hK/

分支内容

  • main - 自我练习实现
  • 左神源码 - 左神算法课程的源码，目测版本不一样，可供参考

待整理：

  1. determinant_reasoning：当一个问题除了前几项是 base case 能直接已知结果外，后续的每一项都按照之前值的严格递推表达式来求出的问题，推理结果为f(n, n-1,... n-m) = f(m,...2,1) * Math.pow(|{x x x} {x x x}{x x x}|, n - m) 典例：斐波那契数列的 O(logN)算法

  2. 假设答案法：假设出最终答案，根据其位置推断出性质，再根据性质设计出简易的代码流程找出答案的位置

  3. 打表法

  4. 构造平凡解，舍弃可能性方法(高级班-1)

  5. 动态规划的斜率优化：当动态规划的状态转移方程中存在枚举行为时，观察临近位置的求值过程是否已经包含了枚举过程的一部分了，存在则可以利用这个位置的值以复用之前位置的枚举结果，减少时间复杂度。

  6. 递归需保证后效性，既母问题的所有决策都体现在子问题的参数上，而不是保留在母问题里

  7. 桶排序普遍针对数据量很大，无法一次加载进内存的数据。将数据分桶，要求每个桶的大小能够被内存加载，进行快排，如果某个区间内数据量仍超出内存，则继续拆分。

  8. 针对无序的字符串序列问题，考虑使用词频表+滑动窗口

  9. 汉诺塔问题n个盘移动次数为：2的n次方减1

TODO:

  • 补充题目注释
  • 总结技巧并添加示例题目链接
  • 修改 main 分支仅保留自己的代码
  • 重学行列式完成 fibonacci 文件夹
  • 补充封装对数器
  • 补充桶排序例题

思维技巧：

  1. 察觉已经计算过的部分并重用，或用缓存以重用
  2. 要用费时间换空间，要么费空间换时间，此消彼长
  3. 利用数学思维：分类讨论，数形结合
  4. 链表常用技巧：快慢指针，
  5. 子字符串串、子数组的问题，就考虑以任意一个位置 i 结尾时的情况；子序列的问题，就每个位置考虑是否选择的问题
  6. 对于有单调性的数组(都为正数或负数)，考虑滑动窗口方式

优化方向：

  1. 自身的数据状况
  2. 所要求解的标准

待强化：

概念整理for leetcode