算法 - 召田最帅boy

922. 按奇偶排序数组 II

给定长度为偶数且奇偶各半的整数数组 nums，要求重新排列，使得下标为偶数的位置存放偶数，下标为奇数的位置存放奇数。解法是一次遍历将所有偶数和奇数分别存入两个等长数组，然后按顺序交替写回原数组，即先放一个偶数再放一个奇数，直至填满。时间复杂度 O(n)，额外空间 O(n/2)。

2022-03-28 11:12:30 阅读

13. 罗马数字转整数

本文介绍了将罗马数字转换为整数的算法。首先阐述罗马数字的七个字符及对应数值，并说明常规写法与六种减法特例（IV、IX、XL、XC、CD、CM）。在约束条件下（长度1‑15，数值1‑3999），给出实现思路：遍历字符串，比较相邻字符的数值大小，若前者小于后者则减去前值，否则加上前值，最后再加上最后一个字符的数值。代码通过一个映射函数 `getValue` 返回单字符数值，实现简洁高效的转换。

2022-03-27 12:50:38 阅读

1507. 转变日期格式

本文介绍 LeetCode 1507 “转变日期格式”题目：给定形如 “Day Month Year”（如 “20th Oct 2052”）的字符串，要求输出 “YYYY‑MM‑DD”。文章说明了合法输入的组成规则，并给出三个示例对应的转换结果。随后提供了一段 Java 实现思路：先按空格分割获取年、月、日；使用月份数组映射英文缩写到两位数字；去除日中的后缀（th、st、nd、rd），不足两位前补零；最后按 “year-month-day” 组装并返回。代码完整且符合题目要求。

2022-03-27 12:30:52 阅读

20.有效的括号

本文介绍了 LeetCode 第 20 题“有效的括号”。题目要求判断仅由 '('、')'、'{'、'}'、'['、']' 组成的字符串是否满足：左括号必须被相同类型的右括号闭合且顺序正确。文章给出 O(n) 时间、O(n) 空间的栈解法：遍历字符时，将左括号对应的期望右括号压入栈；遇到右括号时检查栈顶是否匹配，若不匹配或栈空则返回 false。遍历结束后栈为空即为有效。代码实现简洁，符合题目约束。

2022-03-07 13:15:50 阅读

1108. IP 地址无效化

给定一个有效的 IPv4 地址，将其中的每个点号 “.” 替换为 “[.]”，返回处理后的字符串。示例：`"1.1.1.1"` → `"1[.]1[.]1[.]1"`，`"255.100.50.0"` → `"255[.]100[.]50[.]0"`。实现思路为遍历地址字符，遇到 “.” 时追加 “[.]”，否则直接追加原字符，使用 `StringBuilder` 构造结果并返回。

2022-03-26 19:33:35 阅读

数据结构之线性表详解

本文系统阐述了线性表的三种基本实现——数组、链表和栈。说明了数组的连续存储、随机访问 O(1) 的读取/更新以及插入、删除需搬移元素导致 O(n) 的时间开销，并指出其空间连续性限制和广泛应用；介绍了链表的非连续存储、通过指针连接节点，实现 O(1) 的插入、删除和更新，但查找只能线性遍历 O(n)，适用于频繁增删的场景；进一步解释了栈的后进先出特性，可用数组或链表实现，核心操作为 push 与 pop。最后对比数组与链表的优势与适用场景，强调没有绝对优劣，需根据读写比例选择合适结构。

2021-12-01 16:39:48 阅读

338. 比特位计数

本文介绍了 LeetCode 第 338 题 “比特位计数”。题目要求给定整数 n，返回长度为 n+1 的数组，其中第 i 个元素是 i 的二进制表示中 1 的个数。文中给出两组示例，说明了 0~n 的二进制形式及对应的 1 的计数。随后提供了一种动态规划实现：利用偶数 i 的二进制可由 i/2 左移得到，故 ans[i]=ans[i/2]；奇数 i 则等于前一个数 ans[i-1] 加 1。代码遍历 1 到 n，按上述规则填充 ans 数组，时间复杂度 O(n)，空间 O(n)。

2021-12-10 10:41:09 阅读

739. 每日温度

本文介绍了 LeetCode 第 739 题 “每日温度”。给定一个整数数组 temperatures，要求计算每一天需要等待多少天才能出现更高的温度，若之后无更高温度则填 0。文章通过示例说明输入输出关系，并提供了基于单调栈的 O(n) 解法：遍历温度数组，用栈存储索引，当当前温度高于栈顶索引对应的温度时弹出栈顶并记录间隔天数，随后将当前索引入栈。最终返回记录间隔的结果数组。代码实现简洁，利用 Java 的 Stack 与数组填充完成。

2021-12-09 16:51:41 阅读

75. 颜色分类

给定仅包含 0、1、2（分别代表红、白、蓝）的数组，要求原地排序，使相同颜色相邻且顺序为红-白-蓝。示例展示了不同输入的期望输出。解法采用荷兰国旗算法：使用三个指针 left、i、right，遍历数组时将 0 移到左端、2 移到右端，1 保持原位，完成一次线性扫描即可实现 O(n) 时间、O(1) 额外空间的原地排序。代码实现包括主循环和交换函数。

2021-12-08 16:43:51 阅读

插入排序

插入排序将数组划分为已排序区和未排序区，每轮取未排序区首元素在已排序区向左移动直至找到合适位置插入，直至整体有序。实现时 i 从 1 开始遍历，t 为待插入值，j 为已排序区最后索引；若 t<a[j] 则将 a[j] 右移，循环结束后把 t 放入 j+1 位置。代码展示了每次插入后的数组并已通过提前终止循环和直接移动元素进行优化。插入排序时间复杂度为 O(n²)，在近乎有序数据时可降至 O(n)，且属于稳定排序；相比选择排序，平均性能更佳且保持稳定性。

2021-10-14 22:34:40 阅读

5. 最长回文子串

本文介绍了 LeetCode 第5题“最长回文子串”。给定字符串 s，要求找出其中最长的回文子串。代码实现采用中心扩展法：遍历 2·len‑1 个可能的中心（包括字符本身和字符间的空隙），以 left、right 为左右指针向外扩展，只要两侧字符相等即形成回文，并实时更新最长结果。时间复杂度 O(n²)，空间复杂度 O(1)。示例输入 "babad"、"cbbd"、"a"、"ac" 的输出分别为 "bab"/"aba"、"bb"、"a"、"a"。

2021-11-16 14:26:22 阅读

647. 回文子串

本文介绍了 LeetCode 647 “回文子串”问题：统计字符串中所有回文子串的数量。说明了回文子串的定义及示例（"abc" → 3，"aaa" → 6），并给出 Java 实现。核心算法为中心扩展法，遍历 2·n‑1 个可能的中心，对每个中心向左右扩展，只要左右字符相等即计数，最终返回总数。代码简洁高效，时间复杂度 O(n²)，空间复杂度 O(1)。

2021-11-16 13:44:27 阅读