算法 - 召田最帅boy

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

深入理解Mysql索引底层数据结构与算法

索引是 MySQL 用来加速查询的有序数据结构，通过 B+Tree（或哈希）可把全表扫描降为几次磁盘 I/O。文章概述了二叉树、红黑树、哈希、B‑Tree 与 B+Tree 的特性，重点说明 B+Tree 只在叶节点存数据、非叶节点仅存键并采用双向链指针，从而提升区间访问效率。随后比较 InnoDB（聚集索引，表数据本身即 B+Tree）和 MyISAM（非聚集索引分离）的文件布局，阐述主键应为整型自增以保持索引稳定。进一步解释二级索引、联合索引的回表过程及左前缀原则，指出冗余索引的产生。最后说明 B 树与 B+Tree 的区别，并论证 MySQL 选用 B+Tree 能降低树高、减少 I/O，从而实现高效查询。

2022-07-31 22:39:37 阅读

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

NC32 求平方根

本文介绍了在 O(log x) 时间、O(1) 空间复杂度约束下实现整数平方根（向下取整）的算法。通过牛顿迭代法先设初始值为 x，不断更新 res = (res + x/res)/2，直至 res ≤ x/res 为止，即得到满足 floor(√x) 的整数结果。代码实现简洁，兼顾 x 为 0 或负数的边界处理，并给出示例输入输出验证。

2022-07-13 20:20:31 阅读