算法 - 召田最帅boy

322. 零钱兑换

本文介绍了 LeetCode 322 “零钱兑换”问题的求解思路。给定硬币面额数组和目标金额，要求返回凑成该金额的最少硬币数，若不可达返回 -1。代码实现采用自底向上的动态规划：用一个长度为 amount+1 的数组 target 保存每个子金额的最优硬币数，初始值设为 amount+1（视为不可达），target[0]=0。遍历所有金额 i，针对每枚硬币 coin 若 i-coin≥0，则更新 target[i]=min(target[i], target[i-coin]+1)。最终若 target[amount]仍为初始值则返回 -1，否则返回其值。示例演示了不同输入的输出结果。

2021-11-15 14:30:14 阅读

1324.竖直打印单词

本文介绍了 LeetCode 1324 “竖直打印单词”的实现思路与 Java 代码。先将输入字符串按空格分割为单词数组，遍历求出最长单词长度；随后按行（从第 0 行到最长长度‑1）逐列构造字符序列，对每个单词若当前行索引在其长度范围内则取对应字符，否则填充空格。构造完一行后，从右向左删除末尾的连续空格，确保输出不含尾随空格。最终将每行字符串加入列表返回。代码示例展示了对不同输入的正确输出。

2021-11-15 14:01:38 阅读

选择排序

选择排序把数组划分为已排序和未排序两部分，每轮在未排序区间寻找最小元素并与当前目标位置交换，直至全部有序。实现时用外层循环 i 标记目标索引，内层遍历找最小索引 s，最后一次性交换，降低交换次数。时间复杂度为 O(n²)，与冒泡排序相同，但因交换次数更少通常更快；在高有序度数据上冒泡稍优。选择排序是不稳定的，示例代码通过扑克牌对象演示，同一数值的不同花色在多轮排序后相对位置会改变，而冒泡排序保持相对顺序。代码示例提供完整的 Java 实现及运行结果。

2021-10-13 22:18:37 阅读

冒泡排序

冒泡排序通过重复比较相邻元素并在逆序时交换，使最大（或最小）元素逐轮“冒泡”到数组末端，直至整体有序。基本实现包括外层循环控制轮次，内层循环比较相邻元素并记录是否发生交换，以便在无交换时提前结束。文中给出 Java 简单版代码示例，指出循环变量错误并演示每轮结果输出。随后介绍优化思路：记录本轮最后一次交换的位置作为下一轮比较上限，若本轮未发生交换则直接终止。优化版代码利用该“last”索引显著减少不必要比较，展示了逐轮排序后的数组变化。

2021-10-13 11:48:22 阅读

二分查找

二分查找是一种在有序数组中定位目标值的算法。通过维护左、右边界 L、R，取中间索引 M = (L+R)/2（或使用无符号右移避免溢出），比较 A[M] 与目标 T：相等则返回索引；小于 T 时左边界设为 M+1；大于 T 时右边界设为 M-1，循环直至 L>R 表示未找到。示例代码先对数组排序，再在 while 循环中实现上述逻辑，返回找到的下标或 -1。文中指出当 R 接近 Integer.MAX_VALUE 时 (L+R)/2 可能溢出，提供两种改进：使用 L/2+R/2 的等价写法或位运算 M = (L+R) >>> 1，以确保安全且提升效率。

2021-10-11 23:01:38 阅读