算法 - 召田最帅boy

NC38 螺旋矩阵

本题要求对任意 m × n 矩阵按顺时针螺旋顺序输出所有元素，数据规模 0 ≤ m,n ≤ 10，元素绝对值 ≤ 100，时间、空间均需 O(mn)。解法采用四个边界指针 left、right、up、down，循环在边界未交叉时依次遍历上边从左至右、右边从上至下、下边从右至左、左边从下至上，并在每次遍历后收缩相应边界，直至完成。代码实现简洁，先排除空矩阵，随后在 while 循环中按上述顺序加入结果列表，满足题目要求。

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

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

该题要求将仅含数字的字符串切分为四段，使每段在 0~255 范围内，形成合法 IP 地址并返回所有可能组合。长度限制为 0–12，需采用深度优先搜索+回溯遍历所有切割点，剪枝条件包括段长度不超过 3、首位为 0 时只能为单个 0、数值不超过 255。代码使用 `process` 递归遍历，`path` 保存当前分段，满足四段且遍历完字符串时加入结果；`isValid` 实现上述合法性检查。整体空间、时间复杂度均为 O(n!)，符合题目要求。

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

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

文章介绍了“数组中出现次数超过一半的数字”这一题目：给定长度不超过 50000、元素值在 1~10000 的数组，必存在出现次数超过数组一半的元素，要求在 O(n) 时间、O(1) 额外空间内找出该元素。文中提供的实现采用哈希表统计每个数字的出现次数，在遍历过程中一旦发现某数计数超过数组长度的一半即返回。示例包括 `[1,2,3,2,2,2,5,4,2]` → 2、`[3,3,3,3,2,2,2]` → 3、`[1]` → 1。

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

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

实现字符串转整数（atoi）功能，要求自行编写 `StrToInt`，不使用库函数。算法步骤：①去除首尾空格；②识别首个非空字符的正负号，默认正；③从符号后连续读取数字构成有效整数，遇非数字即停止；④若无有效数字返回 0；⑤结果超出 32 位有符号整数范围时截断到 `[-2^31, 2^31‑1]`。代码采用先去除空格、判断首字符合法性、记录数字起始位置，并统一以负数形式累加防止溢出，最后根据符号返回相应正负值。示例展示了普通、带空格、含多余字符、无数字及溢出等情况的处理。

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

NC142 最长重复子串

本文介绍了“最长重复子串”问题：判断字符串中由两个相同子串相连的最长子串长度，若不存在返回0。字符串长度≤10^3，仅含小写字母。给出 O(n^2) 时间、O(1) 额外空间的解法：从可能的最大子串长度开始枚举，检查相邻两段是否相等，若匹配即返回长度。代码实现包含主函数 solve 与辅助函数 check，遍历并在首次发现符合条件的子串时立即返回结果。

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

NC37 合并区间

文章介绍了“合并区间”题目：给定最多 2×10⁵ 个区间，要求合并所有重叠区间并按起点升序返回，时间复杂度 O(nlogn)、空间复杂度 O(n)。示例展示了相邻区间合并的效果。提供的 Java 解法先对区间按 start、end 排序，然后遍历列表，若当前区间与结果末尾不重叠则直接加入，重叠时更新末尾区间的结束值，实现了高效的合并逻辑并处理空集等特殊情况。

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

NC41 最长无重复子数组

本文给出“最长无重复子数组”问题的描述与示例，要求在长度≤10⁵的数组中返回连续子数组的最大长度，使其中元素全部不重复。提供的 Java 解法采用滑动窗口结合哈希表记录窗口内元素出现次数：右指针扩展窗口并更新计数，若出现重复则左指针收缩窗口直至所有计数≤1，期间维护最大长度。代码时间复杂度 O(n)，空间复杂度 O(m)（m 为不同元素数），能够高效求解该问题。

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

NC19 连续子数组的最大和

求数组任意子数组（长度≥1）的最大和，要求时间 O(n)，空间 O(1)。利用 Kadane 思路：遍历时累计当前子数组和，若前缀和为负则重置为当前元素；同时维护全局最大值。代码示例中通过 `array[i] += Math.max(0, array[i‑1])` 更新累计和，`res` 保存最大和，最终返回 `res`。该算法满足题目约束，适用于正负数混合的任意整数数组。

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

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

本文介绍了“链表每k个节点翻转”问题：在不修改节点值、空间O(1)、时间O(n)的限制下，将链表按k为一组逆序，若不足k则保持原序。给出示例及边界情况。核心思路是先检查当前段是否至少有k个节点，若不足直接返回；否则使用迭代逆转当前k段节点，逆转后递归处理后续子链表，并将原段首节点连接到递归返回的子链表头。代码实现简洁，利用指针pre、cur、tail完成局部翻转并递归链接。

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

NC68 跳台阶

该题要求计算青蛙爬上 n 级台阶的跳法数，青蛙每次可跳 1 级或 2 级，跳法顺序不同视为不同。n 的取值在 1‒40，要求时间 O(n)、空间 O(1)。实际上跳法数等同斐波那契数列，第 n 项可由 dp[i]=dp[i‑1]+dp[i‑2] 递推得到。示例：n=2 时答案 2，n=7 时答案 21。文中给出一种基于数组的实现思路，亦可用常数空间的滚动变量进一步优化。

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

NC76 用两个栈实现队列

本文介绍了利用两个栈实现队列的算法要求：在 O(n) 空间内完成 n 次入队（push）和 n 次出队（pop），且每次操作时间复杂度均为 O(1)。通过在 stack1 中正常入栈，出队时若 stack2 为空则将 stack1 中全部元素倒入 stack2，实现先进先出的顺序。文章提供了示例说明操作过程，并给出 Java 实现代码，展示了 push 方法向 stack1 添加元素，pop 方法在必要时转移元素后从 stack2 弹出，实现队列的基本功能。

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

NC33 合并两个排序的链表

本文介绍了合并两个递增链表的算法，要求时间复杂度 O(n)、空间复杂度 O(1)。给出题目描述、示例及边界情况（空链表），并提供 Java 实现。核心思路是使用两个指针遍历两链表，比较当前节点值，将较小者接到结果链表尾部，并更新相应指针；首次插入时初始化头尾指针，循环结束后将剩余非空链表直接链接到结果尾部。代码实现简洁，满足题目约束。

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