7. 整数反转
通过对 10 求余和除以 10，获取最后一位数字，累加到结果中。累加前需要判断溢出
9. 回文数
反转一半数字，判断是否与另一半相等（注意位数的奇偶），该方法可以防止溢出
11. 盛最多水的容器
双指针，贪心算法。从左右向中间收缩，每次收缩较低的一边。原因是收缩时间距在变小，如果不改变较低的一边，那收缩后面积一定会更小
12. 整数转罗马数字
模拟，预先从大到小列出所有罗马数字组合，从大到小逐步减
13. 罗马数字转整数
模拟，从左到右依次转为数字，需要处理左边数字比右边数字小的情况
15. 三数之和
排序+双指针，选定第一个数，其他两数通过双指针从左右两侧遍历。利用排序进行剪枝优化
16. 最接近的三数之和
解法同三数之和，排序+双指针。根据三数和与 target 之间的最小差选择结果
18. 四数之和
解法类似三数之和，排序+双指针，选定第一个数和第二个数，双指针遍历其他两数
26. 删除有序数组中的重复项
快慢指针，快指针找到不重复的数，赋值给慢指针
27. 移除元素
(1) 快慢指针，快指针找到不为 val 的数，赋值给慢指针
(2) 快慢指针优化，快指针从右向左，赋值给慢指针为 val 的位置
29. 两数相除
用减法模拟乘法，不断循环 1) 减除数，2) 除数翻倍，直到被除数小于需要减去的数，再重新从除数开始减
31. 下一个排列
等价于找到下一比当前数字大的数，即把后面的大数与前面的小数交换，且保证交换后的结果最小。需要从右向左，找到第一个比后面数字小的数字 x，把 x 与后面比它大的最小数字交换。交换后，后续序列一定为倒序排列，需要反转为正序
41. 缺失的第一个正数
原地哈希，首先交换整数 x 到数组中 x-1 位置，随后遍历找到第一个位置不符合的数
50. Pow(x, n)
递归，快速幂
3. 无重复字符的最长子串
(1) 滑动窗口法，借助 map 判断重复字符，并且移动左边界
(2) 滑动窗口法，与解法一相同，但是不删除 map 中元素，而是比大小
5. 最长回文子串
中心扩展法，每个字符向左右两侧遍历，找到最长回文串
6. Z 字形变换
数学推理，行数变化有周期性
8.字符串转换整数 (atoi)
按规则转换，每次新增数字前都需要判断是否会溢出
10.正则表达式匹配
动态规划，dp[i][j] 表示 s 前 i 个字符 是否能被 p 前 j 个字符 匹配。重点：* 号分为匹配字符和不匹配字符分析
14. 最长公共前缀
挨个字符比较，直到结束或者遇到不同字符
28. 找出字符串中第一个匹配项的下标
(1) 暴力匹配
(2) KMP：待实现
30. 串联所有单词的子串
滑动窗口+哈希表，通过哈希表记录滑动窗口中单词与给定词组的个数差
32. 最长有效括号
(1) 借助栈匹配括号，找最长子串
(2) 使用两个常数，记录左括号和右括号数量，相等时即为有效。需要正序遍历和反序遍历各一次
(3) 动态规划，dp[i] 表示位置 i 结尾的字符串中，最大有效括号的长度
38. 外观数列
(1) 递归
(2) 迭代
43. 字符串相乘
模拟，列竖式，num1 的第 i 位与 num2 的第 j 位相乘，结果位于 i + j 和 i + j + 1 位
44. 通配符匹配
动态规划，dp[i][j] 表示 s 前 i 个字符是否能被 p 前 j 个字符匹配。重点：* 号分为匹配字符和不匹配字符分析
49. 字母异位词分组
对字符串的字母计数，计数结果一致的为异位词
19. 删除链表的倒数第 N 个结点
快慢指针，快指针先遍历 N 个结点
21. 合并两个有序链表
(1) 递归，比较头节点，选出最小的
(2) 迭代
23. 合并 K 个升序链表
(1) 递归，比较头节点，选出最小的
(2) 分治，k 个链表分为两份合并
(3) 优先队列，插入全部头节点，每次取出最小节点，并插入其下一个节点
24. 两两交换链表中的节点
(1) 借助栈，先入后出，反序相邻节点
(2) 递归
(3) 迭代
25. K 个一组翻转链表
(1) 借助双端队列，前面的每 k 个元素先入后出，反序节点，最后不足 k 个元素先入先出，保持顺序
(2) 模拟，每 k 个节点，执行一次反转链表
4. 寻找两个正序数组的中位数
(1) 双指针，从小到大递增，直到达到中位数位置
(2) 二分法，问题转化为给定两个有序数组，求第 k 小的数
(3) 二分遍历较小数组的分割线位置
33. 搜索旋转排序数组
二分法，先判断哪半边区间有序，再判断 target 是否在有序区间内
34. 在排序数组中查找元素的第一个和最后一个位置
二分法，查找两次，一次找左边界，一次找右边界。重点在于 nums[mid] == target 时的边界处理
35. 搜索插入位置
二分法
17. 电话号码的字母组合
回溯，遍历所有组合
22. 括号生成
回溯，根据左括号数量，判断下一个字符
37. 解数独
回溯，在每一个空格上，回溯遍历每个合法的数字
39. 组合总和
排序+回溯，需要结合排序结果，避免选择重复的组合
40. 组合总和 II
排序+回溯，需要结合排序结果，且跳过相同的元素，避免选择重复的组合
46. 全排列
回溯，借助交换位置生成全排列
47. 全排列 II
回溯，借助交换位置生成全排列，需要剪枝避免重复
51. N 皇后
(1) 回溯，使用二维数组记录棋盘，判断行，列，对角线是否可以放置皇后
(2) 回溯，使用位运算记录行，列，对角线是否可以放置皇后
52. N 皇后 II
与 “51. N 皇后” 完全一致
(1) 回溯，使用二维数组记录棋盘，判断行，列，对角线是否可以放置皇后
(2) 回溯，使用位运算记录行，列，对角线是否可以放置皇后
36. 有效的数独
(1) 遍历，借助二维数组，判断行、列、块内是否有重复数字
(2) 遍历，借助一维数组 + 位运算，判断行、列、块内是否有重复数字
48. 旋转图像
先转置，后翻转每一行
20. 有效的括号
使用栈，判断括号有效性
42. 接雨水
(1) 双重遍历，找到每根柱子左右侧最高的柱子高度，计算每根柱子的接水量
(2) 动态规划，使用数组记录每个柱子左右侧最高的柱子高度
(3) 双指针，从左右向中间聚拢，每次计算较低一侧的接水量
(4) 单调栈，保持栈内柱子的高度单调递减，每次出栈计算接水量
45. 跳跃游戏 II
贪心，每次选择最远的位置
53. 最大子数组和
(1) 动态规划，dp[i] 代表以 nums[i] 结尾的最大连续子数组和, 满足 dp[i] = max(dp[i-1] + nums[i], nums[i])
(2) 动态规划 + 空间优化，由于 dp[i] 只与 dp[i-1] 有关，因此可以只用一个变量 dp
(3) 分治法，对于任意区间，维护以下四个量，在合并区间时进行更新
- iSum: 区间和
- lSum: 从区间左端点出发的连续子数组最大和
- rSum: 以区间右端点出发的连续子数组最大和
- mSum：区间内的连续子数组最大和
3524. 求出数组的 X 值 I
(1) 动态规划，依据前一个元素结尾的子数组的余数数组，更新下一个元素结尾的子数组的余数数组
(2) 动态规划，在思路一的基础上，优化空间复杂度