算法 - 召田最帅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 实现。给定一个由空格分隔的字符串，要求按单词出现顺序垂直排列并返回字符串列表，列末尾不能有多余空格。实现思路：先用 `split(" ")` 将句子拆分为单词数组，遍历求出最长单词长度 `maxLength`；随后逐行（从第 0 行到 `maxLength‑1`）构建 `StringBuilder`，若当前单词在该行有字符则追加，否则追加空格。完成一行后从右向左寻找最后一个非空格字符，截取子串去除尾随空格后加入结果列表。代码示例包括 `printVertically` 方法及主函数演示。

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

选择排序

选择排序把数组划分为已排序和未排序两部分，每轮在未排序区找最小元素并与当前目标位置交换。代码实现中用两层循环，外层 i 为目标索引，内层遍历寻找最小索引 s，最后一次交换即可，已在实现中完成交换次数的优化。时间复杂度与冒泡排序同为 O(n²)，但因交换次数少通常更快；若序列已有序度高，冒泡可能更优。选择排序是不稳定的——示例用扑克牌对象演示，同样的键值在不同规则下会改变相对顺序，而冒泡排序保持相对顺序，属于稳定算法。

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

冒泡排序

冒泡排序通过逐对比较相邻元素并交换，将最大值“冒”到数组末端，重复多轮直至有序。实现思路是外层循环控制轮次，内层比较并在需要时交换，使用布尔变量检测本轮是否有交换以提前结束。代码示例给出简单版和优化版：优化版记录每轮最后一次交换位置，将其作为下一轮的比较上限，当该值为0时直接退出。两版均演示了对数组 `{5,9,7,4,1,3,2,8}` 的排序过程，最终得到有序序列 `[1,2,3,4,5,7,8,9]`。

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

二分查找

二分查找是一种在有序数组中通过不断取中间元素并与目标值比较、收缩左右边界实现的高效搜索算法。基本思路是设定左、右边界 L、R，循环计算中点 M=(L+R)/2（或使用 M=(L+R)>>>1 防止溢出），比较 A[M] 与目标 T，若相等返回索引，若 A[M]<T 则 L=M+1，若 A[M]>T 则 R=M-1，直至 L>R 表示未找到。文中给出 Java 实现并演示排序后查找示例，同时说明了 (L+R)/2 在极端情况下可能导致整数溢出，推荐使用位右移或分拆加法的写法来避免。

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