19. 删除链表的倒数第 N 个结点
双指针在链表中辅助定位
//
19.题目链接-来源：力扣（LeetCode）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
示例 1：
输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]
思路：我们考虑一趟扫描的思路。思考这样一种实现，我们用两个指针指向链表中的节点，这两个指针之间间隔 n 个结点，我们记更接近尾部的这个指针为 helper，更接近头部的这个指针为 handle，则当 helper 指针达到链表尾部时，handle 恰指向链表的倒数第 n + 1 个节点。细节：链表题目为了简化判定逻辑，需要在链表头部插入一个辅助性质的「伪头结点」，方便我们简化对空表的判断逻辑。注意我们的 handle 要指向倒数第 n + 1 个节点而非倒数第 n 个节点，这样才能方便我们进行删除操作。
时间复杂度：O(n)空间复杂度：O(1)
实现：123456789101112131415161718class Solution { public ListNode re ...
18. 四数之和
双指针简化数组查找
//
18.题目链接-来源：力扣（LeetCode）
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
思路：经过之前的「两数之和」、「三数之和」给我们的启示，对于有序数组最内层的两数循环可以用双指针法从 O(n²) 复杂度降为 O(n)。其他层的优化不会降低复杂度，所以对于「四数之和」，复杂度最少为 O(n³）。首先我们先将原数组排序，然后记四个数的指针从小到大依次为 l1，l2，r1，r2。我们以 l1 为基准，遍历整个数组，为了防止重复，每次更新 l1 时判断与旧值是否相等，若相等则直接跳过；其次以 d 为基准，从后往前遍历 l1 的右侧部分，同样为了防止重复 ...
17. 电话号码的字母组合
用图的遍历 + 回溯 解决字符组合的枚举。
//
17.题目链接-来源：力扣（LeetCode）（中等）
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的电话号码按键字母组合。答案可以按 任意顺序 返回。示例 1：
输入：digits = “23”输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
思路：要求输出的字符串其实就是按照输入的号码建树，根节点是个空串，第一个数字为2，则分出a, b, c三个子节点，第二个数字为3，每个子节点又继续各自分出d, e, f节点，依此类推，然后进行遍历，输出从根节点出发到每个叶节点的结果。由于需要我们自己建树，所以如果用DFS的话就要用回溯算法；而用BFS的话会比较直观一些，但是需要建一个辅助队列。无论哪种做法，时间复杂度都一样，DFS需要递归层数规模的栈空间，BFS需要创建队列容纳相当于所有结果，需要的堆空间比较多。时间复杂度：O( $3^m$ * $4^n$) 其中m是对应3个字母的数字个数（也就是2,3,4,5,6,8），n是7,9的个数空间复杂度：BFS：O(m+n) ...
16. 最接近的三数之和
双指针简化数组遍历
//
16.题目链接-来源：力扣（LeetCode）（中等）
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1输出：2解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
思路：遍历方式跟上一道题雷同。先快速排序，再一层遍历+一层双指针。修改一下更新最佳值的条件即可，要求target和当前三数和的差值的绝对值尽可能小。偷懒的话，可以不进行最后的指针优化（跳过重复元素），复杂度还是一样的。时间复杂度：O(n²)空间复杂度：O(1)
实现：1234567891011121314151617181920212223242526272829303132333435363738class Solution { public int threeSumClosest(int[] nums, i ...
15. 三数之和
利用双指针或哈希表简化数组处理
//
15.题目链接-来源：力扣（LeetCode）（中等）
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]
思路：暴力解法就不谈了，很直白但是肯定超时。至少需要优化到O(n²)才可能通过。注意到要求三元组不可重复，这种时候显然就需要排序了，不然你怎么记得自己存没存过这个答案。一开始心头一惊，一般排序要用快排，实现起来还是蛮繁琐的（要写个寻找pivot然后递归的辅助函数）。然后想起来 Arrays.sort() 这个小东西，对java的基本类型采用的是快排，于是直接拿来。接下来看看能不能从暴力O(n³)简化到O(n²)。上一篇笔记提过这种组合查找的题目自然而然想到用哈希表查找，把某一层O(n)的遍历降为O(1)。用一个HashSet记录一遍表中的元素，那么直接枚 ...
14. 最长公共前缀
顺序比较字符串
//
14. 题目链接-来源：力扣（LeetCode）（简单）
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输入：strs = [“flower”,”flow”,”flight”]输出：”fl”
思路：这题的解法形象地理解就是给你并排放几根烤串，你拿一根签子垂直这些烤串，一排排把东西划下来。第一排全是豆腐，第二排全是鸡柳，第三排全是板筋，第四排，出现不一样的了有骨肉相连、有蚕蛹，那么前三排一样的部分『豆腐』、『鸡柳』、『板筋』就是所求的公共前缀。这种解法可以称之为『垂直遍历』或者『横向遍历』或者随便什么名字。与之相对应的就是『平行遍历』，先遍历记录第一串，再遍历对比第二串，发现到不同之处就截停，丢弃余下部分，只保留相同部分，继续比对。时间复杂度：O(nm) n是字符串个数，m是公共前缀长度。但实际上如果第一串字符串是最长的，第二种方法仍然会把它遍历完，但是多出来的部分不影响mn的数量级就是了。空间复杂度:O(m+n)（垂直遍历） O(m)（平行遍历）
实现：12345678910111213141 ...
13. 罗马数字转整数
实现字符串转换规则
//
13.题目链接-来源：力扣（LeetCode）（简单）
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: “III”输出: 3
思路：这题其实可以做得比上一题巧妙，不懂为什么上题中等这题却是简单。首先转换思路比较直白，读入字符串，数值相应增加，那么跟前一题一样，需要先用个表之类的东西存储一下对应关系。难点在于，4和9的数码对应的字符串含有减法（如IX是 10 - 1 = 9，即后面的大数减去前面的小数）。注意到，减法只会出现在大数前的小数，也就是减法永远出现在数字5,10前面的数字1处。而罗马字符整体上是从大到小显示的，一旦出现『小大』组合，便是小数变号。那么我们将字符串倒过来看，是不是就意味着，整体上是从小到大排列，一旦有『大小』组合，便是小数变号。只要此时在大数出现的时候，作一个负号标记，那么该大数往后的小数就一定需要加负号。（如MCMXCIV，倒序是VICXMCM，V是5，那么之后的I（1）就是负数，C是100，那么之后的X（10）就是负数，依此类推）当然字符串逆序需要多一点点额外的开销，整体 ...
12. 整数转罗马数字
实现编码规则
//
12. 题目链接-来源：力扣（LeetCode）（中等）
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值I 1V 5X 10L 50C 100D 500M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 ...
11. 盛最多水的容器
双指针降低问题复杂度的维数
//
11. 题目链接-来源：力扣（LeetCode）（中等）
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
思路：本质上就是求n块板子两两配对，它们之间的长度和距离所围成的矩形面积。如果暴力解，每块板子都与剩下的n-1块板子配对计算一次面积，也不是不行，但是复杂度为O(n²)，太笨了。简化问题，首先面积 = 距离 * 高度，距离好办，我们一开始分别选择两侧的板子就能保证距离最远。高度呢，那就逐渐缩短距离，以距离换高度。那么从哪边开始缩呢，根据短板原理，需要先改变较低的一边，否则水位只可能下降（另一侧变得比这一侧还要矮）或者持平（另一侧变高或者不变）。所以确定好距离收缩的规则，从两侧向中间收缩，每次收缩求出面积取最大值即可。时间复杂度：O(n)空间复杂度：O(1)
实现：123456789101112131415161 ...
10. 正则表达式匹配
二维动态规划解决正则表达式匹配问题
//
10.题目链接-来源：力扣（LeetCode）（困难）
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符‘*’ 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = “aa” p = “a”输出：false解释：”a” 无法匹配 “aa” 整个字符串。
####思路：本题是一道动态规划处理字符串的的经典题目。对于’.’，一个简化的考虑就是，我们设计一个方法 match(char a, char b)，当且仅当 a = b 或者 a、b之中任意一个为’.’时返回 true 。我们用 f(i, j)表示 s截至第i - 1个字符s[i - 1]的子串，与 p截至第j - 1个字符p[j - 1]的子串 是匹配的。那么我们要考虑的问题就是，f(i + 1, j)是否成立，f(i, j + 1)是否成立。注意，f(0, n) 和 f(m, 0) 分别对应「s为空串」以及「p为空串」 ...