1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
解答思路： 对数组nums进行遍历，遍历i时查找target - nums[i]，查找到了即可返回，查找不到将target - nums[i]和i作为键值对存到Map中。
常规解法：
- 暴力枚举
- Hash Map进行遍历
非常规解法： 3. 排序法 排序后，在小于target的部分数组进行二分查找，排序可选择快排算法等。
时间复杂度取决于排序算法，如果是快排算法是O(nlgn)
2. 两数相加（Medium）
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字0之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围 [1, 100] 内
- 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
解题思路
单链表遍历，并考虑进位
3. 无重复字符的最长子串（Medium）
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
解题思路
使用一个滑动窗口去保存最长子串，什么是滑动窗口，实际上就是一个FIFO队列。
4. 寻找两个正序数组的中位数(Hard)
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
解题思路
- 先合并数组后再进行查找
- 对两个数组同时进行二分查找，如果m+n是奇数，那么中位数是第(m+n)/2个数，如果m+n是偶数，那么中位数是(m+n)/2和(m+n)/2 + 1的平均值。
- 分组方法
5. 最长回文子串(Medium)
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的答案。 示例 2：
输入：s = “cbbd” 输出：“bb”
提示：
1 <= s.length <= 1000 s 仅由数字和英文字母组成
解题思路
- 动态规划
- 中心扩散方法
6. Z 字形变换(Medium)
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：s = "A", numRows = 1
输出："A"
提示：
- 1 <= s.length <= 1000
- s 由英文字母（小写和大写）、’,’ 和 ‘.’ 组成
- 1 <= numRows <= 1000
解题思路
- 使用二维矩阵模拟
- 直接构造
7. 整数反转(中等)
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [$-2^{31}$, $2^{31} - 1$] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
提示：
- $-2^{31} <= x <= 2^{31} - 1$
解题思路：
32位整数的最小和最大值分别是 -2147483648和2147483647 最终可以通过判断反转后的值是否在$-2^{31}/10 <= x <= (2^{31} - 1)/10$间来判断是否会溢出
8. 字符串转换整数 (atoi)(中等)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下：
空格：读入字符串并丢弃无用的前导空格（" “） 符号：检查下一个字符（假设还未到字符末尾）为 ‘-’ 还是 ‘+’。如果两者都不存在，则假定结果为正。 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。 舍入：如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1 。 返回整数作为最终结果。
示例 1：
输入：s = “42”
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
带下划线线的字符是所读的内容，插入符号是当前读入位置。 第 1 步：“42”（当前没有读入字符，因为没有前导空格） ^ 第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’） ^ 第 3 步：“42”（读入 “42”） ^ 示例 2：
输入：s = " -042”
输出：-42
解释：
第 1 步：" -042"（读入前导空格，但忽视掉） ^ 第 2 步：" -042"（读入 ‘-’ 字符，所以结果应该是负数） ^ 第 3 步：" -042"（读入 “042”，在结果中忽略前导零） ^ 示例 3：
输入：s = “1337c0d3”
输出：1337
解释：
第 1 步：“1337c0d3”（当前没有读入字符，因为没有前导空格） ^ 第 2 步：“1337c0d3”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’） ^ 第 3 步：“1337c0d3”（读入 “1337”；由于下一个字符不是一个数字，所以读入停止） ^ 示例 4：
输入：s = “0-1”
输出：0
解释：
第 1 步：“0-1” (当前没有读入字符，因为没有前导空格) ^ 第 2 步：“0-1” (当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’) ^ 第 3 步：“0-1” (读入 “0”；由于下一个字符不是一个数字，所以读入停止) ^ 示例 5：
输入：s = “words and 987”
输出：0
解释：
读取在第一个非数字字符“w”处停止。
提示：
0 <= s.length <= 200 s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+’、’-’ 和 ‘.’ 组成
解题思路
字符的读取处理可以采用自动机的方式，或者直接处理题目的不同情况，并采用一个数字保存符号位。 如果限定只能采用32为整数，那么最大值的判断与整数反转有点区别，因为最后的个位数可能超过范围， 除了判断$-2^{31}/10 <= x <= (2^{31} - 1)/10$，还需要判断最后的个位数是否超出范围。
9. 回文数(简单)
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数 是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
示例 1：
输入：x = 121 输出：true 示例 2：
输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3：
输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。
提示：
-231 <= x <= 231 - 1
进阶：你能不将整数转为字符串来解决这个问题吗？
解题思路
回文长度分为奇数和偶数的情况，两种情况下回文从中间对折后（不含中间分隔的数字）得到的两个数字是相等的。 那么可以中间反转原数字的一半，那么需要求解的是什么时候反转到了一半。原数字x除10求余得到个位数n，然后x再除以十得到剩余的数字x， 每次得到的个位数再按顺序重组为数字b = x * 10 + n。如果x<=b，那么说明已经反转了一半的数字。这时再进行判断，如果x == b 或者 x == b/10，那么即为回文数。
10. 正则表达式匹配(Hard)
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
示例 1：
输入：s = “aa”, p = “a” 输出：false 解释：“a” 无法匹配 “aa” 整个字符串。 示例 2:
输入：s = “aa”, p = “a*” 输出：true 解释：因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。 示例 3：
输入：s = “ab”, p = “.” 输出：true 解释："." 表示可匹配零个或多个（’*’）任意字符（’.’）。
提示：
1 <= s.length <= 20 1 <= p.length <= 20 s 只包含从 a-z 的小写字母。 p 只包含从 a-z 的小写字母，以及字符 . 和 *。 保证每次出现字符 * 时，前面都匹配到有效的字符