23. 合并K个升序链表
用最小堆合并多个链表
//
23.题目链接-来源：力扣（LeetCode）
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6
思路：我们的思路基于「合并2个升序链表」拓展。在 k = 2 时，我们所要获取的链表节点实际上是当前节点值最小的那个节点。于是，我们只要维护一个可以方便获取到 当前活跃链表的未处理值 的最小堆即可。这个最小堆（优先级队列）能让我们以单次平均 O(logk) 的复杂度获取所需的节点。细节：
我们需要提供一个比较器接口给最小堆，这个比较器需要返回两个节点中节点值较小的那一个节点。
另外，当我们弹出一个节点，将其加入我们的返回列表以后，我们要将它的后 ...
22. 括号生成
DFS + 回溯法解决字符串生成问题
//
22.题目链接-来源：力扣（LeetCode）
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
思路：这是字符串生成的问题，可以考虑 DFS + 回溯法。我们利用 DFS 递归地遍历当前下一位所有可能的括号组合（当前至多有 2 种选择），然后用回溯法回到递归前的状态，当左右括号数等于所需的对数时，即收集结果。如此我们可以遍历每一位的括号组合。细节：「剪枝」，即进行下一步之前，通过条件判断过滤掉一些不可能的选择，比如，右括号不能多于左括号，所以当左右括号数相等时，我们下一步只能添加左括号；否则，我们既可以添加左括号，也可右括号，依次回溯遍历即可。时间复杂度：O(4^n/n^0.5)空间复杂度：O(n)
实现：123456789101112131415161718192021222324252627282930313233343536class S ...
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 ...