NowCoder - 召田最帅boy

NC3 链表中环的入口结点

本文介绍了在长度不超过 10000 的单链表中检测环并找出环入口节点的方法。要求空间 O(1)、时间 O(n)。通过快慢指针判断是否存在环，若相遇则说明有环；随后让一个指针回到链表头，与相遇点同步前进，首次相遇即为环入口。代码实现包括 `hasCycle` 用于返回相遇节点，`EntryNodeOfLoop` 返回环入口，若无环返回 null。示例演示了有环、无环以及单节点环的情况。

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

NC22 合并两个有序的数组

本文介绍了在 NowCoder 上的 NC22 题目——将有序整数数组 B 合并到已预留足够空间的有序数组 A 中，使 A 成为整体升序。要求在 A 的前 m 位已有序，B 的前 n 位已有序，且不返回新数组，只需在原 A 中完成合并。文章给出示例说明输入输出，并提供了 Java 实现：使用双指针遍历 A、B，比较取较小元素填入新建的临时数组 sorted，遍历结束后将 sorted 内容拷贝回 A，实现了在 O(m+n) 时间、O(m+n) 额外空间下的合并。

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

NC4 判断链表中是否有环

文章介绍了判断单链表是否存在环的题目，要求空间复杂度 O(1)、时间复杂度 O(n)。输入包括链表节点值和环入口标记，示例说明了有环和无环两种情况。核心解法采用快慢指针：slow 每次走一步，fast 每次走两步，若两指针相遇则链表有环，否则遍历至末尾即无环。代码首先处理空链表，随后在 fast 与 fast.next 不为空的循环中更新指针并判断相等，最终返回相应的布尔结果。

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

盛水最多的容器

给定长度为 n 的数组 height，数组每个元素表示坐标轴上对应点的高度，要求在任意两点之间形成不倾斜的容器，计算该容器能够容纳的最大水量。若 n<2 则返回 0，且结果保证不超过 2³¹‑1。解法采用双指针：左指针指向数组首部，右指针指向末尾，计算当前宽度 (right‑left) 乘以两端较小高度得到容量，并用 max 维护最大值。随后移动较短边的指针，以期找到更高的边可能产生更大容量，直至左右指针相遇。时间复杂度 O(n)，空间复杂度 O(1)。

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

分糖果问题

给定孩子们的得分数组，要求每人至少分得一颗糖，且相邻得分更高的孩子必须分得更多糖。题目要求在 O(n) 时间、O(n) 空间内求最少糖果总数。解法采用两遍遍历的动态规划：首次从左到右若当前得分高于左侧则糖数加一；第二次从右到左若当前得分高于右侧且糖数不够则更新为右侧糖数加一。最终累加所有糖数即为答案。代码实现基于上述思路，时间复杂度 O(n)，空间复杂度 O(n)。

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

编辑距离(一)

本文介绍了求两个仅含小写字母的字符串之间最少编辑操作数的问题，操作包括插入、删除和修改。给出示例说明计算过程，并提供基于动态规划的 O(n·m) 解法。实现中使用两行滚动数组 dp，分别记录当前行和前一行的最优值，通过字符相等与否分别处理转移，最终返回 dp[str1.length % 2][str2.length] 即编辑距离。

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

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

本文介绍了在单链表中查找倒数第k个节点的题目及实现。要求时间 O(n)，进阶空间 O(1)。采用快慢指针法：快指针先走 k 步，随后与慢指针同步前进，快指针到达链表末尾时慢指针即指向倒数第k个节点；若链表长度不足 k 则返回空链表。文中给出完整的 Java 代码实现。

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

NC21 链表内指定区间反转

本文介绍了链表区间反转问题：在长度≤1000的单链表中，将第 m 到第 n 个节点的子序列逆序，要求时间O(n)。示例 1→2→3→4→5，m=2、n=4，结果为1→4→3→2→5。文章给出一种实现思路：遍历链表，将目标区间的节点值压入栈；再次遍历时弹栈并覆盖原节点值，从而完成逆序。该代码时间复杂度为O(n)，但使用了栈导致空间复杂度为O(n)，未满足进阶要求的O(1)空间。

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

NC26 括号生成

本文介绍了“括号生成”问题：给定 n 对括号，生成所有合法的组合，如 n=3 时的五种排列。要求空间 O(n)、时间 O(2^n)，n 的取值范围 0≤n≤10。提供了 Java 解法，使用递归回溯遍历，维护已使用的左、右括号数；当左括号未用完时继续放“(”，当右括号少于左括号且未用完时放“)”。当左右括号均用完即得到一个合法组合并加入结果列表。代码实现简洁，符合题目复杂度要求。

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

NC93 设计LRU缓存结构

本文介绍了在容量固定的情况下实现 O(1) 时间复杂度的 LRU（最近最少使用）缓存。题目要求提供构造函数、`get(key)` 与 `set(key,value)` 两个接口，并在缓存超出容量时淘汰最久未使用的键值对。核心实现思路是结合哈希表快速定位节点和双向链表维护使用顺序：每次 `get` 或 `set` 都将对应节点移动到链表头部；插入新键时若容量已满则删除链表尾部节点。代码给出 Java 实现，包括节点类、插入、移动、删除等辅助方法，完整满足题目 O(1) 的性能要求。

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

NC57 反转数字

题目要求在不使用 64 位整数的前提下，对 32 位有符号整数的数字部分进行翻转，保留符号位，若翻转后超出 \[-2³¹, 2³¹‑1\] 范围则返回 0。解法思路是循环取出原数的最低位（x % 10），累乘 10 并加到结果 res 中，同时将 x 除以 10。为判断溢出，使用 long 类型暂存结果，最后检查 `(int)res == res`，若相等返回转化后的 int，否则返回 0。示例包括正数、负数、含尾零以及溢出情况。

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

NC35 编辑距离(二)

本文介绍了编辑距离的变形问题：在给定插入、删除和替换三个操作代价的前提下，求将字符串 str1 编辑为 str2 的最小总代价。要求时间复杂度为 O(n²)，空间复杂度为 O(n)。文章通过动态规划构建二维数组 dp[i][j]，表示将 str1 前 i 个字符转换为 str2 前 j 个字符的最小代价，初始化第一行和第一列分别对应纯插入或删除的成本，随后递推考虑字符相等、插入、删除和替换四种情况，最终返回 dp[len1][len2]。提供了完整的 Java 实现代码示例，并给出两组示例输入输出验证算法正确性。

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