第二周学习

1. 总结

这周学习了哈希表，映射，集合，树，堆，图，重点是哈希表，python实现的话就是字典，和树，主要是二叉树，整体节奏还可以

2. 知识

2.1 哈希表

  • 也叫散列表
  • key-value结构
  • 哈希碰撞

  • python dict

    2.3 集合

  • set

    2.4 树

    image.png

    2.4.1 二叉树

  • 三种遍历

    • 前序
    • 中序
    • 后序

      2.4.2 二叉搜索树

  • 左子树上所有结点的值均小于它的根结点的值；

  • 右子树上所有结点的值均大于它的根结点的值；
  • 查询
  • 插入新结点

  • 删除

    2.5 堆

  • 可以迅速找到最大值或者最小值

    2.5.1 二叉堆

  • 完全二叉树

  • 树中root>= children
  • 查找O（1）
  • 插入，删除 O（logn）

image.png

2.6 图

  • 有环
  • DFS
  • BFS

3. 刷题

二叉树的前序，中序，后序，层序遍历（python非递归写法总结, python 面试必备）

3.1 1. 两数之和

  • 老生常谈的第一题

  • 直接用dict，找下标

    3.2 242. 有效的字母异位词

  • 直接排序

  • 直接循环判断
  • 使用python内库
  • 使用字典

3.3 49. 字母异位词分组

  • 上一题的进阶
  • 使用元组+字典
  • 元组先把异位词解决
  • 注意dict.get()

image.png