NowCoder - 召田最帅boy

NC3 链表中环的入口结点

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

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

NC22 合并两个有序的数组

本文介绍了 NowCoder 题目 “NC22 合并两个有序的数组”。要求在已预留空间的有序数组 A 中直接合并另一个有序数组 B，使 A 成为整体升序。数据规模为 0≤n,m≤100，且 A 的前 m 位、B 的前 n 位均已排序。示例演示了 A 与 B 不同大小及元素重合的合并结果。提供的 Java 参考实现使用双指针遍历两数组，将较小元素依次写入新建的临时数组 sorted，随后将结果拷贝回 A，实现了在 O(m+n) 时间和 O(m+n) 额外空间下的合并。

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

NC4 判断链表中是否有环

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

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

盛水最多的容器

给定长度为 n 的数组 height，height[i] 表示第 i 点的高度，要求选取两点与 x 轴形成容器，求其能容纳的最大水量。若 n<2 返回 0，结果不超 int 范围。使用双指针分别指向数组左右，两端计算容量 min(height[left],height[right]) × (right‑left) 并更新最大值；随后移动较短边的指针，直至指针相遇即得到最优解。代码实现时间复杂度 O(n)，空间复杂度 O(1)。

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 阅读

编辑距离(一)

本文介绍了编辑距离问题：给定两个仅含小写字母的字符串 str1、str2（长度 ≤ 1000），要求计算将 str1 转换为 str2 的最少操作数，操作包括插入、删除和修改字符。文中给出三组示例，说明不同情形下的最优步骤及返回值。随后提供基于动态规划的 Java 实现，采用滚动数组仅保留两行状态，时间复杂度 O(m·n)，空间复杂度 O(n)。代码通过比较字符相等与否，分别处理不需操作、替换、插入或删除的转移，最终返回 dp[str1.length % 2][str2.length] 即为编辑距离。

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 链表内指定区间反转

本文介绍了链表区间反转问题：在长度≤1000的单向链表中，将第 m 到第 n 个节点的顺序逆转，要求时间复杂度O(n)。题目给出示例及输入输出格式，并提供了一个基于栈的实现方案——遍历链表将目标区间的节点值入栈，再次遍历弹出栈中值覆盖原节点，实现反转。虽满足时间要求，但使用了额外的栈空间，未达到进阶目标的O(1)空间复杂度。

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 阅读