算法 - 召田最帅boy

NC3 链表中环的入口结点

本文介绍了在长度不超过 10000 的单链表中，若存在环如何在 O(1) 额外空间、O(n) 时间内找出环的入口结点。题目输入分为链表非环段和环段，后台会据此构造有环或无环链表。解决思路采用快慢指针：先用两指针遍历检测环并得到相遇节点；若不存在环返回 null；若存在环，将一指针重新指向表头，随后两指针同步移动，首次相遇即为环入口。文中给出 Java 实现代码，展示了 `hasCycle` 检测环及 `EntryNodeOfLoop` 求入口的完整过程。

2022-07-24 12:39:58 阅读

NC22 合并两个有序的数组

本文介绍了 NC22 “合并两个有序的数组” 题目：给定已排序的整数数组 A（长度 m）和 B（长度 n），A 预留 m+n 空间，要求在不返回新数组的情况下将 B 合并到 A 中，使 A 仍保持升序。说明了输入输出示例、约束条件（0≤n,m≤100，元素绝对值≤100）以及实现思路：使用双指针遍历 A、B，将较小元素依次写入临时数组 sorted，遍历结束后将 sorted 内容拷贝回 A。文中提供了完整的 Java 实现代码。

2022-07-23 23:17:36 阅读

NC4 判断链表中是否有环

本文介绍了判断单向链表是否存在环的问题，要求在 O(n) 时间、O(1) 空间内完成。给出题目背景、输入形式（链表节点值及环入口标记）以及示例。核心解法采用快慢指针（Floyd 判圈算法）：初始化快慢指针均指向头结点，快指针每次移动两步、慢指针每次移动一步；若两指针相遇则链表存在环，若快指针先到达 null 则无环。代码实现简洁，先处理空链表情况，循环条件确保安全访问，最终返回布尔结果。该方法满足题目对时间 O(n) 与空间 O(1) 的要求。

2022-07-23 08:20:44 阅读

盛水最多的容器

本文介绍了“盛水最多的容器”算法题，要求在给定高度数组中选取两条垂直线与x轴形成容器，求最大蓄水量。若数组长度小于2返回0，容量不超int范围。提供了示例及双指针解法：左、右指针从两端开始，计算面积后移动较短的一侧，以遍历所有可能并更新最大值。代码实现简洁高效，时间复杂度O(n)。

2025-09-09 11:51:29 阅读

分糖果问题

本题要求给一组孩子的得分数组分配糖果，满足每人至少一颗，得分更高的相邻孩子糖果数必须更多（得分相同则无约束）。在 n≤100000、时间 O(n)、空间 O(n) 的限制下，采用双向遍历的动态规划：先初始化全部为 1，左至右若当前得分大于前一位则糖果数加 1；再右至左若当前得分大于后一位且糖果数不够则设为后一位 +1。最后累计所有糖果即为最少总数。示例 [1,1,2] → 4， [1,1,1] → 3。代码实现即上述两遍遍历并求和。

2025-09-09 11:40:26 阅读

编辑距离(一)

本文介绍了编辑距离问题：给定两个仅含小写字母的字符串（长度≤1000），求将第一个字符串转化为第二个字符串的最少插入、删除或替换操作数。通过动态规划建立 dp[i][j] 表示前 i、j 个字符的最小操作数，利用仅保留两行的滚动数组将空间降至 O(|str2|)。代码实现了上述思路并给出示例验证。

2025-09-09 11:25:19 阅读

NC69 链表中倒数最后k个结点

本文介绍了在单链表中寻找倒数第 k 个节点的算法。给定长度 n 的链表及整数 k，若链表长度小于 k 返回空链表；要求时间 O(n)，空间 O(1)。核心思路是使用快慢指针：快指针先前进 k 步，随后快慢指针同步前进，快指针到达末尾时慢指针即指向倒数第 k 个节点。代码实现展示了该过程，并通过示例说明返回结果。

2023-04-04 10:31:58 阅读

NC21 链表内指定区间反转

本文介绍了链表区间反转的问题：在单向链表中将第 m 到第 n 个节点的顺序逆转，要求时间 O(n)。题目给出约束条件、示例以及进阶目标 O(1) 空间。文中提供的 Java 实现思路是遍历链表两次，利用栈先将目标区间的值入栈，再出栈写回，从而完成反转，空间复杂度为 O(n)。该解法虽满足时间要求，但未实现进阶的常数空间优化。

2023-04-03 10:39:51 阅读

NC26 括号生成

本文介绍了生成 n 对括号合法组合的算法。给定 0≤n≤10，要求空间 O(n)、时间 O(2ⁿ)。采用递归回溯：从空串开始，分别尝试加入左括号（左括号数未达 n）和右括号（右括号数小于左括号数），直到左右括号均用完即得到一个合法序列。代码实现中通过 `recursion(left, right, temp, res, n)` 完成遍历，并将满足条件的字符串加入结果列表，最终返回所有合法组合。

2022-10-28 16:52:44 阅读

NC93 设计LRU缓存结构

本文介绍了 NowCoder 上的 LRU 缓存设计题目，包括需求、示例及 Java 实现。缓存容量在构造时确定，需支持 O(1) 时间的 get 与 set 操作；get 返回键对应的值或 -1，set 在键已存在时更新并提升为最近使用，键不存在时插入，超出容量时淘汰最久未使用的键。实现思路是使用 HashMap 存储键到双向链表节点的映射，链表维护使用顺序，头部为最近使用，尾部为最久未使用。代码中实现了节点类、构造函数、get、set、插入头部、移动到头部、删除尾部等方法，保证所有操作均为常数时间。

2022-09-09 09:05:09 阅读

NC57 反转数字

本文介绍了“NC57 反转数字”题目：给定32位有符号整数，仅翻转其数字部分，符号保持不变，若结果超出[-2³¹,2³¹‑1]范围返回0，且不允许使用64位整数。提供了示例输入输出，并给出Java实现思路：遍历取余构建反转数，使用long临时存储防止溢出，最后判断是否在int范围内返回结果，否则返回0。

2022-09-07 18:23:04 阅读

NC35 编辑距离(二)

本文介绍了编辑距离的变形问题：在给定插入、删除、替换三种操作代价的前提下，求将字符串 str1 编辑为 str2 的最小总费用。数据规模可达 5000 字符，要求时间复杂度 O(n²) 、空间复杂度 O(n)。文章先给出题目描述、示例及约束，然后给出基于动态规划的实现思路：构造 dp[i][j] 表示将 str1 前 i 字符编辑成 str2 前 j 字符的最小代价，边界由插入和删除费用决定，转移方程在字符相等时继承左上角值，否则取插入、删除、替换三者的最小值并加对应费用。最后返回 dp[len1][len2] 即为答案。代码使用 Java 实现，完整展示了初始化、状态转移及结果返回。

2022-09-05 16:43:03 阅读