算法笔记

Posted on | Edited on | In ,

栈和队列

重点

  1. 了解 FIFO 和 LIFO 处理顺序的原理
  2. 实现这两个数据结构
  3. 熟悉内置的队列和栈结构
  4. 解决基本的队列相关问题，尤其是 BFS
  5. 解决基本的栈相关问题
  6. 理解当你使用 DFS 和其他递归算法来解决问题时，系统栈是如何帮助你的。
  • 队列
    • 定义
    • 实现
    • 循环队列 实现
    • BFS 实现 如何避免无限循环 作用：遍历，求最短路径
    • BFS 注意深度需要靠统计每一层的size来辅助计算
  • 栈
    • 实现 用法
    • 最小栈 留意栈的特性 LIFO
    • 单调栈
    • DFS 作用：查找从跟节点到目标节点的路径
    • BFS和DFS的区别：遍历顺序不同
    • 计算DFS空间复杂度时，考虑系统栈
    • 使用递归实现DFS时，递归深度太高将导致栈溢出，优先使用显示栈实现DFS

哈希表

哈希表分为：哈希集合(非重复值) 哈希映射(键值对)

重点

  1. 哈希表的原理是什么？
  2. 如何设计哈希表？
  3. 如何使用哈希集合来解决与重复相关的问题？
  4. 如何使用哈希映射按键聚合信息？
  5. 如何在使用哈希表时设计正确的键？
  • 哈希表原理: 哈希函数将键映射到存储桶
  • 设计哈希表的关键
    • 哈希函数(散列函数)
      • 键值的范围
      • 桶的数量
    • 冲突解决
      • 冲突小 数组
      • 冲突大 高度平衡的二叉树
      • 删除时 从数组中删除i位置的元素 将时间复杂度从O(n)降为O(1)的两种方法: 1.交换 2.链表
  • 复杂度分析
  • 内置哈希表的原理
    • 利用高度平衡的二叉树将数据量大的桶的插入和搜索复杂度从O(n)降到O(logN)

数组和字符串

重点

  1. 了解数组和动态数组之间的区别
  2. 熟悉数组和动态数组中的基本操作
  3. 理解多维数组并能够掌握二维数组的使用
  4. 明白字符串的概念以及字符串所具有的不同特性
  5. 能够运用双指针技巧解决实际问题

待总结

  • 二叉树的前序中序后序遍历