26. 删除有序数组中的重复项
后面的数等于前面的就continue,不等就赋给pre,pre++
25. K 个一组翻转链表
迭代
24. 两两交换链表中的节点
迭代/递归
23. 合并K个升序链表
思路1
按合并两个有序链表一轮一轮比对
思路2
将合并两个有序链表作为方法，顺序merge
思路3
两两合并 logK的方法，仔细处理n对折。
22. 括号生成
思路
- 使用dfs生成。
注意的点
- 结束条件写在最前面
- 接下来是剪枝条件
- 左括号和右括号顺序if。注意参数不能上下影响
21. 合并两个有序链表
思路
- 简单题，正常思路下来就可
18. 四数之和
思路
- 三数之和再加一层for循环，使用continue处理前两个循环的重复问题，使用whle处理left right 重复问题，最后记得left++ right--
17. 电话号码的字母组合
思路1
- 使用map，递归传入str，以（“”，0）开始。index == digits.size()结束。
思路2
- map存数字和字符串的pair，将一个数字的字符串全push，通过q.size()确定循环次数
14. 最长公共前缀
思路1 横向比对
比对相邻两个单词的各个字符，截取最长公共前缀与接下来那个比。（感觉可以用递归来做）
思路2 纵向比对
比对字符串数组中各个单词的第一个第二个……字符，直到某一位不同
面试题 17.21. 直方图的水量
思路1
- 动态规划，左值，dp1存左侧往右能接的水量，右值，dp2存右侧往左能接的水量。取dp1.dp2的最小值为该下标的真实水量
思路2
- 单调栈，
15. 三数之和
思路
- 排序定第一个i，后面使用
leftright移动双指针判断和是否为0
值得注意的地方
- 在去重问题上把边界条件放在
nums[left] = nums[left + 1]前 - 把去重移动放在达成
==0条件的那个区域里
13. 罗马数字转整数
我的思路
- 用一个hashmap保存每一种罗马数和整数的对，在一次循环中查找是两个还是一个。优先查两个的。然后再把对应数相加。
改进思路
- 依然是使用哈希表，为了解决条件判断语句（两个还是一个的问题），将
s中的两位罗马数字替换("IV"换成"a"等等).
大佬思路
- 把一个小值例如
I放在大值V的左边，就是做减法，否则为加法.另外,把由罗马数字获取数字封装为一个函数,使用switch.
12. 整数转罗马数字
思路
- 对罗马数编码，贪心减去最大的数。能减完1000就减完1000再减900.
11. 盛最多水的容器
难点
- 使用双指针，长边缩进只会减少蓄水的容量，只有短边缩进（替换为长边）才会有可能增加容量。所以只要尝试缩进短边使用max就可
10. 正则表达式匹配
思路
-
*字符后的匹配情况分析
1)sa s*a 匹配对角线
2)s a 匹配0个 为左侧状态
3)saa sa 匹配重复 为上方状态
9. 回文数
思路1
- 左右向中间移位1，比较每一位是否相等。（需要求解位数）
思路2
- 将原数组后半部分模拟成前半部分，处理一半长度。
6. Z 字形变换
我的思路
- 使用数学方法，将每一行与首列及numsrow的关系列清楚，再按行计算。
题解思路
- 使用string列表记录每一行的str，使用flag控制列表下标的方向转换。
5. 最长回文子串
思路1
- 动态规划，转移方程：
dp[i][j] = (s[i] == s[j]) && ((j - i) < 3 || dp[i + 1][j - 1])
思路2
- 使用中心扩散的方法，针对回文串为奇数或偶数，基于
（i，i）和(i, i + 1)向两边扩散
4. 寻找两个正序数组的中位数
思路1
- 比较两个正序数组中下标为
[index + k / 2 - 1]的元素大小,去除较小元素及其左侧元素,以k / 2的速度接近中位数
这个方法可以用于获得两个正序数组中第k个元素
需要注意的地方
-
k代表个数,而非下标 - 使用左侧向右延展
k / 2的方式,注意越界情况
思路2
- 中位数满足条件——一条割线的两侧满足交叉小于等于&& 左侧元素个数==右侧元素个数（+1 分奇偶）
有时间复杂度O(log min（m，n）)，在较短的那个数组上进行二分查找。
1. 两数之和
思路：哈希表
使用哈希表记录需要匹配的数和数组下标
2. 两数相加
难点：
- 使用
l1 || l2 || add作为循环条件，在循环里判断链表是否为空
3. 无重复字符的最长子串
思路：滑动窗口
取一个遍历的右指针，一个位于重复元素右侧第一位的左指针，求两指针之间的最大值。
难点
1.如何记录重复字符？
- 使用字符哈希数组记录字符的下标，未重复使用-1作为val
2.如何找到重复元素的下标？
- 使用字符哈希数组与left值作比较，大于等于left值则重复了，被记录了一次过了。
3.使用下标作为val而非（0/1）确定是否重复，免去了查找重复元素的过程。
知识点：
1.字符哈希数组的使用
2.memset
4. 寻找两个正序数组的中位数
1.拼接两个数组并找到中位数
相关题目:
35.二分搜索
7. 整数反转
难点
如何判断溢出情况？
- 输入是十进制的数，所以需满足两个判断条件
1.最后一轮是否大于INT_MAX / 10或者小于INT_MIN / 10
2.在等于的情况下,需要判断最后一位 - 过程是在单while循环中实时模拟的方法
需要解释的地方
讨论一下输入的第一位
以256为例
输入反转后的257/258/259都是溢出的，但是752、852、952均不可能作为输入（>256），所以不需要判断等于的情况
以856为例
输入反转后的857/858/859均是溢出的，且758可以作为输入(<856)，所以要讨论758这个数的第一位(while的最后一次循环)是否大于MAX的最后一位6
