阶段总结： 2020年3月8日

2020年3月8日 下午8:38

总结：
——再次整理:添加——

目前遇到不会的题从哪里去找：

1. 【正向】从具体case找切入点 —》归纳步骤 —》理性整理成代码的样子
2. 【逆向】从常用的数据结构、算法中找切入点 —》用具体的case来验证
3. 【改进】从BF下手，不断改进
4. 【函数式编程】带着一些理想主义的态度去，模块化思考。【反面是正向的琐碎过程化思维】
5. 【逻辑推理】在推理的过程中提示自己使用因为-》所以，也就是说等等提示器来作为【逻辑化的手段】
6. 【数据结构的合理搭配使用】
7. 【过程模拟】要学会分解问题(大问题分解成多个步骤，分块解决，前提任务是啥)，问自己：需要再上步骤中改变什么？
8. 【数学归纳法，巧设变量解方程】
9. 【归纳某一现象条件】在【过程模拟】【正向】尤其常见，提醒自己换换角度，看看还有哪些信息没有用？需不需要自己来统计一些标记条件。
10. 【整理数据和过程的方式】假设是一个个的输入、对数据进行重排列、换个角度去使用数据。这可以是非常好的启发角度。例如dp的打标，我认为也是一种数据整理方式
    • huahua的一步步的Table
    • 数据整理成递归树的形式
    • DP的打表Table
    • 图形（树），不要一直在一个图上画，要化成一个系列，不断地简化，排除干扰。
    • 你现在有100个node，你们怎么组织他们之间的结构？你组织的结构会直接导致他们的子操作(查询、插入、删除)时间复杂度
      • 一串->串也有多种
      • 树->树也有多种
      • 根据node的特征，先进行分为多个小组，在对每个小组进行串/树等的选择设计
      • LFU就是一个好的例子
    • 上面的一定要在纸上用一个例子展现出过程，这样具体化的例子，容易整理思路，也让写代码的时候更加的踏实，因为这样才可以有具体的case
11. 【空间换时间】空间换时间的本质其实就是：【复用，把重复的计算保存下来，下次直接用】，这个思想在递归中就非常常见了。另一种理解是：通过保存数据，使得遍历过程中的当下，可以直接获得更多的信息，以至于可以降低时间复杂度。这也提示我们可以反向思考，看看我们缺什么，然后再循环的之前就统计好。
    1. 能够空间换时间的标志：
       • 【思考：我i能不能偷个懒，利用前人的经验，加快自己的学习速度】
       • 【这道题的max函数，体现出线性递增的趋势】- 这样我们就可能【联系上下文进行推断、计算】
12. 【设计变量语义】动态数组的题，【指针的语义是一个范围】，不是指单个位置。这提醒我们，在编程的时候要【设计变量的语义】，一个好的语义让你思路清晰，不纠结与假特殊case。就像设计数据的处理过程一样，关键在于认为的设计。
13. 【设计数据结构】从UnionFindSet中我感受到【如何设计数据结构】–先想好你的基础语义动作是什么，然后选合适的基础数据结构来表示
    • 这些题的解题套路有两步：
      • 1.建立起元素之间关系
      • 2.在建立起的关系中进行查询
    • 这其中涉及到：【在这个思考的过程中，也要问问自己的数据结构能否方便的完成下面的操作】【当然，也可以作为寻找思路的启发点】
      • 1.关系的初始化
      • 2.关系的建立
      • 3.关系的合并
      • 4.关系的改变
14. 【在循环中动态编程】对于这种动态编程的技巧【明确维护的空间范围是什么？抓住维护空间的边界条件】。eg：滑动窗口
15. hard类型的题也分几个种类:
    1. 【难在题意上】题都读不懂：也就是说你连简单的暴力模拟都不知道怎么一步步的走。887. 鸡蛋掉落
    2. 【难在复杂上】需要你分解成多个子问题来分别解决：
    3. 【难在思路上】在写代码之前，需要你在纸上建模、得出结论、归纳总结：这些题写代码运用总结出的结论反而很简单 面试题 16.03. 交点
    4. 有一个技巧：
       1. 学会从简单的暴力模拟等方式开始思考，作为一个思考的跳板，千万不要死钻，也不要想着复杂度什么的，先做出来再说。
       2. 学会分解问题，拆解成多个子问题来解决，理清楚子问题之间的顺序关系
16. 程序的正确性证明与能够顺利写出模拟的程序是共存的：
    1. 程序的正确性证明中，最重要的一点就是循环不变性是什么？
       1. 这里面最重要的就是定义好循环的单元，并且，每次新的循环中，可以保证循环单元是初始化到循环单元开始的位置的。
       2. 我们在递归中常常提及到子问题，其实循环也是寻需要设计子问题的，需要设计出口条件，只不过常常由于简单而忽略了
       3. 我们很容易犯的一个毛病是：没想到思路，就开始写代码，想着边写代码边设计思路；其实变量的语义、循环单元语义需要再编码之前设计好才可能作对，这些是需要设计的，从二分查找和二叉树的遍历过程，我们就可以认识到他们的重要性。所以，以后要培养：即使是简单问题，也要问问自己设计的语义是什么。你设计的语义，是你整理思路，写成代码，以及最终正确性证明的有效推理手段。有时候再想：写程序都说是一个逻辑性的活，那么我怎么体会不到。你连定义都没有，怎么进行推理！！
    2. 94. 二叉树的中序遍历在这道题中就体现出了设计循环不变性，循环子单元的重要性，直接决定了你能不能写出正确的代码。
17. 找到做数学题的感觉：
    1. 【想数学证明需要什么(定义的变量，设计的逻辑，就要找到这种感觉)】
    2. 具体来说，最常遇到的情况是
       1. 设计定义变量的语义：二分查找，并在迭代中维护定义的区间[left,right]中有我们要找的target
       2. 定义变量的取值区间：eg: [0,~] 等等
          1. 34. 在排序数组中查找元素的第一个和最后一个位置
       3. 设计定义条件： 二叉树的最近公共祖先 我自己的方法
       4. 利用上面定义进行逻辑推理验证
       5. 每次新的循环开始，都是自带定义，说明当前变量满足的性质，这个性质使我们进行逻辑推理的关键。非常常用。
          1. 这个定义一般都是while(condition)中的condition，或者我在上次循环最后所限制的条件
          2. 从这里我们也能明确循环单元的重要性
18. dp思路：
    1. 有几组状态？你做的这件事有几个因变量，也就是有哪些可能，这些【可能】可以分为几类
    2. 状态之间的关系？考虑到达当前状态有几种【可能】，我的目的是找最大的还是最小的
    3. 【dp其实就是在暴力枚举可能状态，他比纯暴力不超时的原因是，将题目中蕴含的上下文关系结合到了暴力的过程中。】
       1. 从纯暴力的枚举所有【case】，编程dp的枚举所有【状态】，注意这里case到状态的改变
    4. eg: 123. 买卖股票的最佳时机 III
       1. 一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过
       2. 所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]
19. 暴力：不要觉得暴力很low，很多题在理解了题意之后，做一些针对性的整理，最后通过暴力来做出最后的结果。
    1. 这是我们这次周赛后感觉出的经验！
20. 搜索：
    1. 这类题其实属于搜索这一大类，其中dp，深度搜索、广度搜索，暴力搜索，搜索的剪枝等等内容的本质就是搜索
    2. 在搜索的题中，关键的区别就是看是否能够找到题目本身的规律进行剪枝、优化、避免重复计算。
    3. 983. 最低票价
21. 看实况，对我有重大启示：
    1. zerotrac的个人空间 - 哔哩哔哩 ( ゜- ゜)つロ 乾杯~ Bilibili
    2. 最大的收获：高手做题，一看题就会想这道题是在考那个知识点，我们就用哪个知识点进行解答。
    3. 对比我原先的方法：做了很多没有必要的思考，反而浪费的时间。
22. 特征不明显的题，需要我们先去发现规律，然后根据规律的特征然后找到合适的算法。对于这样的题先从暴力开始下手是一个不错的建议，然后从暴力中寻找可以优化的规律。
23. 递归的表达能力比迭代要强：
    1. 所有递归都可以改写成循环吗？ - 知乎
    2. 角度1：用循环压栈来避免递归也太搞笑了点吧，手工递归就不是递归了？
    3. 角度2：栈底不可预见的时候，递归是无法有效地化为循环的。
24. 如何将递归写成迭代？或者递归和迭代的的区别？
    1. 148. 排序链表
       1. 准则：
          1. 准则1：一定要先写递归，在写迭代：递归的表达能力比迭代强，对于递归边界不明确的问题无法写成迭代
          2. 准则2：在递归中，我们确定基础动作有哪些，这些动作迭代中一定有
          3. 准则3：动作的执行方法变成交替进行 或者说 类似于dp的感觉：从最小的数据范围进行解决，然后不断的扩大数据的范围 ==》 最终完成所有的数据范围
             1. 抓住dp的感觉就对了：先彻底解决最小问题，然后不断扩大。这其中关键是：在这道题中是连接好子问题和大问题，对应到dp就是状态转移方程
             2. 这里与dp不同的一点是：
                1. dp的状态转移方程 =》 变成了一种链表之间的连接
                2. 状态变量 ==》dp是一层一层的，这里是树的一层一层的
                3. 他没有打表这么明确的因变量，以及打表的顺序方向(这么一说dp是不是特别简单)
    2. 【递归有点倒着写的感觉 ==》 当考察你对递归的理解：可以说(具有相同子问题 + 考虑有限的所有的情况)】
       1. 这里需要我们考虑所有的可能的情况，又和dp思路重合了
    3. 总结：
       1. 写递归更加容易，不容易被不断的迭代过程绕过去，有明显的步骤感，并且递归的能力比迭代强
       2. 当遇到时间、空间复杂度的时候，我们再尝试写成迭代的方式
          1. 在写的时候，我经验是别从递归改代码，而是当做一道新的模拟题去做，过程中可以把递归的基础动作当做是检验、提醒的作用
          2. 因为该的过程中，需要使用两种思维，容易绕住
       3. dp、递归、迭代这些算法思路可以相互的提醒、辅助
    4. 迭代的本质：先彻底解决最小问题，然后不断扩大。
    5. 递归的本质：直接解决大问题
    6. dp：先彻底解决最小问题，然后不断扩大。
    7. dp、递归、迭代 的共同本质就是题目中蕴含子问题这个概念，当出现子问题时，我们可以选择他们其中之一进行解决

现在做的题多了，方法总结的也多了，我得想办法进行精简：

我觉得心里记笨方法比较有用，因为特别的方法，题目中的特征也比较明显，容易想到，【最怕的就是那种完全没有思路的！】

1. 笨方法(无策时找到启发点)：
   • 【正向case】【BF】【过程模拟】==》 拿上case，一步不落的走走！【整理数据和过程的方式】
2. 精益求精的方法(在有思路的基础上)：
   • 【其他的】
3. 最关键的：就是【正确的思考角度 】+ 【归纳现象条件】，对零散的现象屡出个一二三类来的【逻辑思维能力】。不论哪种方法的核心都是这个

态度是最关键的：

1.提醒自己乐观、多角度的的尝试各种方法。脑子转的快一点。
2.不要眼高手低，落实到每一个步中，自然就会有感觉

水平高了之后:

不能满足于功能:

1. 【思路层面】多种思路的时间复杂度
2. 正确性证明
3. 【代码层面】相同的思路,代码层面上如何设计简化