Q1主动回忆难度 3
1/12
算法与数据结构 · 高级 04
记忆强度
算法与数据结构高级题库第 4 组，共 12 张卡片。
算法与数据结构 · 高级 04
哈希表通过哈希函数把键转换为整数摘要，再映射到底层桶下标。
动态规划适用于问题能够拆成相互重叠的子问题，并且整体最优解可以由子问题的最优解组合得到的场景。
回溯是一种系统枚举候选解的深度优先搜索方法。
组合求和要求从候选数中选择若干元素，使总和等于目标值。
快速排序采用分治思想：选择一个基准值，通过分区把序列重新排列，使一侧元素不大于基准，另一侧元素不小于基准，再递归处理两个子区间。
拓扑排序是把有向图中的顶点排列成线性序列，使每条边 u → v 的起点 u 都出现在终点 v 之前。
Floyd-Warshall 算法用于计算带权图中所有顶点对之间的最短路径。
二叉树的每个结点至多拥有左、右两个子结点。
零一背包给定若干物品，每件物品有重量和价值，每件最多选择一次；
完全背包型找零问题给定若干正整数面额，每种硬币可以使用任意次，目标是在总金额恰好等于 amount 的前提下最小化硬币数量。
朴素字符串匹配会从文本的每个候选起点开始逐字符比较。
归并排序和快速排序都采用分治思想，也都能达到平均 O(n log n) 量级，但两者划分问题和组织数据的方式不同。