LearningNotes
未读
最后编辑于2025-06-19
14. 最长公共前缀（Longest Common Prefix）Easy编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，则返回空字符串 ""。
示例 1：输入： strs = ["flower","flow","flight"]输出： "fl"
示例 2：输入： strs = ["dog","racecar","car"]输出： ""
约束：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 由小写英文字母组成
思路与常见解法此题没有复杂的数据结构，常见解法包括：
纵向扫描（逐列比较）：以第一个字符串为基准，逐列比较其它字符串对应位置的字符，遇到不匹配或某个字符串到达末尾即停止，时间复杂度 O(S)（S 为所有字符总数）。
横向扫描（逐个字符串 ...
LearningNotes
未读
最后编辑于2025-06-16
13. 罗马数字转整数（Roman to Integer）Easy罗马数字由七个符号表示：I(1), V(5), X(10), L(50), C(100), D(500), M(1000)。
将给定的罗马数字字符串转换为整数，输入保证在 1 到 3999 范围内且为有效罗马数字。
示例：
输入："III"，输出：3
输入："IV"，输出：4
输入："IX"，输出：9
输入："LVIII"，输出：58（L = 50, V = 5, III = 3）
输入："MCMXCIV"，输出：1994（M = 1000, CM = 900, XC = 90, IV = 4）
约束：
1 <= s.length <= 15
s 仅包含字符 I, V, X, L, C, D, M
保证 s 是一个合法的罗马数字（范围 [1,3999]）
思路与解法把罗马数字转为整数的常见 ...
LearningNotes
未读
最后编辑于2025-06-13
12. 整数转罗马数字（Integer to Roman）Medium罗马数字由七个符号表示：I(1), V(5), X(10), L(50), C(100), D(500), M(1000)。
在通常书写中，较大的数字放在左边，特殊情况使用减法表示（例如 IV 表示 4，IX 表示 9，XL 表示 40，XC 表示 90，CD 表示 400，CM 表示 900）。给定一个整数，将其转为罗马数字（1 到 3999 之间）。
示例：
输入：3，输出："III"
输入：4，输出："IV"
输入：9，输出："IX"
输入：58，输出："LVIII"（L = 50, V = 5, III = 3）
输入：1994，输出："MCMXCIV"（M = 1000, CM = 900, XC = 90, IV = 4）
约束：
1 <= num <= 3999
思路与解法由于输 ...
LearningNotes
未读
最后编辑于2025-06-10
11. 盛最多水的容器（Container With Most Water）Medium给定一个整数数组 height 长度为 n，第 i 条竖线的坐标为 (i, 0) 和 (i, height[i])。
找出两条线，使得它们与 x 轴一起形成的容器可以装下最多的水，返回容器可以存储的最大水量。注意容器不能倾斜。
示例 1：输入： height = [1,8,6,2,5,4,8,3,7]输出： 49
解释： 选取第 1（高度 8）和第 8（高度 7）两条线，面积为 min(8,7) * (8-1) = 7 * 7 = 49。
示例 2：输入： height = [1,1]输出： 1
约束：
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4
解题思路（双指针 + 贪心）观察发现，容器面积由两部分决定：宽度 j - i 与高度 min(height[i], height[j])。暴力枚举所有对需要 O(n^2)，输入规模较大时不可行。
使用双指针从数组两端向中 ...
LearningNotes
未读
最后编辑于2025-06-07
10. 正则表达式匹配（Regular Expression Matching）Hard给定输入字符串 s 和模式 p，实现支持 . 与 * 的正则表达式匹配，其中：
. 匹配任意单个字符。
* 匹配零个或多个前面的那一个元素。
匹配应该覆盖整个输入字符串（不是部分匹配）。
示例 1：输入： s = "aa", p = "a"输出： false
示例 2：输入： s = "aa", p = "a*"输出： true
示例 3：输入： s = "ab", p = ".*"输出： true
约束：
1 <= s.length <= 20
1 <= p.length <= 20
s 仅包含小写英文字母
p 仅包含小写英文字母、. 与 *，且每个 * 前都有合法的字符
思路概览此题的核心在于处理 * 带来的“零次或多次”匹配，以及 . 的通配符效果。常见解法有：
递归（回溯）：按模式逐步匹配，遇 ...
LearningNotes
未读
最后编辑于2025-06-04
9. 回文数（Palindrome Number）Easy给定一个整数 x，若 x 是回文整数则返回 true，否则返回 false。
示例 1：输入： x = 121输出： true解释： 从左到右和从右到左都是 121。
示例 2：输入： x = -121输出： false解释： 从左到右为 -121，从右到左为 121-，因此不是回文。
示例 3：输入： x = 10输出： false解释： 反向为 01，因此不是回文。
约束：
-2^{31} <= x <= 2^{31} - 1
进阶： 你能在不将整数转换为字符串的情况下解决此题吗？
思路与常见解法把整数转换为字符串后判断回文是最直接的方法，但进阶要求不允许字符串转换，可以用以下数学方法：
首尾位比较（取整/取余法）：通过计算除数 div（使 x/div 得到最高位），比较最高位与最低位（x%10），然后去掉首尾继续比较。需要注意更新 div（每次去除两位后 div 除以 100）。
翻转后半段（反转半段法）：将数字的 ...
LearningNotes
未读
最后编辑于2025-06-01
8. 字符串转整数（String to Integer, atoi）Medium实现 myAtoi(string s) 函数，将字符串转换为 32 位带符号整数（类似 C/C++ 的 atoi）。算法规则如下：
读取并忽略开头的空白字符。
检查下一个字符是否为 - 或 +，若是则记录符号并读取该字符；否则默认正数。
继续读取后续的数字字符直到遇到非数字或字符串末尾，其他字符均忽略。
将读取的数字字符转换为整数（例如 “0032” -> 32）；若没有读取到任何数字，则返回 0。根据步骤 2 中的符号调整正负。
若转换后的整数超出 32 位带符号整数范围 [-2^31, 2^31 - 1]，则截断为边界值。
返回最终结果。
示例 1：输入： s = "42"输出： 42
示例 2：输入： s = " -42"输出： -42
示例 3：输入： s = "4193 with words"输出： 4193
示例 4：输入： s = "words and 987&q ...
LearningNotes
未读
最后编辑于2025-05-29
7. 整数反转（Reverse Integer）Easy给定一个带符号的 32 位整数 x，将 x 的数字部分反转后返回。如果反转后整数溢出（超出有符号 32 位整数范围 [-2^31, 2^31-1]），则返回 0。
假设运行环境不允许使用 64 位整型（signed 或 unsigned）。
示例 1：输入： x = 123输出： 321
示例 2：输入： x = -123输出： -321
示例 3：输入： x = 120输出： 21
约束：
-2^{31} <= x <= 2^{31} - 1
题目要点与溢出处理反转整数的关键在于逐位取出数字并按位构造反转后的结果，同时要在每一步检测是否会造成溢出。因为题目限定不能使用 64 位整型（在某些 OJ 环境下），所以需要用 int 并在乘 10 或加下一位之前判断是否会越界。
一种常见且优雅的判定方法是：在将 res 乘以 10 之前检查 abs(res) > INT_MAX / 10（若为真则一定会溢出），这样可以在溢出发生前 ...
LearningNotes
未读
最后编辑于2025-5-26
6. Z字变换（ZigZag Conversion）Medium将字符串 s 按给定行数 numRows 以之字形排列，然后逐行读取得到新的字符串并返回。
示例 1：输入： s = "PAYPALISHIRING", numRows = 3输出： "PAHNAPLSIIGYIR"
示例 2：输入： s = "PAYPALISHIRING", numRows = 4输出： "PINALSIGYAHRPI"解释：
1234P I NA L S I GY A H RP I
示例 3：输入： s = "A", numRows = 1输出： "A"
约束：
1 <= s.length <= 1000
s 由大小写英文字母、, 和 . 组成
1 <= numRows <= 1000
问题分析将字符串按 numRows 行以之字形排列，观察各行字符在原串中的下标规律可以发现： ...
LearningNotes
未读
最后编辑于2025-5-23
5. 最长回文子串（Longest Palindromic Substring）Medium给定一个字符串 s，返回 s 中最长的回文子串。
示例 1：输入： s = "babad"输出： "bab"解释： "aba" 也是可接受的答案。
示例 2：输入： s = "cbbd"输出： "bb"
约束：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
问题分析与常用解法概览回文串是正读反读都相同的字符串，如 "bob"、"level"、"noon" 等。求最长回文子串的常见方法包括：
中心扩展（Expand Around Center）——时间复杂度 O(n^2)，实现简单且常用。需同时处理奇偶长度回文。推荐在面试中先写这个并通过边界测试。
改进中心扩展的快速跳过重复字符方法——在遇到连续相同字符时先跳过以合并奇偶情形，能减少常数项操作。
动态规划 ...
