1

常见数据结构和算法

数据结构的存储方式

数据结构的底层存储方式只有两种：数组（顺序存储）和链表（链式存储）

1. 队列、栈 这两种数据结构既可以使用链表也可以使用数组实现。用数组实现，
   就要处理扩容缩容的问题；用链表实现，没有这个问题，但需要更多的内存空间
   存储节点指针
2. 图 两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。邻接矩阵判断连
   通性迅速，并可以进行矩阵运算解决一些问题，但是如果图比较稀疏的话很耗费空
   间。邻接表比较节省空间，但是很多操作的效率上肯定比不过邻接矩阵
3. 散列表 通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法
   ，拉链法需要链表特性，操作简单，但需要额外的空间存储指针；线性探查法就需
   要数组特性，以便连续寻址，不需要指针的存储空间，但操作稍微复杂些
4. 树 用数组实现就是堆，因为堆是一个完全二叉树，用数组存储不需要节点指针
   ，操作也比较简单；用链表实现就是很常见的那种树，因为不一定是完全二叉树，
   所以不适合用数组存储。为此在这种链表树结构之上，又衍生出各种巧妙的设计，
   比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等

数据结构的基本操作

各种数据结构的遍历+访问有两种形式：线性的和非线性的。线性就是 for/while
迭代为代表，非线性就是递归为代表。线性表应满足的条件是：除了头尾两个节点
以外，每个节点有且只有一个前节点和一个后节点

1. 数组遍历，线性迭代结构

   void traverse(int[] arr) {
       for (int i = 0; i < arr.length; i++) {
           // 迭代访问 arr[i]
       }
   }

2. 链表遍历，兼具迭代和递归结构

   /* 基本的单链表节点 */
   class ListNode {
       int val;
       ListNode next;
   }
   
   void traverse(ListNode head) {
       for (ListNode p = head; p != null; p = p.next) {
           // 迭代访问 p.val
       }
   }
   
   void traverse(ListNode head) {
       // 递归访问 head.val
       traverse(head.next);
   }

3. 二叉树遍历，典型的非线性递归遍历

   /* 基本的二叉树节点 */
   class TreeNode {
       int val;
       TreeNode left, right;
   }
   
   void traverse(TreeNode root) {
       traverse(root.left);
       traverse(root.right);
   }

   二叉树框架可以扩展为 N 叉树的遍历

   /* 基本的 N 叉树节点 */
   class TreeNode {
       int val;
       TreeNode[] children;
   }
   
   void traverse(TreeNode root) {
       for (TreeNode child : root.children)
           traverse(child);
   }

动态规划详解

动态规划问题的一般形式就是求最值，比如说让你求最长递增子序列最小编辑
距离等。动态规划问题一定会具备最优子结构，才能通过子问题的最值得到原
问题的最值。虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万
化，穷举所有可行解其实并不是一件容易的事，只有列出正确的状态转移方
程，才能正确地穷举。重叠子问题、最优子结构、状态转移方程就是动态规划
三要素

#明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

斐波那契数列

1. 暴力递归 斐波那契数列的数学形式就是递归的，存在大量重复计算

   int fib(int N) {
       if (N == 1 || N == 2) return 1;
       return fib(N - 1) + fib(N - 2);
   }

2. 即然耗时的原因是重复计算，那么我们可以造一个备忘录，每次算出某个子
   问题的答案后别急着返回，先记到备忘录里再返回。这就是动态规划问题的第一
   个性质：重叠子问题

   int fib(int N) {
       if (N < 1) return 0;
       // 备忘录全初始化为 0
       vector<int> memo(N + 1, 0);
       // 进行带备忘录的递归
       return helper(memo, N);
   }
   int helper(vector<int>& memo, int n) {
       // base case
       if (n == 1 || n == 2) return 1;
       // 已经计算过
       if (memo[n] != 0) return memo[n];
       memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
       return memo[n];
   }

3. dp数组的迭代解法 带备忘录的递归解法的效率已经和迭代的动态规划解法
   一样了。实际上这种解法和迭代的动态规划已经差不多了，只不过这种方法叫
   做自顶向下，动态规划叫做自底向上，把这个备忘录独立出来成为一张表

   int fib(int N) {
       if (N < 1) return 0;
       if (N == 1 || N == 2) return 1;
       vector<int> dp(N + 1, 0);
       // base case
       dp[1] = dp[2] = 1;
       for (int i = 3; i <= N; i++)
           dp[i] = dp[i - 1] + dp[i - 2];
       return dp[N];
   }

4. 状态压缩 根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态
   有关，其实并不需要那么长的一个DP table 来存储所有的状态，只要想办法存
   储之前的两个状态就行了

   int fib(int n) {
       if (n < 1) return 0;
       if (n == 2 || n == 1) 
           return 1;
       int prev = 1, curr = 1;
       for (int i = 3; i <= n; i++) {
           int sum = prev + curr;
           prev = curr;
           curr = sum;
       }
       return curr;
   }

凑零钱问题

这个问题是动态规划问题，因为它具有最优子结构的。要符合最优子结构，子问
题间必须互相独立。回到凑零钱问题，为什么说它符合最优子结构呢？比如你想
求 amount = 11 时的最少硬币数（原问题），如果你知道凑出 amount = 10
的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为1的
硬币）就是原问题的答案

# 伪码框架
def coinChange(coins: List[int], amount: int):

    # 定义：要凑出金额 n，至少要 dp(n) 个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # 题目要求的最终结果是 dp(amount)
    return dp(amount)

根据伪码，我们加上 base case 即可得到最终的答案。显然目标金额为
0 时，所需硬币数量为0；当目标金额小于0 时，无解返回-1

def coinChange(coins: List[int], amount: int):
	# 备忘录
    memo = dict()
    def dp(n):
     	# 查备忘录，避免重复计算
        if n in memo: return memo[n]
        # base case
        if n == 0: return 0
        if n < 0: return -1
        # 求最小值，所以初始化为正无穷
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # 子问题无解，跳过
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)

        return res if res != float('INF') else -1
    
    return dp(amount)

也可以自底向上使用 dp table 来消除重叠子问题

int coinChange(vector<int>& coins, int amount) {
    // 数组大小为 amount + 1，初始值也为 amount + 1
    vector<int> dp(amount + 1, amount + 1);
    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.size(); i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

回溯算法详解

回溯算法其实就是我们常说的DFS 算法，本质上就是一种暴力穷举算法。解决一
个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1. 路径：也就是已经做出的选择
2. 选择列表：也就是你当前可以做的选择
3. 结束条件：也就是到达决策树底层，无法再做选择的条件

其核心就是for 循环里面的递归，在递归调用之前做选择，在递归调用之后撤销
选择

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

全排列问题

比如找[1,2,3]的全排列，[2] 就是「路径」，记录你已经做过的选择；[1,3] 就
是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，
在这里就是选择列表为空的时候

for 选择 in 选择列表:
    # 做选择
    将该选择从选择列表移除
    路径.add(选择)
    backtrack(路径, 选择列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入选择列表

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节
点的选择列表和路径

List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举
整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子
问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高

N皇后问题

给你一个 N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击。皇后可以攻
击同一行、同一列、左上左下右上右下四个方向的任意单位

vector<vector<string>> res;

/* 输入棋盘边长 n，返回所有合法的放置 */
vector<vector<string>> solveNQueens(int n) {
    // '.' 表示空，'Q' 表示皇后，初始化空棋盘。
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0);
    return res;
}

// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(vector<string>& board, int row) {
    // 触发结束条件
    if (row == board.size()) {
        res.push_back(board);
        return;
    }
    int n = board[row].size();
    for (int col = 0; col < n; col++) {
        // 排除不合法选择
        if (!isValid(board, row, col)) 
            continue;
        // 做选择
        board[row][col] = 'Q';
        // 进入下一行决策
        backtrack(board, row + 1);
        // 撤销选择
        board[row][col] = '.';
    }
}

这部分主要代码，其实跟全排列问题差不多

/* 是否可以在 board[row][col] 放置皇后？ */
bool isValid(vector<string>& board, int row, int col) {
    int n = board.size();
    // 检查列是否有皇后互相冲突
    for (int i = 0; i < n; i++) {
        if (board[i][col] == 'Q')
            return false;
    }
    // 检查右上方是否有皇后互相冲突
    for (int i = row - 1, j = col + 1; 
            i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q')
            return false;
    }
    // 检查左上方是否有皇后互相冲突
    for (int i = row - 1, j = col - 1;
            i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q')
            return false;
    }
    return true;
}

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做
一些操作

def backtrack(...):
    for 选择 in 选择列表:
        做选择
        backtrack(...)
        撤销选择

BFS算法

BFS就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们
写BFS 算法都是用队列这种数据结构，每次将一个节点周围的所有节点加入队列
BFS 找到的路径一定是最短的，但代价就是空间复杂度比DFS 大很多

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

二叉树的最小高度

显然起点就是root 根节点，终点就是最靠近根节点的那个叶子节点

int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    // root 本身就是一层，depth 初始化为 1
    int depth = 1;
    
    while (!q.isEmpty()) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();
            /* 判断是否到达终点 */
            if (cur.left == null && cur.right == null) 
                return depth;
            /* 将 cur 的相邻节点加入队列 */
            if (cur.left != null)
                q.offer(cur.left);
            if (cur.right != null) 
                q.offer(cur.right);
        }
        /* 这里增加步数 */
        depth++;
    }
    return depth;
}

解开密码锁的最少次数

双向 BFS 优化

传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向BFS则
是从起点和终点同时开始扩散，当两边有交集的时候停止

二分查找

二分查找框架

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if
写清楚，这样可以清楚地展现所有细节

寻找一个数

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

寻找左侧边界的二分搜索

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

寻找右侧边界的二分查找

int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

滑动窗口算法

这个算法技巧的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案。
如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

股票买卖问题

打家劫舍问题

区间集合问题

NSUM问题

二叉树问题

链表类型