数据存储方式概述

1. 数组与链表

  • 数组的存储方式主要为数组和链表。
  • 散列表通过散列函数将键映射到一个大数组中，但需要考虑解决散列冲突。

2. 树结构

  • 用数组实现的树就是堆，因为堆是一个完全二叉树，用数组存储不需要节点指针。
  • 用链表表示，会衍生出巧妙的设计，比如二叉搜索树、AVL树、红黑树。

3. 数组的优缺点

  • 优点: 可以随机访问，通过索引快速找到对应元素。
  • 缺点: 链表不支持随机访问，需要通过顺序访问，通过前驱或者后继依次访问表内元素。

4. 链表的优缺点

  • 优点: 不需要考虑扩容，方便插入和删除元素。如果知道某一个元素的前驱和后驱，插入和删除的时间复杂度就是 O(1)。
  • 缺点: 随机访问效率低。

动态规划

1. 动态规划的定义

  • 动态规划问题的一般形式是求最值，求解动态规划的核心是穷举。
  • 关键要素包括重叠子问题、最优子结构、状态转移方程。

2. 方法论

  • 明确 base case。
  • 明确状态，明确选择，定义数组或者函数的含义。

3. 斐波那契数列

  • 暴力递归: 代码低效，主要原因在于出现大量的重复计算。
1
2
3
4
int fib(int N) {
    if (N == 0 || N == 1) return N;
    return fib(N - 1) + fib(N - 2);
}

4. 优化算法

  • 带备忘录的递归算法，最终的时间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fib(int N) {
    if (N < 0) return 0; // 备忘录全初始化为
    vector<int> memo(N + 1, -1); // 进行带备忘录的递归
    return helper(memo, N);
}

int helper(vector<int>& memo, int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过
    if (memo[n] != -1) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}