算法 - 召田最帅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 的数组中寻找出现次数超过一半的数字的问题，要求时间复杂度 O(n) 且空间复杂度 O(1)。给出示例输入输出，并提供了一段 Java 代码实现。该实现采用哈希表统计每个元素的出现次数，在遍历过程中一旦某个数字的计数超过 n/2 即返回该数字，满足线性时间但使用了 O(n) 的额外空间。全文重点在于描述题目需求、示例以及基于计数的直接解法。

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 最长无重复子数组

本文介绍了 NC41 “最长无重复子数组” 的求解思路。给定长度 ≤10⁵ 的整数数组，要求返回其中连续且元素互不相同的最长子数组长度。使用滑动窗口结合哈希表记录窗口内各数字出现次数：右指针逐步扩张，将新元素计入哈希表；若出现次数超过 1，则左指针收缩并相应减计数，直至窗口内无重复。每次更新窗口长度的最大值，即得到答案。代码实现基于 O(n) 时间、O(k) 空间（k 为窗口内不同元素数）。

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

NC19 连续子数组的最大和

本文介绍了求整型数组所有连续子数组最大和的问题，要求时间 O(n)，空间 O(1)。给出典型示例并提供基于 Kadane 算法的实现：遍历数组时累计当前子数组和，若累计和为负则重置为零，并实时更新全局最大值。代码示例展示了仅用一次遍历即可得到答案。

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

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

题目要求在链表中每 k 个节点为一组进行翻转，若剩余节点不足 k 则保持原序，只能改动指针，空间 O(1)、时间 O(n)。解法先遍历 k 步确定本组末节点 tail，若不足则直接返回原链表；随后在 head 与 tail 之间使用前驱 pre、当前 cur 进行就地翻转，循环至 cur 达到 tail。翻转完成后，将原 head（现为本组尾）指向递归处理的下一段 tail，返回翻转后的头指针 pre。代码实现简洁，满足题目所有约束。

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 用两个栈实现队列

本文介绍了使用两个栈实现队列的算法。通过在入队时向栈 1 压入元素，出队时若栈 2 为空则将栈 1 的全部元素弹出并压入栈 2，实现先进先出。该实现满足空间复杂度 O(n) 且每次 push、pop 的均摊时间复杂度均为 O(1)。代码示例给出 Java 实现，演示了对应的操作流程和示例输入输出。

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

NC33 合并两个排序的链表

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

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