【0014_Week02】第二周总结

[javaxiaomangren]

之前一周刷题的感觉有几个：

1. 越刷越快, 看到新题思路会多一些
2. 有些题浪费了太长时间，信心受挫， 五步刷题的精髓是先熟后精
3. 不会的题千万千万别纠结， 快速过， 重复过， 缩短每次刷题时间， 增加刷题次数
4. 看不太懂的解题方法-使用IDE的调试功能，跑几遍就了然了
5. 多总结规律

为了方便复习我整理了一个脑图： https://www.processon.com/view/link/5df9915ae4b06f5f14615e8a

---

(一) 散列表

• O(1)时间复杂度的 查找key-value的“动态”数据结构，类似的动态数据结构还有 O(logn)的跳表、二叉搜索树、AVL树、红黑树
• 散列表通过散列函数把key 映射到数组中的某个坐标。 由于内存限制，以及鸽巢问题，保存key 的数组是有限的，我们组要在有限的范围内计算key的hash 值，就有可能把不同key 计算到相同的位置即 hash 冲突。

冲突解决的解决方法

• 线性探测、二次探测、双重hash 适合数据量较小、装载因子较小的情况：
• 拉链法 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

hash 函数的设计

• 函数设计要求
  1. 计算的散列值是一个非负数
  2. 如果 key1 = key2，那 hash(key1) == hash(key2)；
  3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。
  4. 散列函数生成的值要尽可能随机并且均匀分布
• 常用的方法 除留取余法\平方取中\折叠法\直接寻址法

动态扩容

• 装载因子 load factor 填入表中的元素个数/散列表的长度 装载因子越大说明填入hash标的元素越多， 冲突概率越大， 此时就会触发 动态扩容, 增加hash表的容量

• 动态扩容会导致数据搬移重新计算hash值和元素的位置，如果一次搬移的数据过多回到导致散列表性能下降。 一个优化方法是动态搬移， 每次插入数据的试从老的散列表取一个数据插入到新的散列表，老的散列表逐步被清空。

  如何设计一个工业级的散列表

• 散列函数的设计、优化动态扩容、调整装载因子大小

• 根据实际情况选择合适的冲突解决方法， 比如用红黑树代替链表

  散列表与双向链表的结合使用

  • 散列表示动态数据结构 插入删除查找效率都很高， 但是顺序访问效率低 所以需要结合链表或者跳表来满足顺序访问
• java.LinkedHashMap
• LRU Cache 双向链表+hash表， 双向链表多存一个hnext 作为解决从冲突用。

• Redis 有序集合

  Hash算法及其应用的

---

(二) 树、二叉树、二叉查找树 一些基本概念前驱、后继节点、父节点、子节点、兄弟节点 节点高度、节点深度 、树的高度 、节点层数

• 二叉树的遍历

  前： 根 -> 左子 -> 右子 中 左子 -> 根 -> 右子 后 左子 -> 右子 -> 根 时间复杂度O(n)，使用递归技巧完成

• 完全二叉树 最后一层靠左排列、其他层满的二叉树 使用数组存储空间是连续的

• 二叉查找树 一个满足下面条件的完全二叉树 当前节点 > 左子树的节点 当前节点 < 右子树的节点

  • 中序遍历 是一个有序数组 二叉查找树在动态插入删除的过程中会失去平衡， 退化为链表， 所以又诞生了平衡二产查找树

(三) 递归

• 递归的思维模式

  1. 拒绝人肉递归
  2. 寻找 最近重复子问题-递归公式
  3. 数学归纳思维 怎么、寻找递归公式关系

• 如何写递归代码 1.终止条件的定义

  2. 处理当前层的逻辑
  3. 去到下一层 - 递归调用
  4. 清里当前层状态-或者返回

class Solution:
    def climbStairs(self, n: int) -> int:
        mem = {}
        return self._climb(n, mem)

    def _climb(self, n: int, mem: dict) -> int:
        # 1. 递归终止条件
        if n <= 2:
            return n
        # 2. 处理当前层逻辑 - 这里可以用类似记忆化
        if mem.get(n):
            return mem.get(n)
        # 3. 去到下一层
        res = self._climb(n - 1, mem) + self._climb(n-2, mem)
        # 4. 清理当前层状态
        mem[n] = res
        return res

[javaxiaomangren]

加油！

[pokongzi]

666