21. 合并两个有序链表
链表形式的归并排序
//
21.题目链接-来源：力扣（LeetCode）
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]
思路：用两个指针指向两个链表的当前节点，取其中节点值较小者加入我们的结果链表，直到两链表均遍历完即可。细节：用一个「伪头结点」dummy 帮我们简化对结果链表为空时的判断逻辑，当某一个链表为空时，直接将另一条链表的余下部分接入。时间复杂度：O(n)空间复杂度：O(n)
实现：123456789101112131415161718192021222324class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode pre = new ListNode(0); ListNode cur = pre; while (l1 != ...
20. 有效的括号
用栈解决括号配对问题。
//
20.题目链接-来源：力扣（LeetCode）
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。
示例 1：
输入：s = “()”输出：true
思路：括号的配对，可以用栈来解决。因为对于一个有效的括号字符串，当第一个反括号出现时，一定可以与栈顶的正括号配对，消去栈顶元素。这样不停地用反括号消去栈顶元素，当最后一个字符访问后，栈一定为空。于是我们只要模拟这样的栈特性，当反括号出现时，就比较栈顶元素是否与其配对，若配对则消去。当遍历字符串结束后，以栈是否为空来作为判断字符串是否有效的依据。时间复杂度：O(n)空间复杂度：O(n)
实现：12345678910111213141516171819202122232425262728class Solution { public boolean isValid(String s) { Stack<Character& ...
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 可以放在 ...