数据结构与算法之美 学习笔记

找回作为大学数据结构课代表的尊严！（羞耻+1

老师建议的学习大纲：

20 个最常用的、最基础数据结构与算法，不管是应付面试还是工作需要，只要集中精力逐一攻克这 20 个知识点就足够了。

• 10 个 数据结构：
  • 数组、链表、栈、队列、散列表
  • 二叉树、堆、跳表、图、Trie 树；
• 10 个算法：
  • 递归、排序、二分查找、搜索、哈希算法、贪心算法
  • 分治算法、回溯算法、动态规划、字符串匹配算法

已完成内容

• 复杂度分析与表达✅
• 链表✅
  • 实现单链表
  • 单链表实现LRU
  • 基于链表判断回文字符串
    • 快慢指针定位中间节点
• 栈✅
  • 浏览器页面栈实现思路
• 队列✅
  • 实现顺序队列：数组队列（入队，出队，搬移，扩容）
  • 实现数组循环队列（思路分析）
  • 阻塞队列（实现思路，应用场景学习）
  • 并发队列（实现思路，应用场景学习）
• 递归✅
  • 学习递归的思路（防止脑壳内堆栈溢出）
  • 使用递归的必须条件（大问题可拆小，小问题仅数据规模不同，有终止条件）
  • 递归的缺点
  • 使用递归的注意事项

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

• 排序 ✅

  • 冒泡
  • 插入
  • 选择排序
  • 归并
  • 快排
  • 桶排序
  • 计数排序
  • 基数排序-底层排序算法要稳定

• 排序优化