NowCoder - 召田最帅boy

NC38 螺旋矩阵

给定 m×n 矩阵，要求按螺旋顺序输出所有元素，时间、空间复杂度均为 O(mn)。文章先说明输入范围与示例，然后给出 Java 实现：通过四个边界变量 left、right、up、down 循环遍历上、右、下、左四条边，并在每次遍历后收缩相应边界，直至边界重合，最终返回螺旋顺序的列表。

2022-09-04 12:37:38 阅读

NC20 数字字符串转化成IP地址

该题要求将仅包含数字的字符串（长度0~12）切分为四段，每段取值在0~255且不能出现除单个0外的前导零，输出所有可能的IP地址形式。文章给出示例“25525522135”对应“255.255.22.135”“255.255.221.35”。解法采用深度优先搜索+回溯：用`path`记录已选段，递归遍历切割点，若段合法（长度≤3、数值≤255且不含非法前导零）则加入`path`继续搜索；当恰好四段且遍历完字符串时，将`path`拼成“x.x.x.x”加入结果。整体时间、空间复杂度均为O(n!)，代码实现为Java类`Solution`。

2022-08-18 19:19:52 阅读

BM51 数组中出现次数超过一半的数字

本文介绍了“数组中出现次数超过一半的数字”问题：给定长度 n 的数组，必有一个元素出现次数 > n/2，要求在 O(n) 时间、O(1) 额外空间内找出该元素。文章给出一种基于哈希表的实现思路：遍历数组，用 map 记录每个数的出现次数，若某个数的计数超过数组长度的一半即返回。代码展示了具体的 Java 实现，并通过示例说明了输入输出结果。

2022-08-13 16:47:45 阅读

NC100 把字符串转换成整数(atoi)

本文介绍了实现字符串转整数（atoi）的函数 StrToInt，要求在不使用库函数的前提下完成转换。算法步骤包括：①去除首尾空格；②判断并记录符号位；③从首个数字字符起连续读取数字，遇到非数字立即停止；④在累加过程中检测是否会越界，若超出 32 位有符号整数范围则返回 INT_MAX 或 INT_MIN；⑤返回结果时根据符号恢复正负。代码实现采用统一负数累加的技巧，利用 Integer.MIN_VALUE 的除余值进行溢出判断，确保在整数范围内返回正确值。示例展示了普通、含空格、含多余字符、无有效数字以及超出范围的情况。

2022-08-06 12:33:41 阅读

NC142 最长重复子串

文章介绍了“最长重复子串”问题：给定仅含小写字母的字符串（长度≤10³），求由两个相同子串连续拼接而成的最长子串长度，若不存在返回0。示例说明“ababc”返回4（子串“abab”），而“abcab”返回0。要求在空间O(1)、时间O(n²)内实现。提供的 Java 解法先枚举可能的子串长度，从最大可能值递减检查，每次在所有起始位置比较对应字符是否相等，若匹配即返回长度；若遍历完仍未找到则返回0。代码包含主函数solve和辅助检查函数check，整体思路简洁直观，满足题目复杂度要求。

2022-07-21 11:25:34 阅读

NC37 合并区间

给定一组区间，需合并所有重叠区间并按起点升序返回。约束 n≤2×10⁵，区间值 0≤val≤2×10⁵，要求时间 O(nlogn)、空间 O(n)。思路：先按区间起点（起点相同则按终点）排序，然后遍历合并——若当前区间起点大于已合并区间的终点则直接加入，否则更新末尾区间的终点为两者最大值。代码实现采用 Java，利用 `ArrayList<Interval>` 存储结果并在遍历中维护合并逻辑。

2022-07-20 12:02:19 阅读

NC41 最长无重复子数组

本题要求在长度不超过10⁵的整数数组中求最长的连续子数组，使其内部元素全部唯一。采用滑动窗口配合哈希表记录窗口内各元素出现次数：右指针逐步扩展窗口并更新计数，若出现重复则左指针收缩窗口直至所有计数≤1。每次窗口合法时更新最大长度。时间复杂度O(n)，空间复杂度O(m)（m 为窗口内不同元素数），代码实现简洁高效。

2022-07-19 22:06:36 阅读

NC19 连续子数组的最大和

本文介绍了 NC19 “连续子数组的最大和”问题：在长度为 n （1≤n≤2×10⁵）的整数数组中，求任意非空连续子数组的最大和。要求时间 O(n)，空间 O(1)。核心思路是 Kadane 动态规划：遍历数组时把当前元素与前缀和相加，仅在前缀和为正时保留，否则重新开始；同时维护全局最大值。代码实现仅修改原数组或使用额外变量即可在 O(n) 时间、O(1) 空间内得到答案。示例说明了正负数混合及单元素情况的正确性。

2022-07-18 13:14:35 阅读

NC50 链表中的节点每k个一组翻转

文章介绍了链表节点每 k 个一组翻转的问题，要求在 O(1) 额外空间和 O(n) 时间内完成。给出题目描述、约束条件和示例，随后提供 Java 实现。核心思路是先遍历 k 步定位段尾，若不足 k 则保持原样；否则在该段内部使用前驱指针逐个翻转，并递归处理后续段，最终返回翻转后的链表头节点。

2022-07-18 09:47:33 阅读

NC68 跳台阶

本文介绍了 NC68 “跳台阶”题目：一只青蛙每次可跳 1 级或 2 级，求跳上 n 级台阶的不同跳法数（顺序不同计为不同），n 范围 1≤n≤40。要求时间复杂度 O(n)、空间复杂度 O(1)。示例说明 n=2 时有两种方案，n=7 时答案为 21。提供的 Java 解法使用动态规划，利用 dp[i]=dp[i‑1]+dp[i‑2] 的斐波那契递推，只保留必要的前两项即可实现 O(1) 额外空间。

2022-07-17 16:50:49 阅读

NC76 用两个栈实现队列

本文介绍了利用两个栈实现队列的算法，满足存储 n 个元素空间复杂度 O(n)、插入（push）和删除（pop）时间复杂度均为 O(1) 的要求。核心思路是：所有入队操作统一压入 stack1；出队时若 stack2 为空，则将 stack1 中的元素全部弹出并压入 stack2，实现顺序逆转，从而在 stack2 顶部即可按 FIFO 顺序弹出元素。代码示例用 Java 实现了 push 与 pop 两个方法，并通过示例验证了正确性。

2022-07-16 18:35:04 阅读

NC33 合并两个排序的链表

本文介绍了合并两个递增链表的算法，要求时间复杂度 O(n)、空间复杂度 O(1)。通过遍历两链表比较节点值，将较小节点接入新链表，并维护头尾指针；当任一链表耗尽后，直接链接剩余链表。代码实现了空链表处理、首次插入初始化以及后续节点拼接，最终返回合并后的有序链表。

2022-07-14 15:32:58 阅读