算法是啥？为啥要学它？
想象一下，你是个大厨（程序员），食材是数据，厨房是电脑。算法就是你的菜谱！ 一个烂菜谱（烂算法）会让你手忙脚乱，做出来的菜又慢又难吃（程序慢、结果差）。一个好菜谱（好算法）能让你行云流水，又快又好地端上美味佳肴（高效、正确的程序）。
为啥学？
效率！效率！效率！ 重要的事情说三遍。处理1条数据？无所谓。处理1亿条数据？好算法和烂算法可能就是“秒级”和“等到天荒地老”的区别。
写出更优雅的代码： 好的算法思想能让代码逻辑清晰，像读故事一样流畅（好吧，是技术故事...）。
面试通关秘籍： 大厂面试官最爱问：“这个场景下，你会用什么算法？为什么？” 答不上来？出门左转，慢走不送。
解决问题的通用思维： 算法教会你如何系统化、步骤化地拆解复杂问题，这种能力放之四海皆准。
核心思想：算法 = 解决问题的“武功秘籍”
第一章：排序算法 - 让混乱数据乖乖排队
1. 冒泡排序 (Bubble Sort) - 像汽水泡泡一样往上冒
心法： 从头到尾比较相邻元素，如果顺序不对就交换。每轮会把最大的元素“冒”到最后。重复直到所有元素都“冒”到位。
幽默比喻： 就像一群小朋友按身高排队，老师从队头走到队尾，看到前面同学比后面同学高就让他们换位置，走完一轮，最高的就到队尾了。老师重复走，直到所有小朋友都排好。
时空复杂度： O(n²) (时间), O(1) (空间 - 原地排序)
Java实现：
public static void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环：控制“走”多少轮（n-1轮）
for (int i = 0; i < n - 1; i++) {
// 内层循环：每轮“冒泡”的范围（越来越小）
for (int j = 0; j < n - i - 1; j++) {
// 如果前面的大哥比后面的小弟高，就交换位置（让他们按规矩站好！）
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1] - 经典的三杯水交换法
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// 想象老师喊：“这轮结束，最高那个站最后别动了！”
}
}2. 选择排序 (Selection Sort) - 我是“点名王”
心法： 在未排序部分中找到最小（或最大）元素，把它和未排序部分的第一个元素交换位置。重复这个过程。
幽默比喻： 老师要选最矮的站第一个。他扫视全班（未排序区），找到最矮的小明，让他和队伍第一个位置的同学交换。然后老师说：“小明站好了，剩下的同学注意！”，再从剩下的同学里找最矮的放到第二个位置，以此类推。
时空复杂度： O(n²) (时间), O(1) (空间 - 原地排序)
Java实现：
public static void selectionSort(int[] arr) {
int n = arr.length;
// 外层循环：控制当前要放“最小元素”的位置（从0到n-2）
for (int i = 0; i < n - 1; i++) {
int minIndex = i; // 假设当前位置i的元素就是最小的（先点个名）
// 内层循环：在未排序区（i+1 到末尾）找真正的“最矮个”
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 发现更矮的！更新“最矮个”记录
}
}
// 找到本轮真正的最小值位置minIndex，把它交换到当前位置i（让最矮的站到指定位置）
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
// 想象老师喊：“第i个位置的同学站好了！剩下的继续！”
}
}3. 插入排序 (Insertion Sort) - 像打扑克牌一样理牌
心法： 将待排序元素看作一张张要插入手牌的扑克。对于每个新元素，在已排序序列中从后向前扫描，找到合适位置插入。
幽默比喻： 你手里已经有一部分牌是排好序的（比如A, 5, 7, 10）。现在你摸到一张新牌8。你从右往左看手里的牌：10比8大，往后挪；7比8小，找到了！把8插在7后面。重复这个过程。
时空复杂度： O(n²) (平均/最坏), O(n) (最好 - 数组已有序), O(1) (空间 - 原地排序)
Java实现：
public static void insertionSort(int[] arr) {
int n = arr.length;
// 从第2张牌（索引1）开始摸牌（因为第一张牌自己就是有序的）
for (int i = 1; i < n; i++) {
int key = arr[i]; // 摸到的新牌key
int j = i - 1; // 开始和手里已排序的牌（i-1到0）比较
// 从右向左扫描手牌，比新牌大的都往后挪一个位置（腾地方！）
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // 把比新牌大的牌往后挪（别挡道！）
j = j - 1; // 继续向左看下一张牌
}
// 跳出循环时，j指向的位置就是新牌key应该插入位置的前一个（或者j=-1）
arr[j + 1] = key; // 把新牌key插入到正确位置（终于找到家了！）
}
}4. 归并排序 (Merge Sort) - “分而治之”的典范
心法： 分 (Divide)：把数组递归地分成两半。治 (Conquer)：当子数组小到只有一个元素时，自然有序。合 (Merge)：将两个已排序的子数组合并成一个大的有序数组（核心操作）。
幽默比喻： 要把全校学生按身高排序太难了！校长说：“分成两个班，各自排好再来找我”。两个班各自分成四个组...直到每个组只有1-2个人（自然有序）。然后开始“合并大会”：两个有序小组比较最前排同学身高，矮的先站到新队伍里，直到两个小组都合并完。不断合并小有序队伍成大的有序队伍，最终全校有序。
时空复杂度： O(n log n) (时间 - 非常稳定！), O(n) (空间 - 需要额外空间合并)
Java实现：
// 主方法：驱动归并排序
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) return; // 空或单元素数组直接返回
int[] temp = new int[arr.length]; // 申请一个临时“操场”用于合并
mergeSort(arr, 0, arr.length - 1, temp); // 开始真正的分治过程
}
// 递归分治方法 (分 + 合)
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) { // 只要当前区间还有至少2个元素，就继续分
int mid = left + (right - left) / 2; // 找到中间点（避免整数溢出）
// 分！递归排序左半部分 (left...mid)
mergeSort(arr, left, mid, temp);
// 分！递归排序右半部分 (mid+1...right)
mergeSort(arr, mid + 1, right, temp);
// 合！将排好序的左右两半合并到原数组arr的[left, right]区间
merge(arr, left, mid, right, temp);
}
}
// 核心：合并两个有序子数组 arr[left...mid] 和 arr[mid+1...right]
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 1. 先把要合并的区间[left, right]复制到临时操场temp
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left; // 左半部分的“排头兵”指针 (指向temp)
int j = mid + 1; // 右半部分的“排头兵”指针 (指向temp)
int k = left; // 合并后要放入原数组arr的位置指针
// 2. 合并：比较左右两个“排头兵”，谁矮(小)谁先站到新队伍(k位置)！
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) { // 左排头兵更矮(或相等)
arr[k] = temp[i]; // 左排头兵站到新位置k
i++; // 左队伍派出下一个排头兵
} else { // 右排头兵更矮
arr[k] = temp[j]; // 右排头兵站到新位置k
j++; // 右队伍派出下一个排头兵
}
k++; // 新队伍位置k往后挪一位
}
// 3. 处理“剩余兵力”：如果左半部分还有同学没站队(肯定都比已站的都高了)
while (i <= mid) {
arr[k] = temp[i]; // 剩下的左半部分同学依次站队
k++;
i++;
}
// 3. 或者，如果右半部分还有同学没站队(同理)
while (j <= right) {
arr[k] = temp[j]; // 剩下的右半部分同学依次站队
k++;
j++;
}
// 合并大会圆满结束！arr[left..right] 现在完全有序！
}5. 快速排序 (Quick Sort) - “分而治之”的快枪手
心法： 选择一个元素作为 基准 (pivot)。分区 (Partition)：把所有小于pivot的元素移到它左边，大于pivot的移到右边（等于的放哪边都行）。递归地对pivot左右两边的子数组进行快排。
幽默比喻： 体育老师要按身高分组。他随机挑一个同学当“标杆”(pivot)。一声令下：“比标杆矮的站左边！比标杆高的站右边！动作快！”。标杆自己站中间。然后老师对左边队和右边队分别重复这个过程，直到每个小队只有1-2个人（自然有序）。最后整个队伍就排好了。老师选标杆的方式（选第一个、最后一个、中间、随机）会影响效率。
时空复杂度： O(n log n) (平均 - 非常快), O(n²) (最坏 - 比如数组已有序且选第一个/最后一个当pivot), O(log n) (空间 - 递归栈深度)
Java实现 (Lomuto分区方案)：
// 主方法：驱动快速排序
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
// 递归分治方法
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 分区操作，返回pivot的最终位置
int pivotIndex = partition(arr, low, high);
// 分！递归排序pivot左边的子数组
quickSort(arr, low, pivotIndex - 1);
// 分！递归排序pivot右边的子数组
quickSort(arr, pivotIndex + 1, high);
}
}
// Lomuto分区方法 (常用，但Hoare分区更优，这里用Lomuto演示)
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为pivot（容易导致最坏情况，实际常用随机选）
int i = low - 1; // i 指向“小于pivot区域”的最后一个元素
// j指针从low遍历到high-1 (因为high是pivot)
for (int j = low; j < high; j++) {
// 如果当前元素arr[j] <= pivot（矮个子）
if (arr[j] <= pivot) {
i++; // 扩张“小于pivot区域”
// 交换arr[i]和arr[j]：把矮个子arr[j]换到“小于区域”的末尾
swap(arr, i, j);
}
// 比pivot高的(j位置元素)不用管，j继续往后走，它自然就在“大于区域”了
}
// 最后，把pivot（arr[high]）交换到“小于区域”后面（i+1位置），这就是pivot的最终位置
swap(arr, i + 1, high);
return i + 1; // 返回pivot的最终位置索引
}
// 辅助交换方法
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}6. 堆排序 (Heap Sort) - 利用“二叉堆”的力量
心法： 建堆 (Heapify)：把无序数组构造成一个最大堆 (Max Heap)（父节点值 >= 子节点值）。此时堆顶（根节点）是最大元素。排序：将堆顶元素（最大）与堆的最后一个元素交换，然后堆的大小减1（最大元素已归位）。对新的堆顶元素进行下滤 (Sink/Down Heapify) 操作，使其重新满足最大堆性质。重复交换和堆化过程，直到堆中只剩一个元素。
幽默比喻： 想象一个金字塔擂台（最大堆）。塔顶的擂主是实力最强的。比赛规则：
先搭建好金字塔（建堆），确保每层的大哥都比下一层的小弟强（父>子）。
把塔顶最强的擂主请下来，放到冠军领奖台（数组最后）。
把塔底最后一个小弟临时放到塔顶（交换）。
新塔顶小弟开始挑战：他需要和下一层最强的两个小弟PK，如果输了就和赢的那个交换位置（下滤），直到他掉到符合他实力的位置，金字塔秩序恢复。
重复2-4步，直到所有“强者”都按实力从弱到强（数组从前往后）站上领奖台。
时空复杂度： O(n log n) (时间 - 非常稳定), O(1) (空间 - 原地排序)
Java实现：
public static void heapSort(int[] arr) {
int n = arr.length;
// 1. 建堆：从最后一个非叶子节点开始，自底向上进行下滤
// 最后一个非叶子节点索引 = n/2 - 1
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i); // 对以i为根的子树进行下滤，使其满足最大堆
}
// 2. 排序：一个个把堆顶元素（最大）交换到数组末尾，并调整堆
for (int i = n - 1; i > 0; i--) {
// 交换当前堆顶（arr[0]，最大）和未排序部分的最后一个元素（arr[i]）
swap(arr, 0, i);
// 堆大小减1（i），对新的堆顶（arr[0]）进行下滤，重新调整成最大堆（范围是0到i-1）
heapify(arr, i, 0);
}
}
// 下滤操作：确保以root为根的子树满足最大堆性质（前提是root的左右子树已是最大堆）
private static void heapify(int[] arr, int heapSize, int root) {
int largest = root; // 假设根是最大值
int left = 2 * root + 1; // 左孩子索引
int right = 2 * root + 2; // 右孩子索引
// 如果左孩子存在且比当前假设的最大值大
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
// 如果右孩子存在且比当前已知的最大值（可能是root或left）大
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点了，说明需要交换并继续下滤
if (largest != root) {
swap(arr, root, largest); // 把真正的强者换上来当根
heapify(arr, heapSize, largest); // 递归地对被交换下去的原root（现在在largest位置）进行下滤
}
}
// 辅助交换方法
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}7. 希尔排序 (Shell Sort) - 插入排序的“超级赛亚人”形态
心法： 是插入排序的改进。定义一个增量序列 (gap sequence)。对每个增量gap，将数组分成gap个子序列（每个子序列由相隔gap的元素组成），对每个子序列进行插入排序。随着增量gap不断减小（通常最后减到1），数组变得越来越“部分有序”，最后当gap=1时做一次标准的插入排序，效率就很高了。关键在于增量序列的选择（如Hibbard, Sedgewick序列）。
幽默比喻： 想象一群学生站成多列纵队（gap决定列数）。第一次，让他们按列（相隔gap的同学组成一列）进行插入排序（每列内部按身高排）。然后减少列数（增大间隔，实际是减小gap），重新站队，再按列排。最后让他们站成一列（gap=1），做最后一次快速插入排序。因为之前几次排序让队伍“基本有序”了，这次最后的插入排序就会非常快。
时空复杂度： 取决于增量序列，最好可到O(n log² n)，平均优于O(n²)，最坏O(n²)。O(1)空间。
Java实现 (使用Knuth增量序列 gap = 3*gap + 1)：
public static void shellSort(int[] arr) {
int n = arr.length;
// 1. 计算初始增量gap (使用Knuth序列：1, 4, 13, 40, 121...，找到小于n的最大值)
int gap = 1;
while (gap < n / 3) {
gap = 3 * gap + 1; // 1, 4, 13, 40, 121...
}
// 2. 开始希尔排序，增量gap不断减小直到1
while (gap >= 1) {
// 3. 对当前增量gap下的每个子序列进行插入排序 (i从gap开始，因为0到gap-1是各子序列的第一个元素)
for (int i = gap; i < n; i++) {
// 对子序列 arr[i], arr[i-gap], arr[i-2*gap], ... 进行插入排序
int temp = arr[i]; // 当前要插入的元素
int j = i;
// 在子序列中从后向前扫描，寻找temp的插入位置
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap]; // 比temp大的元素后移gap位
j -= gap; // 向前移动gap位
}
arr[j] = temp; // 插入temp到正确位置
}
// 4. 减小gap (Knuth序列的逆：gap = (gap - 1) / 3)
gap /= 3; // 或者 gap = (gap - 1) / 3; 确保最终gap=1
}
}8. 计数排序 (Counting Sort) - 数数小能手
心法： 不是基于比较！适用于元素范围已知且较小的整数。统计每个元素出现的次数。根据统计信息直接计算出每个元素在最终有序数组中的位置。
幽默比喻： 老师有红、黄、蓝三种颜色的球要按颜色排序。他不用比较球，而是：1. 数出红球有3个，黄球有2个，蓝球有4个。2. 知道顺序是红、黄、蓝。3. 直接按数量放：前3个位置放红球，接着2个放黄球，最后4个放蓝球。搞定！
时空复杂度： O(n + k) (时间 - n是元素个数，k是整数范围大小), O(n + k) (空间 - 需要计数数组和输出数组)
Java实现 (假设元素范围是0到max)：
public static void countingSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
// 1. 找出数组中的最大值 (确定范围k)
int max = arr[0];
for (int num : arr) {
if (num > max) max = num;
}
// 2. 创建计数数组count，大小为 max+1 (索引0..max)，初始化为0
int[] count = new int[max + 1];
// 3. 计数：统计每个元素出现的次数
for (int num : arr) {
count[num]++; // arr[i]这个值出现了一次
}
// 4. (可选，稳定排序需要) 累加计数：count[i]表示小于等于i的元素有多少个
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// 5. 创建输出数组output (大小和arr一样)
int[] output = new int[arr.length];
// 6. (为了稳定性) 反向遍历原数组arr，根据count数组将元素放到output的正确位置
for (int i = arr.length - 1; i >= 0; i--) {
int num = arr[i];
output[count[num] - 1] = num; // count[num] 是num应该在的位置(从1计数)，减1得到数组索引(从0计数)
count[num]--; // 放了一个num，计数减1，为下一个相同的num腾位置（保证稳定性）
}
// 7. (如果不要求原地) 将output数组复制回原数组arr
System.arraycopy(output, 0, arr, 0, arr.length);
}9. 桶排序 (Bucket Sort) - 化整为零，各个击破
心法： 将元素根据某种规则（如数值范围）分配到有限数量的“桶”中。对每个桶内的元素进行排序（通常使用其他排序算法，如插入排序）。最后按桶的顺序依次取出所有元素。
幽默比喻： 老师要把全班按0-59分，60-79分，80-100分分成三个桶。学生们先按分数范围进入各自的桶。然后老师对每个桶内的学生单独按具体分数排序（比如用插入排序）。最后，按桶的顺序（低分桶 -> 中分桶 -> 高分桶）把学生依次叫出来，整个班级就按分数排好队了。
时空复杂度： 取决于数据分布和桶内排序算法。理想情况（均匀分布）下O(n)，最坏O(n²)。空间O(n + k)（k是桶数）。
Java实现 (简化版，假设元素在[0, 1)范围内)：
public static void bucketSort(double[] arr) {
if (arr == null || arr.length <= 1) return;
int n = arr.length;
// 1. 创建桶 (这里用ArrayList的数组，桶的数量设为n)
List<Double>[] buckets = new ArrayList[n];
for (int i = 0; i < n; i++) {
buckets[i] = new ArrayList<>(); // 初始化每个桶
}
// 2. 将元素分配到桶中 (假设元素在[0,1)之间)
for (double num : arr) {
int bucketIndex = (int) (num * n); // 计算属于哪个桶
buckets[bucketIndex].add(num); // 放入对应的桶
}
// 3. 对每个桶内部进行排序 (这里用Collections.sort，实际可能是插入排序等)
for (List<Double> bucket : buckets) {
Collections.sort(bucket); // 对每个小桶排序
}
// 4. 按桶顺序（0号桶，1号桶...）将元素依次放回原数组
int index = 0;
for (List<Double> bucket : buckets) {
for (double num : bucket) {
arr[index++] = num;
}
}
}10. 基数排序 (Radix Sort) - 按位排序的“老学究”
心法： 适用于整数或字符串。从最低位（个位）到最高位，依次对每一位使用稳定的排序算法（通常是计数排序）进行排序。经过多轮排序后，整个序列就有序了。
幽默比喻： 要排序一批电话号码。老学究说：“先只看最后一位数字排序！”。排好后他说：“现在只看倒数第二位数字排序！但要保持最后一位的顺序哦（稳定）！”。接着看倒数第三位...直到看完第一位。最终，电话号码就完全有序了。
时空复杂度： O(d * (n + k)) (时间 - d是最大位数，k是每位可能的基数如10), O(n + k) (空间 - 计数排序开销)
Java实现 (LSD - 从低位开始，用于整数)：
public static void radixSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
// 1. 找出最大值，确定最大位数d
int max = Arrays.stream(arr).max().getAsInt();
int maxDigit = (int) (Math.log10(max) + 1); // 计算最大位数
// 2. 创建10个桶（0~9），用于每一位的计数排序
int[][] buckets = new int[10][arr.length]; // 二维数组模拟桶
int[] bucketCount = new int[10]; // 每个桶当前存放的元素个数
int mod = 10; // 用于取模
int div = 1; // 用于取指定位的数字
// 3. 对每一位（从个位开始）进行计数排序
for (int d = 0; d < maxDigit; d++, mod *= 10, div *= 10) {
// 3.1 分配：遍历数组，根据当前位数字放入对应桶
for (int num : arr) {
int digit = (num % mod) / div; // 取出当前位的数字(0-9)
buckets[digit][bucketCount[digit]] = num; // 放入桶
bucketCount[digit]++; // 该桶计数+1
}
// 3.2 收集：按桶顺序（0->9）依次取出元素放回原数组
int index = 0;
for (int digit = 0; digit < 10; digit++) {
if (bucketCount[digit] > 0) {
// 取出当前桶bucketCount[digit]个元素
for (int j = 0; j < bucketCount[digit]; j++) {
arr[index++] = buckets[digit][j];
}
// 清空该桶计数，为下一位排序准备
bucketCount[digit] = 0;
}
}
}
}第二章：查找算法 - 大海捞针的技巧
1. 线性查找 (Linear Search) - 老实人挨个问
心法： 从第一个元素开始，逐个检查每个元素，直到找到目标或遍历完所有元素。
幽默比喻： 在人群中找人，你从第一个人开始问：“你是小明吗？”，“你是小明吗？”...一直问到最后一个。
时空复杂度： O(n) (时间), O(1) (空间)
Java实现：
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // 找到了，返回索引
}
}
return -1; // 没找到
}2. 二分查找 (Binary Search) - “猜数字”大师
心法： 要求数组必须有序。每次比较目标值与数组中间元素。如果相等则找到；如果目标值小于中间元素，则在左半部分继续二分查找；否则在右半部分继续二分查找。
幽默比喻： 猜1-100的数字。你猜50？我说大了。你猜25？我说小了。你猜37？我说大了。你猜31？对了！二分查找每次都猜中间值，根据反馈缩小一半搜索范围。
时空复杂度： O(log n) (时间 - 超级高效！), O(1) (空间 - 迭代实现)
Java实现 (迭代版)：
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) { // 搜索区间 [left, right] 还存在
int mid = left + (right - left) / 2; // 防止整数溢出，计算中间索引
if (arr[mid] == target) {
return mid; // 找到目标！
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分 [mid+1, right]
} else {
right = mid - 1; // 目标在左半部分 [left, mid-1]
}
}
return -1; // 没找到
}3. 插值查找 (Interpolation Search) - 二分查找的“预言家”表弟
心法： 二分查找的改进，适用于元素均匀分布的有序数组。它根据目标值在整个取值范围中的大致位置来预测其索引，而不是简单地取中点。
公式：
mid = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])幽默比喻： 猜1-100的数字，你知道数字是均匀分布的。这次你想猜得更“智能”。如果目标是30，范围是1-100，你可能会猜
1 + (30-1)*(100-1)/(100-1) ≈ 30，一下就猜中了！它根据目标值在范围中的比例来猜位置。时空复杂度： 平均O(log log n) (在均匀分布下超快！)，最坏O(n)（分布不均时退化）。O(1)空间。
Java实现：
public static int interpolationSearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
// 注意：需要确保数组元素值范围，且arr[high] != arr[low] (否则除零)
while (low <= high && target >= arr[low] && target <= arr[high]) {
// 关键：使用插值公式计算预测位置mid
int mid = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
low = mid + 1; // 目标在右半部分
} else {
high = mid - 1; // 目标在左半部分
}
}
return -1; // 没找到或target不在[arr[low], arr[high]]范围内
}4. 哈希表查找 (Hash Table Lookup) - 直达专车
心法： 利用哈希函数 (Hash Function) 将键 (Key) 映射到一个固定范围的索引（桶位置）。理想情况下，通过键可以直接计算（O(1)时间）到存储值的位置。需要处理哈希冲突（不同键映射到相同位置），常用方法有链地址法（数组+链表/树）、开放地址法（线性探测、平方探测等）。
幽默比喻： 图书馆按书名首字母分类（哈希函数）。找《算法导论》，首字母是'S'，直接去S区找（理想情况O(1)）。但S区有很多书（冲突），你需要在这个区内部再按规则找（解决冲突）。
时空复杂度： 平均 O(1) 查找/插入/删除（理想哈希函数+好冲突解决），最坏 O(n) （所有键都冲突，退化成链表）。空间O(n)。
Java实现 (使用HashMap，内部已处理冲突)：
import java.util.HashMap;
public class HashLookup {
public static void main(String[] args) {
HashMap<String, Integer> phoneBook = new HashMap<>();
// 存储 (键-值对)
phoneBook.put("Alice", 123456);
phoneBook.put("Bob", 654321);
phoneBook.put("Charlie", 987654);
// 查找
Integer aliceNumber = phoneBook.get("Alice"); // O(1) 平均时间
if (aliceNumber != null) {
System.out.println("Alice's number is: " + aliceNumber);
} else {
System.out.println("Alice not found!");
}
}
}第三章：图论算法 - 探索关系网络
(先建立图的基础表示，常用邻接矩阵或邻接表，这里用邻接表更通用)
import java.util.*;
// 表示图的类 (无向图)
class Graph {
private int V; // 顶点数
private LinkedList<Integer>[] adj; // 邻接表数组
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList<>();
}
}
// 添加边 (无向图，两边都要加)
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
// 获取顶点v的邻接点列表
public LinkedList<Integer> getAdj(int v) {
return adj[v];
}
public int getV() {
return V;
}
}1. 广度优先搜索 (BFS) - 地毯式搜索，由近及远
心法： 从起点开始，先访问所有直接邻居（第一层），然后访问邻居的邻居（第二层），以此类推。使用队列 (Queue) 来管理待访问的顶点。
应用： 无权图的最短路径（按层数计算）、网络爬虫、社交网络好友推荐（几度关系）。
时空复杂度： O(V + E) (时间 - 访问所有顶点和边), O(V) (空间 - 队列和访问标记)
Java实现：
public static void BFS(Graph graph, int start) {
int V = graph.getV();
boolean[] visited = new boolean[V]; // 标记顶点是否被访问过
Queue<Integer> queue = new LinkedList<>(); // 使用队列
visited[start] = true; // 标记起点已访问
queue.add(start); // 起点入队
while (!queue.isEmpty()) {
int current = queue.poll(); // 从队首取出一个顶点
System.out.print(current + " "); // 访问它（或做其他操作）
// 遍历当前顶点的所有邻接点
for (int neighbor : graph.getAdj(current)) {
if (!visited[neighbor]) { // 如果邻接点没被访问过
visited[neighbor] = true; // 标记为已访问
queue.add(neighbor); // 邻接点入队（等着下一层访问）
}
}
}
}2. 深度优先搜索 (DFS) - 一条道走到黑，再回溯
心法： 从起点开始，沿着一条路径尽可能深入地访问，直到没有未访问的邻居，然后回溯到上一个顶点，尝试其他路径。通常使用递归或栈 (Stack) 实现。
应用： 拓扑排序、检测环、寻找连通分量、解决迷宫问题。
时空复杂度： O(V + E) (时间), O(V) (空间 - 递归栈深度或栈大小)
Java实现 (递归版)：
public static void DFSRecursive(Graph graph, int start) {
int V = graph.getV();
boolean[] visited = new boolean[V]; // 标记顶点是否被访问过
DFSUtil(graph, start, visited); // 调用递归辅助函数
}
private static void DFSUtil(Graph graph, int v, boolean[] visited) {
visited[v] = true; // 标记当前顶点v已访问
System.out.print(v + " "); // 访问它（或做其他操作）
// 递归访问所有未访问的邻接点
for (int neighbor : graph.getAdj(v)) {
if (!visited[neighbor]) {
DFSUtil(graph, neighbor, visited); // 深入探索
}
}
}3. 迪杰斯特拉算法 (Dijkstra's Algorithm) - 单源最短路径 (无负权边)
心法： 求一个顶点（源点）到图中所有其他顶点的最短路径（路径权重和最小）。使用贪心策略和优先队列 (最小堆)。维护一个距离数组
dist[]，dist[v]表示源点到v的当前已知最短距离。每次从优先队列（按dist值排序）中取出dist最小的顶点u（它此时的距离已确定），然后松弛u的所有邻接点v（即尝试通过u到达v是否能获得更短的dist[v]）。幽默比喻： 你（源点）用滴滴打车去城市各处。系统（算法）知道每条路的长度（权重）。它先派车去离你最近的点A（dist[A]确定）。然后看：从A出发，能不能更快地到达A的邻居B、C？（松弛操作）。接着在所有已知距离（包括刚更新的B、C）中选择距离最小的点（比如B），确定到B的最短距离。重复这个过程，直到知道到所有地方的最短距离和路线。
时空复杂度： O((V+E) log V) (使用优先队列), O(V) (空间)
Java实现 (使用PriorityQueue)：
import java.util.*;
public static void dijkstra(Graph graph, int src) {
int V = graph.getV();
int[] dist = new int[V]; // 存储源点到各点的最短距离
Arrays.fill(dist, Integer.MAX_VALUE); // 初始化为无穷大
dist[src] = 0; // 源点到自己的距离是0
// 优先队列（最小堆），按dist值排序。元素是 [距离, 顶点]
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, src}); // 源点入队
while (!pq.isEmpty()) {
int[] pair = pq.poll();
int u = pair[1]; // 当前距离最小的顶点u
int uDist = pair[0]; // u的当前距离
// 重要：如果队列中的u的dist不是最新的（被其他路径松弛过更小的值），跳过这个旧的u
if (uDist != dist[u]) continue;
// 松弛u的所有邻接点v
for (int v : graph.getAdj(u)) {
// 假设图有权重，这里简化，每条边权重为1。实际应通过邻接点获取边权重weight
int weight = 1; // 实际情况：int weight = graph.getWeight(u, v);
int newDist = dist[u] + weight; // 尝试通过u到达v的距离
// 如果找到更短的路径到v
if (newDist < dist[v]) {
dist[v] = newDist; // 更新v的最短距离
pq.offer(new int[]{newDist, v}); // 将v（或更新v）放入优先队列
}
}
}
// 打印结果
System.out.println("顶点\t距离源点");
for (int i = 0; i < V; i++) {
System.out.println(i + "\t\t" + dist[i]);
}
}4. 弗洛伊德算法 (Floyd-Warshall Algorithm) - 所有顶点对之间的最短路径
心法： 计算图中任意两个顶点之间的最短路径。使用动态规划。维护一个二维距离矩阵
dist[i][j]。通过顶点k（作为中间点）来尝试缩短i到j的距离：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。对所有可能的k进行迭代。时空复杂度： O(V³) (时间), O(V²) (空间)
Java实现 (核心部分)：
public static void floydWarshall(int[][] graph) {
int V = graph.length;
int[][] dist = new int[V][V]; // 距离矩阵
// 初始化dist矩阵：直接使用输入的邻接矩阵graph (graph[i][j]表示i到j的直接边权，INF表示无边)
for (int i = 0; i < V; i++) {
System.arraycopy(graph[i], 0, dist[i], 0, V);
}
// 三重循环：k, i, j
for (int k = 0; k < V; k++) { // 中间顶点k
for (int i = 0; i < V; i++) { // 起点i
for (int j = 0; j < V; j++) { // 终点j
// 如果经过顶点k中转的路径更短，且i->k和k->j有路径
if (dist[i][k] != Integer.MAX_VALUE &&
dist[k][j] != Integer.MAX_VALUE &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j]; // 更新最短距离
}
}
}
}
// ... 打印dist矩阵 ...
}5. 贝尔曼-福特算法 (Bellman-Ford Algorithm) - 单源最短路径 (可处理负权边，检测负权环)
心法： 也能求单源最短路径。比Dijkstra慢，但能处理负权边，并能检测负权环。进行V-1轮松弛操作（V是顶点数）。每轮对所有边进行松弛。如果第V轮还能松弛成功，说明存在负权环。
时空复杂度： O(V*E) (时间), O(V) (空间)
Java实现 (核心部分)：
public static boolean bellmanFord(List<Edge> edges, int V, int src) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// 1. 进行V-1轮松弛
for (int i = 1; i < V; i++) {
for (Edge edge : edges) {
int u = edge.src;
int v = edge.dest;
int weight = edge.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight; // 松弛成功
}
}
}
// 2. 检查第V轮：如果还能松弛，说明有负权环
for (Edge edge : edges) {
int u = edge.src;
int v = edge.dest;
int weight = edge.weight;
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("图包含负权环！");
return false; // 返回false表示有负权环
}
}
// ... 打印最短路径 (无负权环) ...
return true;
}
// 需要定义边类
class Edge {
int src, dest, weight;
Edge(int s, int d, int w) {
src = s; dest = d; weight = w;
}
}6. 克鲁斯卡尔算法 (Kruskal's Algorithm) - 最小生成树 (MST) 的“拼图”
心法： 用于在连通无向带权图中找最小生成树 (MST)（连接所有顶点的树，且总权重最小）。将边按权重从小到大排序。依次选择权重最小的边，如果加入这条边不会在当前的MST森林中形成环，就加入它。使用并查集 (Union-Find) 高效检测环。
幽默比喻： 要在几个城市间建成本最低的通信网（连通所有城市）。把所有可能的路（边）按造价（权重）从低到高排序。从最便宜的路开始选。选路时，如果这条路连接的两个城市还不属于同一个连通区域（避免成环），就修这条路，并把这两个区域合并。重复直到所有城市连通。
时空复杂度： O(E log E) 或 O(E log V) (主要花在排序边), O(V) (空间 - 并查集)
Java实现 (需要并查集)：
import java.util.*;
public static void kruskalMST(Graph graph) {
int V = graph.V;
List<Edge> result = new ArrayList<>(); // 存储MST的边
int e = 0; // MST中的边数计数器 (最终应为V-1)
// 1. 获取图中所有边并排序 (按权重升序)
List<Edge> edges = graph.getAllEdges();
Collections.sort(edges, Comparator.comparingInt(e -> e.weight));
// 2. 初始化并查集 (每个顶点自成一个集合)
UnionFind uf = new UnionFind(V);
// 3. 遍历排序后的边
int index = 0;
while (e < V - 1 && index < edges.size()) {
Edge nextEdge = edges.get(index++);
int x = uf.find(nextEdge.src);
int y = uf.find(nextEdge.dest);
// 如果加入这条边不会形成环 (即src和dest不在同一个集合)
if (x != y) {
result.add(nextEdge); // 将边加入结果MST
e++; // MST边数+1
uf.union(x, y); // 合并两个集合
}
}
// ... 打印MST的边和总权重 ...
}
// 简化版并查集 (Union-Find/Disjoint Set) 实现
class UnionFind {
int[] parent, rank;
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) parent[i] = i; // 每个点都是自己的根
}
public int find(int x) { // 带路径压缩
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) { // 按秩合并
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}7. 普里姆算法 (Prim's Algorithm) - 最小生成树 (MST) 的“生长”
心法： 也用于找MST。从一个顶点开始，逐步“生长”MST。维护一个集合（MST顶点集）和一个优先队列（存放连接MST集和非MST集的边，按权重排序）。每次选择权重最小的横切边加入MST，并将其连接的顶点加入集合。
幽默比喻： 还是建通信网。这次你随便选一个城市A作为起点（MST种子）。看看从A出发，到哪些未连接城市的路最便宜（横切边）。选最便宜的那条路（比如到B），修通AB，现在A和B在网内了。再看现在网内城市（A, B）到网外城市的路，哪条最便宜？选最便宜的修（比如B到C）。重复，直到所有城市入网。
时空复杂度： O(E log V) (使用优先队列), O(V) (空间)
Java实现 (使用优先队列)：
import java.util.*;
public static void primMST(Graph graph) {
int V = graph.getV();
boolean[] inMST = new boolean[V]; // 标记顶点是否在MST中
int[] parent = new int[V]; // parent[i] 记录MST中顶点i的父节点（连接i的那条边的另一端）
int[] key = new int[V]; // key[i] 表示连接到顶点i的最小边权重（初始无穷大）
Arrays.fill(key, Integer.MAX_VALUE);
// 优先队列，按key值排序。元素是 [key, vertex]
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
key[0] = 0; // 选择顶点0作为起点
pq.offer(new int[]{0, 0}); // [key=0, vertex=0]
parent[0] = -1; // 根节点没有父节点
while (!pq.isEmpty()) {
int[] pair = pq.poll();
int u = pair[1]; // 取出当前key最小的顶点u
inMST[u] = true; // 将u加入MST集合
// 遍历u的所有邻接点v
for (int v : graph.getAdj(u)) {
int weight = graph.getWeight(u, v); // 获取边(u, v)的权重
// 如果v不在MST中，且边(u, v)的权重小于当前连接v的已知最小权重(key[v])
if (!inMST[v] && weight < key[v]) {
key[v] = weight; // 更新连接到v的最小权重
parent[v] = u; // 更新v在MST中的父节点为u
pq.offer(new int[]{key[v], v}); // 将v（或更新v的key）放入优先队列
}
}
}
// ... 打印MST的边 (parent数组) 和总权重 (sum(key)) ...
}第四章：动态规划 (DP) - 记住过去，避免重复劳动
核心思想： 将复杂问题分解为重叠子问题。存储子问题的解（通常用数组/表），避免重复计算。自底向上或带备忘录的自顶向下求解。
1. 斐波那契数列 (Fibonacci) - DP的“Hello World”
递归 (低效)：
fib(n) = fib(n-1) + fib(n-2)，存在大量重复计算。DP (高效)：
状态定义：
dp[i]表示第i个斐波那契数。状态转移方程：
dp[i] = dp[i-1] + dp[i-2](i >= 2)初始化：
dp[0] = 0, dp[1] = 1计算顺序： 自底向上，从i=2计算到i=n。
时空复杂度： O(n) (时间), O(n) (空间 - 可优化到O(1))
Java实现 (自底向上)：
public static int fibDP(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移
}
return dp[n];
}
// 空间优化版 (O(1)空间)
public static int fibDPOpt(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1, current = 0;
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}2. 0/1背包问题 (0/1 Knapsack) - 经典的取舍问题
问题： 有N件物品和一个容量为W的背包。物品i有重量
wt[i]和价值val[i]。如何选择装入背包的物品（每件物品要么选要么不选），使得总价值最大，且总重量不超过W？DP解法：
状态定义：
dp[i][w]表示考虑前i件物品，在背包容量为w时能获得的最大价值。状态转移方程：
不选第i件物品：
dp[i][w] = dp[i-1][w]选第i件物品（需满足w >= wt[i-1]）：
dp[i][w] = dp[i-1][w - wt[i-1]] + val[i-1]取两者最大值：
dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1]) if w >= wt[i-1]
初始化：
dp[0][w] = 0(考虑0件物品，价值为0)计算顺序： 自底向上，i从1到N，w从0到W。
时空复杂度： O(NW) (时间), O(NW) (空间 - 可优化到O(W))
Java实现 (自底向上，未优化空间)：
public static int knapSack(int W, int[] wt, int[] val, int n) {
int[][] dp = new int[n + 1][W + 1];
// 初始化：考虑0件物品，价值为0 (Java数组默认0，可省略显式初始化第一行)
for (int i = 1; i <= n; i++) { // i 从1到n (表示考虑前i件物品)
for (int w = 0; w <= W; w++) { // w 从0到W
// 不选第i件物品
dp[i][w] = dp[i - 1][w];
// 如果第i件物品的重量小于等于当前背包容量w，考虑选它
if (w >= wt[i - 1]) { // 注意：wt和val索引是i-1（因为i从1开始）
int include = dp[i - 1][w - wt[i - 1]] + val[i - 1];
// 取选和不选的最大值
if (include > dp[i][w]) {
dp[i][w] = include;
}
}
}
}
return dp[n][W]; // 考虑前n件物品，容量W时的最大价值
}3. 最长公共子序列 (LCS) - 找共同记忆
问题： 给定两个序列
X和Y，找出它们最长的公共子序列（不要求连续）。DP解法：
状态定义：
dp[i][j]表示X[0..i-1]和Y[0..j-1]的最长公共子序列长度。状态转移方程：
如果
X[i-1] == Y[j-1]：dp[i][j] = dp[i-1][j-1] + 1否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始化：
dp[0][j] = 0(X空序列),dp[i][0] = 0(Y空序列)计算顺序： 自底向上，i从1到m（X长度），j从1到n（Y长度）。
时空复杂度： O(mn) (时间), O(mn) (空间 - 可优化到O(min(m, n)))
Java实现：
public static int lcs(String X, String Y) {
int m = X.length();
int n = Y.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X.charAt(i - 1) == Y.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n]; // 返回LCS长度
// 若要构造LCS字符串，需要回溯dp表
}4. 最长递增子序列 (LIS) - 寻找上升轨迹
问题： 给定一个整数序列，找到最长严格递增子序列的长度（不一定连续）。
DP解法 (O(n²))：
状态定义：
dp[i]表示以第i个元素结尾的最长递增子序列的长度。状态转移方程：
dp[i] = 1 + max(dp[j])对于所有0 <= j < i且arr[j] < arr[i]。如果没有这样的j，则dp[i] = 1。初始化： 所有
dp[i] = 1(单个元素本身就是一个长度为1的LIS)。计算顺序： 自底向上，i从0到n-1。最后结果是
max(dp[i])。
更优解法 (O(n log n))： 贪心 + 二分查找，维护一个tails数组，tails[k]存储长度为k+1的IS的最小尾部元素。
Java实现 (O(n²) DP)：
public static int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1); // 每个元素自身至少构成长度为1的LIS
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) { // 只有在前面有更小的数时
if (dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1; // 更新以nums[i]结尾的LIS长度
}
}
}
maxLen = Math.max(maxLen, dp[i]); // 更新全局最大值
}
return maxLen;
}第五章：贪心算法 - 活在当下，最优选择
核心思想： 在每一步都做出当前看起来最优的选择（局部最优解），希望这些局部最优解能导致全局最优解。关键点：贪心策略必须能保证局部最优能最终达到全局最优，这需要证明（或问题本身具有贪心选择性质）。
1. 活动选择问题 (Activity Selection) - 选最多的兼容活动
问题： 给定n个活动，每个活动有开始时间
start[i]和结束时间end[i]。选择最大的互不重叠（兼容）活动集合。贪心策略： 总是选择结束时间最早的活动（给剩余时间留下更多机会）。
步骤：
按结束时间
end[i]对活动升序排序。选择结束时间最早的活动，加入结果集。
从剩余活动中选择第一个开始时间大于等于上一个选中活动结束时间的活动（兼容），加入结果集。
重复步骤3，直到没有活动可选。
时空复杂度： O(n log n) (排序), O(n) (空间 - 存储结果)
Java实现：
import java.util.*;
public static List<int[]> activitySelection(int[][] activities) {
// activities[i] = [start_i, end_i]
List<int[]> result = new ArrayList<>();
if (activities == null || activities.length == 0) return result;
// 1. 按结束时间升序排序
Arrays.sort(activities, Comparator.comparingInt(a -> a[1]));
// 2. 总是选第一个活动（结束最早的）
result.add(activities[0]);
int lastEnd = activities[0][1];
// 3. 遍历剩余活动
for (int i = 1; i < activities.length; i++) {
int start = activities[i][0];
int end = activities[i][1];
// 如果当前活动的开始时间 >= 上一个选中活动的结束时间，则兼容
if (start >= lastEnd) {
result.add(activities[i]);
lastEnd = end; // 更新上一个选中活动的结束时间
}
}
return result;
}2. 霍夫曼编码 (Huffman Coding) - 数据压缩的贪心魔法
问题： 为一组字符（及其出现频率）构造最优二进制前缀码，使得编码后的总长度（频率*编码长度之和）最小。
贪心策略： 总是合并当前频率最低的两棵树。
步骤：
为每个字符创建一个叶子节点，节点权重为字符频率。
将所有节点放入一个最小堆（优先队列）。
当堆中节点数 > 1时：
弹出两个频率最小的节点A和B。
创建一个新节点C，其权重 = A.weight + B.weight，C的左孩子 = A，右孩子 = B。
将节点C加入堆中。
最后剩下的节点就是霍夫曼树的根节点。从根到叶子的路径（左0右1）即为字符的编码。
时空复杂度： O(n log n) (时间 - n是字符数), O(n) (空间)
Java实现 (核心建树)：
import java.util.*;
class HuffmanNode implements Comparable<HuffmanNode> {
char data; // 字符（叶子节点有）
int freq; // 频率
HuffmanNode left, right; // 左右孩子
public HuffmanNode(char data, int freq) {
this.data = data;
this.freq = freq;
}
public HuffmanNode(int freq) { // 用于内部节点
this.freq = freq;
this.data = '\0';
}
@Override
public int compareTo(HuffmanNode o) {
return this.freq - o.freq; // 按频率比较，用于优先队列
}
}
public static HuffmanNode buildHuffmanTree(char[] data, int[] freq) {
int n = data.length;
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
// 创建叶子节点，加入优先队列
for (int i = 0; i < n; i++) {
pq.offer(new HuffmanNode(data[i], freq[i]));
}
// 合并节点，直到只剩一个根节点
while (pq.size() > 1) {
// 弹出两个频率最小的节点
HuffmanNode left = pq.poll();
HuffmanNode right = pq.poll();
// 创建新内部节点，频率为两者之和
HuffmanNode parent = new HuffmanNode(left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.offer(parent); // 新节点入队
}
return pq.poll(); // 返回最终的霍夫曼树根节点
}3. 最小生成树算法 (Prim & Kruskal) - 前面图论部分已详细讲解，它们都是贪心算法的经典应用！
第六章：回溯算法 - 试错大师，走不通就回头
核心思想： 一种选优搜索法，按选优条件向前搜索。当探索到某一步，发现原先选择达不到目标或不是最优，就退回一步重新选择（回溯）。通常用递归实现，隐式地使用系统栈。
1. N皇后问题 (N-Queens) - 皇后的和平共处
问题： 在N×N的棋盘上放置N个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一斜线上）。
回溯思路：
按行放置皇后（每行放一个）。
尝试在当前行的每一列放置皇后。
检查放置位置是否安全（不与上方已放置的皇后冲突：同列、左上斜线、右上斜线）。
如果安全，则放置皇后，并递归放置下一行。
如果不安全，则尝试当前行的下一列。
如果当前行所有列都不安全，则回溯到上一行，移动上一行的皇后到下一列，再继续。
当成功放置第N个皇后时，找到一个解。
Java实现 (核心回溯部分)：
public static List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
int[] queens = new int[n]; // queens[row] = col, 表示在第row行的皇后放在第col列
Arrays.fill(queens, -1); // 初始化为-1，表示未放置
backtrack(solutions, queens, 0, n); // 从第0行开始放置
return solutions;
}
private static void backtrack(List<List<String>> solutions, int[] queens, int row, int n) {
// 终止条件：所有行都成功放置了皇后
if (row == n) {
solutions.add(generateBoard(queens, n)); // 生成一个棋盘解
return;
}
// 尝试在当前行row的每一列col放置皇后
for (int col = 0; col < n; col++) {
if (isValid(queens, row, col)) { // 检查(row, col)位置是否安全
queens[row] = col; // 放置皇后
// 递归放置下一行
backtrack(solutions, queens, row + 1, n);
// 回溯：撤销当前行的皇后放置 (queens[row]会在下次循环被覆盖，也可显式置-1)
// queens[row] = -1; // 可选，显式回溯
}
}
}
private static boolean isValid(int[] queens, int row, int col) {
// 检查当前列col是否安全：遍历当前行row上面的所有行
for (int i = 0; i < row; i++) {
// 1. 检查同一列：queens[i] == col
// 2. 检查左上斜线：queens[i] - i == col - row (即行差 == 列差)
// 3. 检查右上斜线：queens[i] + i == col + row (即行差 == -列差)
if (queens[i] == col || queens[i] - i == col - row || queens[i] + i == col + row) {
return false;
}
}
return true;
}
private static List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.'); // 初始化一行都是'.'
row[queens[i]] = 'Q'; // 在皇后位置放'Q'
board.add(new String(row));
}
return board;
}2. 子集问题 (Subsets) - 所有可能的组合
问题： 给定一个不含重复元素的整数数组
nums，返回其所有可能的子集（幂集）。回溯思路： 每个元素都有选或不选两种选择。构建一棵二叉树，左分支代表不选当前元素，右分支代表选当前元素。遍历所有路径即可得到所有子集。
Java实现：
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}
private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
// 每次进入递归，当前tempList就是一个子集，加入结果（包括空集）
result.add(new ArrayList<>(tempList)); // 注意：必须创建新列表副本！
for (int i = start; i < nums.length; i++) {
tempList.add(nums[i]); // 选择当前元素nums[i]
backtrack(result, tempList, nums, i + 1); // 递归处理后面的元素
tempList.remove(tempList.size() - 1); // 回溯：撤销选择（不选nums[i]）
}
}3. 全排列问题 (Permutations) - 所有可能的顺序
问题： 给定一个不含重复元素的整数数组
nums，返回其所有可能的全排列。回溯思路： 每次从未使用的元素中选择一个放到当前位置。使用一个
used数组标记元素是否已被使用。Java实现：
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
return result;
}
private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, boolean[] used) {
// 终止条件：当前排列长度等于原数组长度
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 跳过已使用的元素
used[i] = true; // 标记当前元素已使用
tempList.add(nums[i]); // 将当前元素加入排列
backtrack(result, tempList, nums, used); // 递归生成剩余元素的排列
// 回溯：撤销选择
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}第七章：位运算 - 操控比特的奇技淫巧
位运算直接在二进制位级别操作数据，效率极高。常见操作：
&(AND)：同1为1|(OR)：有1为1^(XOR)：不同为1 (异或)~(NOT)：取反<<(Left Shift)：左移，低位补0 (相当于 *2^n)>>(Signed Right Shift)：带符号右移，高位补符号位 (相当于 /2^n)>>>(Unsigned Right Shift)：无符号右移，高位补0
经典技巧：
判断奇偶：
(n & 1) == 1是奇数，(n & 1) == 0是偶数。交换两数：
a = a ^ b; b = a ^ b; // b = (a ^ b) ^ b = a a = a ^ b; // a = (a ^ b) ^ a = b取最低位的1：
n & (-n)(负数用补码表示，-n = ~n + 1).去掉最低位的1：
n & (n - 1)(常用于计算二进制中1的个数、判断2的幂)。判断是否是2的幂：
n > 0 && (n & (n - 1)) == 0。计算二进制中1的个数 (Brian Kernighan算法)：
int count = 0; while (n != 0) { n = n & (n - 1); // 去掉最低位的1 count++; }异或找唯一： 在一堆成对出现的数字中，找出唯一一个只出现一次的数字（其他都出现两次），将所有数字异或即可。
位图 (Bitmap)： 用整数的每一位来表示一个状态（存在/不存在），极大节省空间。例如用
int[10]可以表示320个状态（32位 * 10）。
Java位运算示例：
int a = 5; // 二进制 0101
int b = 3; // 二进制 0011
int and = a & b; // 0001 -> 1
int or = a | b; // 0111 -> 7
int xor = a ^ b; // 0110 -> 6
int notA = ~a; // 1111...1010 (负数，补码表示)
int leftShift = a << 1; // 1010 -> 10 (相当于5*2)
int rightShift = a >> 1; // 0010 -> 2 (相当于5/2)
int unsignedRightShift = a >>> 1; // 0010 -> 2 (正数>>和>>>一样)第八章：字符串匹配算法 - 大海捞针升级版
1. 朴素匹配 (Brute-Force) - 老实人挨个比
心法： 文本串
T长度为n，模式串P长度为m。将P对准T的开头，逐个字符比较。如果完全匹配则成功。否则将P向右移动一位，重新比较。重复直到找到匹配或P移出T。时空复杂度： O(n*m) (最坏), O(1) (空间)
Java实现：
public static int bruteForce(String text, String pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) { // i是文本串起始比较位置
int j;
for (j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) {
break; // 字符不匹配，跳出内层循环
}
}
if (j == m) { // 内层循环完整走完，说明匹配成功
return i; // 返回匹配起始位置
}
}
return -1; // 未找到
}2. KMP算法 (Knuth-Morris-Pratt) - 利用已知信息跳过不必要的比较
心法： 当发生不匹配时，利用模式串
P自身的特性（部分匹配表next[]），将P向右滑动尽可能远的距离，避免回溯文本指针i。关键： 构建
next[]数组。next[j]表示当P[j]不匹配时，j应该回退到的位置（P[0..j-1]的最长相等真前缀和真后缀的长度）。时空复杂度： O(n + m) (时间), O(m) (空间 - 存储next数组)
Java实现 (简化版，展示核心)：
public static int kmp(String text, String pattern) {
int n = text.length();
int m = pattern.length();
if (m == 0) return 0;
int[] next = computeNext(pattern); // 计算next数组
int i = 0; // 文本指针
int j = 0; // 模式指针
while (i < n) {
if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
if (j == m) { // 匹配成功
return i - j;
}
} else {
j = next[j]; // 利用next数组回退模式指针j
}
}
return -1;
}
private static int[] computeNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
next[0] = -1; // 初始化
int j = 0; // 当前匹配前缀的末尾
int k = -1; // 当前匹配后缀的末尾 (也是next[j]的值)
while (j < m - 1) {
if (k == -1 || pattern.charAt(j) == pattern.charAt(k)) {
j++;
k++;
next[j] = k; // 如果匹配，next[j] = k
} else {
k = next[k]; // 不匹配，k回退到next[k]
}
}
return next;
}3. BM算法 (Boyer-Moore) - 从后往前匹配，坏字符和好后缀规则
心法： 从模式串
P的末尾开始向前匹配文本串T。利用坏字符规则 (Bad Character Heuristic) 和好后缀规则 (Good Suffix Heuristic) 计算模式串可以向右滑动的最远距离。效率： 实际应用中通常比KMP更快，尤其当模式串较长、字符集较大时。
实现较复杂： 需要构建
badChar[]数组和goodSuffix数组。
4. Rabin-Karp算法 - 基于哈希的匹配
心法： 计算模式串
P的哈希值。计算文本串T中所有长度为m的子串的哈希值。如果某个子串的哈希值与P的哈希值匹配，再逐个字符比较确认（避免哈希冲突）。使用滚动哈希技术高效计算子串哈希值（例如多项式哈希）。时空复杂度： 平均 O(n + m)，最坏 O(n*m) (如果哈希冲突频繁且每次都需验证)。O(1)空间（忽略哈希计算存储）。
适用于： 多模式匹配、近似匹配、检测重复子串。
第九章：其他重要算法与概念
拓扑排序 (Topological Sorting)： 用于有向无环图 (DAG)。将顶点排成线性序列，使得对于图中任意有向边
u->v，u在序列中都在v前面。常用Kahn算法 (基于入度) 或DFS实现。并查集 (Union-Find / Disjoint-Set)： 高效管理元素分组（合并集合、查询元素所属集合）。支持
find（查找根节点，带路径压缩）和union（合并两棵树，带按秩合并）。时间复杂度接近O(α(n))（阿克曼函数反函数，几乎常数时间）。用于Kruskal算法、检测连通性、动态连通性问题。布隆过滤器 (Bloom Filter)： 一种空间效率极高的概率型数据结构。用于判断一个元素是否一定不在集合中或可能在集合中。存在假阳性（判断存在但实际不存在），但没有假阴性（判断不存在则一定不存在）。核心是多个哈希函数和一个位数组。
LRU缓存 (Least Recently Used Cache)： 一种缓存淘汰策略。当缓存空间不足时，淘汰最久未使用的数据。通常用哈希表 + 双向链表实现。哈希表保证O(1)查找，双向链表维护访问顺序（最近访问的移到链表头，淘汰链表尾）。
一致性哈希 (Consistent Hashing)： 解决分布式缓存/负载均衡中，当节点增删时数据大量迁移的问题。将数据和节点都映射到一个环形哈希空间。数据顺时针找到的第一个节点即为存储位置。节点增删只影响相邻节点的少量数据。
跳表 (Skip List)： 一种可以替代平衡树（如红黑树）的数据结构。它通过添加多级索引，使得查找、插入、删除的平均时间复杂度达到O(log n)，且实现比平衡树简单。Redis的有序集合使用跳表实现。
B树/B+树 (B-Tree / B+Tree)： 多路平衡查找树，专为磁盘或其他直接存取辅助存储设备设计。能有效减少磁盘I/O次数。广泛应用于数据库和文件系统的索引结构。B+树是B树的变种，所有数据都存储在叶子节点，非叶子节点只存储键，查询更稳定。
红黑树 (Red-Black Tree)： 一种自平衡二叉查找树。通过着色和旋转规则保证树大致平衡，确保查找、插入、删除的最坏时间复杂度为O(log n)。Java的
TreeMap、TreeSet，C++ STL的map、set等底层实现。
总结：
哇！这场算法世界的环球旅行真是精彩纷呈！🎉 我们从基础的排序查找出发，穿越了图论的丛林，领略了动态规划的智慧，体验了贪心的果断和回溯的坚韧，还探索了位运算的奇妙和字符串匹配的精密，最后还瞥见了那些支撑现代计算的重要基石。
记住：
理解思想比死记代码更重要！ 算法的核心是解决问题的思路和策略。
复杂度分析是灵魂！ 时刻问自己：这个算法快不快？占多少地方？
实践！实践！再实践！ 看懂和能写出来、能灵活运用是两码事。去LeetCode、牛客网等平台刷题吧！
没有银弹！ 不同算法适用于不同场景。选择合适的“工具”解决特定的“问题”。
持续学习！ 算法世界博大精深，新的思想和优化不断涌现。
评论区