一、编程语言

1、C

2、.NET

3、Java

4、Python

二、数据结构

1、数组（Arrays）

• 介绍：
  • 数组 CS50 哈佛大学
  • 数组（视频）
  • 加州大学伯克利分校CS61B – 线性和多维数组（视频）（从15分32秒开始）
  • 动态数组（视频）
  • 嵌套数组（视频）
• 实现一个动态数组（可自动调整大小的可变数组）：
  •  练习使用数组和指针去编码，并且指针是通过计算去跳转而不是使用索引
  • 通过分配内存来新建一个原生数据型数组
    • 可以使用 int 类型的数组，但不能使用其语法特性
    • 从大小为16或更大的数（使用2的倍数 —— 16、32、64、128）开始编写
  •  size() —— 数组元素的个数
  •  capacity() —— 可容纳元素的个数
  •  is_empty()
  •  at(index) —— 返回对应索引的元素，且若索引越界则愤然报错
  •  push(item)
  •  insert(index, item) —— 在指定索引中插入元素，并把后面的元素依次后移
  •  prepend(item) —— 可以使用上面的 insert 函数，传参 index 为 0
  •  pop() —— 删除在数组末端的元素，并返回其值
  •  delete(index) —— 删除指定索引的元素，并把后面的元素依次前移
  •  remove(item) —— 删除指定值的元素，并返回其索引（即使有多个元素）
  •  find(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引，若未找到则返回 -1
  • resize(new_capacity) // 私有函数
    • 若数组的大小到达其容积，则变大一倍
    • 获取元素后，若数组大小为其容积的1/4，则缩小一半
• 时间复杂度
  • 在数组末端增加/删除、定位、更新元素，只允许占 O(1) 的时间复杂度（平摊（amortized）去分配内存以获取更多空间）
  • 在数组任何地方插入/移除元素，只允许 O(n) 的时间复杂度
• 空间复杂度
  • 因为在内存中分配的空间邻近，所以有助于提高性能
  • 空间需求 = （大于或等于 n 的数组容积）* 元素的大小。即便空间需求为 2n，其空间复杂度仍然是 O(n)

2、链表（Linked Lists）

• 介绍：
  •  链表 CS50 哈佛大学 – 这样建立了直观感。
  •  单链表（视频）
  •  CS 61B – 链表1（视频）
  •  CS 61B – 链表 2（视频）
  •  [复习] 4分钟了解链表（视频）
•  C代码（视频） – 不是整个视频，只是关于Node结构和内存分配的部分。
• 链表 vs 数组：
  • 核心链表与数组（视频）
  • 在现实世界中，链表与数组的比较（视频）
•  为什么你需要避免使用链表（视频）
• 的确：你需要关于“指向指针的指针”的相关知识：（因为当你传递一个指针到一个函数时， 该函数可能会改变指针所指向的地址）该页只是为了让你了解“指向指针的指针”这一概念。 但我并不推荐这种链式遍历的风格。因为，这种风格的代码，其可读性和可维护性太低。
  • 指向指针的指针
• 实现（我实现了使用尾指针以及没有使用尾指针这两种情况）：
  •  size() —— 返回链表中数据元素的个数
  •  empty() —— 若链表为空则返回一个布尔值 true
  •  value_at(index) —— 返回第 n 个元素的值（从0开始计算）
  •  push_front(value) —— 添加元素到链表的首部
  •  pop_front() —— 删除首部元素并返回其值
  •  push_back(value) —— 添加元素到链表的尾部
  •  pop_back() —— 删除尾部元素并返回其值
  •  front() —— 返回首部元素的值
  •  back() —— 返回尾部元素的值
  •  insert(index, value) —— 插入值到指定的索引，并把当前索引的元素指向到新的元素
  •  erase(index) —— 删除指定索引的节点
  •  value_n_from_end(n) —— 返回倒数第 n 个节点的值
  •  reverse() —— 逆序链表
  •  remove_value(value) —— 删除链表中指定值的第一个元素
• 双向链表
  • 介绍（视频）
  • 并不需要实现

3、堆栈（Stack）

• 堆栈（视频）
•  [Review] Stacks in 3 minutes (video)
•  可以不实现，因为使用数组来实现是微不足道的事

4、队列（Queue）

• 队列（视频）
•  原型队列/先进先出（FIFO）
•  [Review] Queues in 3 minutes (video)
• 使用含有尾部指针的链表来实现:
  • enqueue(value) —— 在尾部添加值
  • dequeue() —— 删除最早添加的元素并返回其值（首部元素）
  • empty()
• 使用固定大小的数组实现：
  • enqueue(value) —— 在可容的情况下添加元素到尾部
  • dequeue() —— 删除最早添加的元素并返回其值
  • empty()
  • full()
• 花销：
  • 在糟糕的实现情况下，使用链表所实现的队列，其入列和出列的时间复杂度将会是 O(n)。 因为，你需要找到下一个元素，以致循环整个队列
  • enqueue：O(1)（平摊（amortized）、链表和数组 [探测（probing）]）
  • dequeue：O(1)（链表和数组）
  • empty：O(1)（链表和数组）

5、哈希表（Hash table）

• 视频：
  •  链式哈希表（视频）
  •  Table Doubling 和 Karp-Rabin（视频）
  •  Open Addressing 和密码型哈希（Cryptographic Hashing）（视频）
  •  PyCon 2010：强大的字典（视频）
  •  PyCon 2017：字典更强大（视频）
  •  (高级) 随机化：通用和完美哈希（视频）
  •  (进阶)完美哈希（Perfect hashing）（视频）
  •  [复习]4分钟了解哈希表（视频）
• 在线课程：
  •  核心哈希表（视频）
  •  数据结构（视频）
  •  电话簿问题（视频）
  • 分布式哈希表：
    • Dropbox中的即时上传和存储优化（视频）
    • 分布式哈希表（视频）
• 使用线性探测法的数组实现
  • hash(k, m) – m是哈希表的大小
  • add(key, value) – 如果键已存在，则更新值
  • exists(key) – 检查键是否存在
  • get(key) – 获取给定键的值
  • remove(key) – 删除给定键的值

6、按位运算（Bitwise operations）

•  Bits 速查表 ── 你需要知道大量2的幂数值（从2^1 到 2^16 及 2^32）
• 好好理解位操作符的含义：&、|、^、~、>>、<<
  •  字码（words）
  •  好的介绍： 位操作（视频）
  •  C 语言编程教程 2-10：按位运算（视频）
  •  位操作
  •  按位运算
  •  Bithacks
  •  位元抚弄者（The Bit Twiddler）
  •  交互式位元抚弄者（The Bit Twiddler Interactive）
  •  位操作技巧（Bit Hacks）（视频）
  •  练习位操作
• 一补数和补码
  • 二进制：利 & 弊（为什么我们要使用补码）（视频）
  • 一补数（1s Complement）
  • 补码（2s Complement）
• 计算置位（Set Bits）
  • 计算一个字节中置位（Set Bits）的四种方式（视频）
  • 计算比特位
  • 如何在一个 32 位的整型中计算置位（Set Bits）的数量
• 交换值：
  • 交换（Swap）
• 绝对值：
  • 绝对整型（Absolute Integer）

7、树（Trees）

• 树-介绍
  •  树的介绍（视频）
  •  树遍历（视频）
  • BFS（广度优先搜索）和DFS（深度优先搜索）（视频）
    • BFS 笔记
      • 层次遍历（BFS，使用队列）
      • 时间复杂度： O(n)
      • 空间复杂度：最佳情况：O(1)，最坏情况：O(n/2)=O(n)
    • DFS 笔记：
      • 时间复杂度：O(n)
      • 空间复杂度：
        • 最好情况：O(log n) – 树的平均高度
        • 最坏情况：O(n)
      • 中序遍历（DFS：左、节点本身、右）
      • 后序遍历（DFS：左、右、节点本身）
      • 先序遍历（DFS：节点本身、左、右）
  •  [复习]4分钟内的广度优先搜索（视频）
  •  [复习] 4分钟内的深度优先搜索（视频）
  •  [复习]11分钟内的树遍历（播放列表）（视频）
• 二叉查找树（Binary search trees）：BSTs
  •  二叉搜索树复习（视频）
  •  介绍（视频）
  •  MIT（视频）
  • C/C++:
    •  二叉查找树 —— 在 C/C++ 中实现（视频）
    •  BST 的实现 —— 在堆栈和堆中的内存分配（视频）
    •  在二叉查找树中找到最小和最大的元素（视频）
    •  寻找二叉树的高度（视频）
    •  二叉树的遍历 —— 广度优先和深度优先策略（视频）
    •  二叉树：层序遍历（视频）
    •  二叉树的遍历：先序、中序、后序（视频）
    •  判断一棵二叉树是否为二叉查找树（视频）
    •  从二叉查找树中删除一个节点（视频）
    •  二叉查找树中序遍历的后继者（视频）
  • 实现：
    •  insert // 将值插入树中
    •  get_node_count // 查找树上的节点数
    •  print_values // 从小到大打印树中节点的值
    •  delete_tree
    •  is_in_tree // 如果值存在于树中则返回 true
    •  get_height // 以节点为单位返回高度（单个节点的高度为1）
    •  get_min // 返回树上的最小值
    •  get_max // 返回树上的最大值
    •  is_binary_search_tree
    •  delete_value
    •  get_successor // 返回给定值的后继者，若没有则返回-1
• 堆（Heap） / 优先级队列（Priority Queue） / 二叉堆（Binary Heap）
  • 以树形结构可视化，但通常在存储上是线性的（数组、链表）
  •  堆（Heap）
  •  堆简介（视频）
  •  二叉树（视频）
  •  树高度备注（视频）
  •  基本操作（视频）
  •  完全二叉树（视频）
  •  伪代码（视频）
  •  堆排序 – 跳转到开始部分（视频）
  •  堆排序（视频）
  •  构建堆（视频）
  •  MIT：堆和堆排序（视频）
  •  CS 61B Lecture 24：优先队列（视频）
  •  线性时间构建堆（大顶堆）
  •  [复习] 13分钟了解堆（视频）
  • 实现一个大顶堆：
    •  insert
    •  sift_up —— 用于插入元素
    •  get_max —— 返回最大值但不移除元素
    •  get_size() —— 返回存储的元素数量
    •  is_empty() —— 若堆为空则返回 true
    •  extract_max —— 返回最大值并移除
    •  sift_down —— 用于获取最大值元素
    •  remove(i) —— 删除指定索引的元素
    •  heapify —— 构建堆，用于堆排序
    •  heap_sort() —— 拿到一个未排序的数组，然后使用大顶堆或者小顶堆进行就地排序

7、排序（Sorting）

• 笔记:
  • 实现各种排序，知道每种排序的最坏、最好和平均的复杂度分别是什么场景:
    • 不要用冒泡排序 – 效率太差 – 时间复杂度 O(n^2), 除非 n <= 16
  • 排序算法的稳定性 (“快排是稳定的么?”)
    • 排序算法的稳定性
    • 排序算法的稳定性
    • 排序算法的稳定性
    • 排序算法 – 稳定性
  • 哪种排序算法可以用链表？哪种用数组？哪种两者都可？
    • 并不推荐对一个链表排序，但归并排序是可行的.
    • 链表的归并排序
• 关于堆排序，请查看前文堆的数据结构部分。堆排序很强大，不过是非稳定排序。
• Sedgewick ── 归并排序（5个视频）
  •  1. 归并排序（Mergesort）
  •  2. 自底向上的归并排序（Bottom up Mergesort）
  •  3. 排序复杂性（Sorting Complexity）
  •  4. 比较器（Comparators）
  •  5. 稳定性（Stability）
• Sedgewick ── 快速排序（4个视频）
  •  1. 快速排序（Quicksort）
  •  2. 选择排序（Selection）
  •  3. 重复键（Duplicate Keys）
  •  4. 系统排序（System Sorts）
• 加州大学伯克利分校：
  •  CS 61B Lecture 29：排序 I（视频）
  •  CS 61B Lecture 30：排序 II（视频）
  •  CS 61B Lecture 32：排序 III（视频）
  •  CS 61B Lecture 33：排序 V（视频）
  •  CS 61B 2014-04-21：基数排序（视频）
•  冒泡排序（视频）
•  冒泡排序分析（视频）
•  插入排序 & 归并排序（视频）
•  插入排序（视频）
•  归并排序（视频）
•  快排（视频）
•  选择排序（视频）
• 归并排序代码：
  •  使用外部数组（C语言）
  •  使用外部数组（Python语言）
  •  对原数组直接排序（C++）
• 快速排序代码：
  •  实现（C语言）
  •  实现（C语言）
  •  实现（Python语言）
• [Review] Sorting (playlist) in 18 minutes
  •  Quick sort in 4 minutes (video)
  •  Heap sort in 4 minutes (video)
  •  Merge sort in 3 minutes (video)
  •  Bubble sort in 2 minutes (video)
  •  Selection sort in 3 minutes (video)
  •  Insertion sort in 2 minutes (video)
• 实现:
  •  归并：平均和最差情况的时间复杂度为 O(n log n)。
  •  快排：平均时间复杂度为 O(n log n)。
  • 选择排序和插入排序的最坏、平均时间复杂度都是 O(n^2)。
  • 关于堆排序，请查看前文堆的数据结构部分。
• 有兴趣的话，还有一些补充，但并不是必须的:
  • Sedgewick──基数排序 (6个视频)
    •  1. Java 中的字符串
    •  2. 键值索引计数（Key Indexed Counting）
    •  3. Least Significant Digit First String Radix Sort
    •  4. Most Significant Digit First String Radix Sort
    •  5. 3中基数快速排序
    •  6. 后继数组（Suffix Arrays）
  •  基数排序
  •  基数排序（视频）
  •  基数排序, 计数排序 (线性时间内)（视频）
  •  随机算法: 矩阵相乘, 快排, Freivalds’ 算法（视频）
  •  线性时间内的排序（视频）
• 总结一下，这是15种排序算法的可视化表示。 如果你需要有关此主题的更多详细信息，请参阅“一些主题的额外内容”中的“排序”部分。

8、图（Graphs）

• MIT（视频）：
  • 广度优先搜索
  • 深度优先搜索
• Skiena 教授的课程 – 很不错的介绍:
  •  CSE373 2012 – 课程 11 – 图的数据结构（视频）
  •  CSE373 2012 – 课程 12 – 广度优先搜索（视频）
  •  CSE373 2012 – 课程 13 – 图的算法（视频）
  •  CSE373 2012 – 课程 14 – 图的算法 (1)（视频）
  •  CSE373 2012 – 课程 15 – 图的算法 (2)（视频）
  •  CSE373 2012 – 课程 16 – 图的算法 (3)（视频）
• 图 (复习和其他):
  •  6.006 单源最短路径问题（视频）
  •  6.006 Dijkstra算法（视频）
  •  6.006 Bellman-Ford算法（视频）
  •  6.006 加速Dijkstra算法（视频）
  •  Aduni：图算法 I – 拓扑排序，最小生成树，Prim算法 – 讲座6（视频）
  •  Aduni：图算法 II – DFS，BFS，Kruskal算法，Union Find数据结构 – 讲座7（视频）
  •  Aduni：图算法 III：最短路径 – 讲座8（视频）
  •  Aduni：图算法 IV：几何算法入门 – 讲座9（视频）
  •  CS 61B 2014：加权图（视频）
  •  贪婪算法：最小生成树（视频）
  •  强连通分量Kosaraju算法图算法（视频）
  •  [复习] 最短路径算法（播放列表）16分钟（视频）
  •  [复习] 最小生成树（播放列表）4分钟（视频）
• 完整的 Coursera 课程:
  •  图的算法（视频）

9、递归（Recursion）

• Stanford 大学关于递归 & 回溯的课程:
  •  课程 8 | 抽象编程（视频）
  •  课程 9 | 抽象编程（视频）
  •  课程 10 | 抽象编程（视频）
  •  课程 11 | 抽象编程（视频）
• 什么时候适合使用
• 尾递归会更好么?
  •  什么是尾递归以及为什么它如此糟糕?
  •  尾递归（视频）
•  解决任何递归问题的5个简单步骤（视频）

10、字典树（Tries）

• 需要注意的是，字典树各式各样。有些有前缀，而有些则没有。有些使用字符串而不使用比特位来追踪路径。
• 阅读代码，但不实现。
• Sedgewick──字典树（3个视频）
  •  1. R Way字典树
  •  2. 三元搜索树
  •  3. 基于字符串的操作
•  数据结构笔记及编程技术
• 短课程视频：
  •  对字典树的介绍（视频）
  •  字典树的性能（视频）
  •  实现一棵字典树（视频）
•  字典树：一个被忽略的数据结构
•  TopCoder —— 使用字典树
•  标准教程（现实中的用例）（视频）
•  MIT，高阶数据结构，字符串（视频中间有点困难）（视频）

11、动态规划（Dynamic Programming）

• 视频:
  •  Skiena：CSE373 2020 – 讲座19 – 动态规划简介（视频）
  •  Skiena：CSE373 2020 – 讲座20 – 编辑距离（视频）
  •  Skiena：CSE373 2020 – 讲座20 – 编辑距离（续）（视频）
  •  Skiena：CSE373 2020 – 讲座21 – 动态规划（视频）
  •  Skiena：CSE373 2020 – 讲座22 – 动态规划和复习（视频）
  •  Simonson：动态规划 0（从59:18开始）（视频）
  •  Simonson：动态规划 I – 第11讲（视频）
  •  Simonson：动态规划 II – 第12讲（视频）
  •  单独的动态规划问题列表（每个都很短）: 动态规划（视频）
• 耶鲁课程笔记:
  •  动态规划
• Coursera 课程:
  •  RNA 二级结构问题（视频）
  •  动态规划算法（视频）
  •  DP 算法描述（视频）
  •  DP 算法的运行时间（视频）
  •  DP vs 递归实现（视频）
  •  全局成对序列排列（视频）
  •  本地成对序列排列（视频）

12、设计模式

• 主要的设计模式:
  • 策略模式（strategy）
  • 单例模式（singleton）
  • 适配器模式（adapter）
  • 原型模式（prototype）
  • 装饰器模式（decorator）
  • 访问者模式（visitor）
  • 工厂模式，抽象工厂模式（factory, abstract factory）
  • 外观模式（facade）
  • 观察者模式（observer）
  • 代理模式（proxy）
  • 委托模式（delegate）
  • 命令模式（command）
  • 状态模式（state）
  • 备忘录模式（memento）
  • 迭代器模式（iterator）
  • 组合模式（composite）
  • 享元模式（flyweight）
• 书籍：《Head First 设计模式》、《大话设计模式》

内容参考来源：https://github.com/jwasham/coding-interview-university/blob/main/translations/README-cn.md