学习笔记

• 复习了一下求和题的思路：

  • 方法一：哈希表
  • 方法二：指针法
    • 指针法主要是先将元素进行排列，然后固定左右指针（双指针），R指针用来从L指针后面查找数组中是否含有和L指针指向值和为target的数。

• 新学习的内容（这周由于个人原因课程没有听完，得下周继续听了）：

  • 1.字典树：
    • 可以用于搜索引擎里面的单词补全
    • 字典树不再是像二叉树一样，每个节点存的是单词本身。而是把一个单词拆成单个单个的字母，每个字母存到这个结点里面去。
    • 字典树的优势在于查找的时间复杂度是常数级别
    • 查询效率比哈希表高
    • 基本性质：
      • （1）节点本身不存完整单词
      • （2）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
      • （3）每个结点的所有子节点路径代表的字符都不相同。
    • 即，字典树是通过消耗空间来转换为优化时间。
    • 举例：在查询一个单词的话，比如查询”ten“这个单词，这个单词一共有三个字母，在整个树结构当中，也就是查3次就够了。碰到10多个字母的单词，查十几次就够了。比排序+二分查找快的多。
    • 在单词搜索的实战题当中，是利用了字典树+dfs+剪枝来进行优化和实现的。