algorithm

注意：所有的文本内容来自于 jwasham/coding-interview-university 我只是将其 fork 下来，方便自己学习。

algorithm 算法

• 二分查找（Binary search）

  • 二分查找（视频）
  • 二分查找（视频）
  • 详情
  • 蓝图
  • 【复习】四分钟二分查找(视频)
  • 实现：
    • 二分查找（在一个已排序好的整型数组中查找）
    • 迭代式二分查找

• 按位运算（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）

排序（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 种排序算法的可视化表示。 如果你需要有关此主题的更多详细信息，请参阅“一些主题的额外内容”中的“排序”部分。

• 递归（Recursion）

  • Stanford 大学关于递归 & 回溯的课程:

    • 课程 8 | 抽象编程（视频）
    • 课程 9 | 抽象编程（视频）
    • 课程 10 | 抽象编程（视频）
    • 课程 11 | 抽象编程（视频）

  • 什么时候适合使用

  • 尾递归会更好么?

    • 什么是尾递归以及为什么它如此糟糕?
    • 尾递归（视频）

  • 解决任何递归问题的 5 个简单步骤（视频）

    回溯蓝图: Java Python

• 动态规划（Dynamic Programming）

  • 在你的面试中或许没有任何动态规划的问题， 但能够知道一个题目可以使用动态规划来解决是很重要的。
  • 这一部分会有点困难，每个可以用动态规划解决的问题都必须先定义出递推关系，要推导出来可能会有点棘手。
  • 我建议先阅读和学习足够多的动态规划的例子，以便对解决 DP 问题的一般模式有个扎实的理解。
  • 视频:
    • 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 递归实现（视频）
    • 全局成对序列排列（视频）
    • 本地成对序列排列（视频）