LeetCode 21-25 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题21-25 =====＞＞＞ ＜建议收藏＞)
LeetCode 21-25 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题21-25 =====＞＞＞ ＜建议收藏＞)
第21题. Merge Two Sorted Lists
题目描述（简单难度）
合并两个有序链表。
解法一 迭代
遍历两个链表。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode h = new ListNode(0);
ListNode ans=h;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
h.next = l1;
h = h.next;
l1 = l1.next;
} else {
h.next = l2;
h = h.next;
l2 = l2.next;
}
}
if(l1==null){
h.next=l2;
}
if(l2==null){
h.next=l1;
}
return ans.next;
}时间复杂度：O（m + n）。
空间复杂度：O（1）。
解法二 递归
参考[这里](https://leetcode.wang/Merge Two Sorted Lists)
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}时间复杂度：
空间复杂度：
总
递归看起来，两个字，优雅！但是关于递归的时间复杂度，空间复杂度的求法，先留个坑吧。
第22题 . Generate Parentheses
1. 题目描述（中等难度）
给一个数字 n ，返回所有合法的括号匹配，刚好和[20题](https://leetcode.wang/leetCode-20-Valid Parentheses.html)相反。
自己没想出来，全部参考 LeetCode 给出的 Solution。
解法一 暴力破解
列举所有的情况，每一位有左括号和右括号两种情况，总共 2n 位，所以总共 22n2^{2n}22n 种情况。
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current))
result.add(new String(current));
} else {
current[pos] = '(';
generateAll(current, pos+1, result);
current[pos] = ')';
generateAll(current, pos+1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') balance++;
else balance--;
if (balance < 0) return false;
}
return (balance == 0);
}时间复杂度：对每种情况判断是否合法需要 O（n），所以时间复杂度是 O(22nn)O(2^{2n}n)O(22nn) 。
空间复杂度：O(22nn)O(2^{2n}n)O(22nn)，乘以 n 是因为每个串的长度是 2n。此外这是假设所有情况都符合的时候，但其实不可能都符合，后边会给出更精确的情况。
解法二
解法一中，我们不停的加左括号，其实如果左括号超过 n 的时候，它肯定不是合法序列了。因为合法序列一定是 n 个左括号和 n 个右括号。
还有一种情况就是如果添加括号的过程中，如果右括号的总数量大于左括号的总数量了，后边不论再添加什么，它都不可能是合法序列了。因为每个右括号必须和之前的某个左括号匹配，如果右括号数量多于左括号，那么一定有一个右括号没有与之匹配的左括号，后边不论加多少左括号都没有用了。例如 n = 3 ，总共会有 6 个括号，我们加到 ( ) ) 3 个括号的情况的时候，有 1 个左括号，2 个右括号，此时后边 3 个括号无论是什么，已经注定它不会是合法序列了。
基于上边的两点，我们只要避免它们，就可以保证我们生成的括号一定是合法的了。
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, String cur, int left, int right, int n){
if (cur.length() == n * 2) {
ans.add(cur);
return;
}
//左括号不要超过 n
if (left < n)
backtrack(ans, cur+"(", left+1, right, n);
//右括号不要超过左括号
if (right < left)
backtrack(ans, cur+")", left, right+1, n);
}时间复杂度：
空间复杂度：
递归的复杂度分析，继续留坑 =.=。
解法三
解法二中是用列举的方法，仔细想想，我们每次用递归的时候，都是把大问题换成小问题然后去解决，这道题有没有这个思路呢？
我们想一下之前的列举过程，第 0 个位置一定会是左括号，然后接着添加左括号或右括号，过程中左括号数一定大于或等于右括号数，当第一次出现左括号数等于右括号数的时候，假如此时的位置是 c 。那么位置 1 到 c - 1 之间一定是合法序列，此外 c + 1 到最后的 2n -1 也是合法序列。而假设总共是 n 组括号，1 到 c - 1 是 a 组括号， c + 1 到 2n - 1 之间则是 n - 1 - a 组括号，如下图
最重要的是，每一个合法序列都会有这么一个数 c ，且唯一。所以我们如果要求 n 组括号的所有序列，只需要知道 a 组括号以及 ( n - a - 1) 组括号的所有序列，然后两两组合即可。
以 n = 3 为例，我们把 0 到 c 之间的括号数记为 a 组， c + 1 到最后的括号数记为 b 组，则
a = 0，b = 2 对应 （）（（））以及 （）（）（） 两种情况，此时 c = 1。
a = 1，b = 1，对应 （（））（（）） 一种情况，此时 c = 3。
a = 2，b = 0 对应 （（（）））， （（）（）） 两种情况，此时 c = 5。
所以我们如果要想求 n 组括号，只需要知道 a 组和 b 组的情况，然后组合起来就可以了。
看起来我们在迭代 a ，其实本质上是在迭代 c ，c = 2a + 1，迭代 a 从 0 到 n - 1 ，就是迭代 c 从 1 到 2n - 1。看起来 c 都是奇数，其实是可以理解的，因为 0 到 c 间都是一组组的括号， 所以 c 一定是奇数。为什么可以迭代 c ，因为上边说到每一个合法序列都对应着一个 c ，遍历 c 的话，就能得到所有的情况了，看一下代码吧。
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
if (n == 0) {
ans.add("");
} else {
for (int a = 0; a < n; a++)
for (String left: generateParenthesis(a))
for (String right: generateParenthesis(n-1-a))
ans.add("(" + left + ")" + right);
}
return ans;
}时间复杂度：
空间复杂度：
留坑。
扩展 卡塔兰数
如果这道题不是让你列举所有的情况， 而是仅仅让你输出 n 对应下有多少种合法序列，该怎么做呢？
答案就是 1n+1C2nn\frac{1}{n+1}C^n_{2n}n+11C2nn，也可以写成1n+1(2nn)\frac{1}{n+1}\binom{2n}{n}n+11(n2n)。怎么证明呢？我主要参考了这里，说一下。
我们假设不考虑是不是合法序列，那么就一共有C2nnC^n_{2n}C2nn种情况，然后我们只需要把里边的非法情况减去就可以了，一共有多少种非法情况呢？
首先我们用C2nnC^n_{2n}C2nn就保证了一定是有 n 个左括号，n 个右括号，那么为什么出现了非法序列？
为了方便论述，我们把左括号记为 +1，右括号记为 -1.
ps：下边的 和 都是指两个数的和，不是你和我中的和。
我们假设非法序列的集合是 M ，而非法序列就是列举过程中右括号数比左括号数多了，也就是和小于 0 了，变成 -1 了。这种情况一旦出现，后边无论是什么括号都改变不了它是非法序列的命了。我们将第一次和等于 -1 的时候的位置记为 d 。每一个非法序列一定存在这样一个 d 。然后关键的地方到了！
此时我们把 0 到 d 所有的 -1 变成 1，1 变成 -1，我们将每一个非法序列都这样做，就构成了一个新的集合 N ，并且这个集合 N 一定和 M 中的元素一一对应（ N -> M，在集合 N 中第一次出现和为 1 的位置也就是 d ，把 0 到 d 中所有的 -1 变成 1，1 变成 -1 就回到了 M），从而集合 M 的数量就等于集合 N 的数量。集合 N 的数量是多少呢？
我们来分析下集合 N 是什么样的，集合 N 对应的集合 M 原来的序列本来是这样的，在 0 到 d 之间和是 -1 ，也就是 -1 比 +1 多一个，d + 1 到最后的和一定是 1（因为 n 个 +1 和 n 个 -1 的和一定是 0 ，由于 0 到 d 和是 -1，后边的和一定是 1），也就意味着 +1 比 -1 多一个。而在集合 N 中，我们把 0 到 d 的 -1 变成了 +1 ，+1 变成了 -1 ，所以也变成了 +1 比 -1 多一个，所以集合 N 总共就是 +1 比 -1 多 2 个的集合，也就是 n + 1 个 +1 和 n - 1 个 -1 。
所以集合 N 就是 2n 个位置中选 n - 1 个位置放 -1，其他位置放 +1，总共就有 C2nn−1C^{n - 1}{2n}C2nn−1，所以集合 M 也有 C2nn−1C^{n - 1}{2n}C2nn−1种。
所有合法序列就有 C2nn−C2nn−1=1n+1C2nnCn_{2n}-C{n-1}{2n}=\frac{1}{n+1}C^n{2n}C2nn−C2nn−1=n+11C2nn 。
将集合 M 和集合 N 建立了一一映射，从而解决了问题，神奇！！！！！！！！！！其实，这个数列就是卡塔兰数，可以看下维基百科的定义。
而这个数列，其实除了括号匹配，还有很多类似的问题，其本质是一样的，例如，
2n 个人排队买票，其中 n 个人持 50 元，n 个人持 100 元。每张票 50 元，且一人只买一张票。初始时售票处没有零钱找零。请问这 2n 个人一共有多少种排队顺序，不至于使售票处找不开钱？
对于一个无限大的栈，一共n个元素，请问有几种合法的入栈出栈形式？
P = a1 a2 a3 … an，其中 ai 是矩阵。根据乘法结合律，不改变矩阵的相互顺序，只用括号表示成对的乘积，试问一共有几种括号化方案？
n 个结点可构造多少个不同的二叉树？
… …
而 Solutin 给出的时间复杂度，其实就是卡特兰数。
维基百科的给出的性质。
总
本以为这道题挺常规的，然后自己一直卡在解法三的理解上，查来查去，竟然查出了卡塔兰数，虽然似乎和解法三也没什么关系，但又开阔了很多思路。解法三分析出来的迭代方法，以及用映射证明卡塔兰数的求法，棒！
第23题: Merge k Sorted Lists
- 题目描述（困难难度）
k 个有序链表的合并。
我们用 N 表示链表的总长度，考虑最坏情况，k 个链表的长度相等，都为 n 。
解法一 暴力破解
简单粗暴，遍历所有的链表，将数字存到一个数组里，然后用快速排序，最后再将排序好的数组存到一个链表里。
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> l = new ArrayList<Integer>();
//存到数组
for (ListNode ln : lists) {
while (ln != null) {
l.add(ln.val);
ln = ln.next;
}
}
//数组排序
Collections.sort(l);
//存到链表
ListNode head = new ListNode(0);
ListNode h = head;
for (int i : l) {
ListNode t = new ListNode(i);
h.next = t;
h = h.next;
}
h.next = null;
return head.next;
}时间复杂度：假设 N 是所有的数字个数，存到数组是 O（N），排序如果是用快速排序就是 O(NlogN)O(Nlog_N)O(NlogN) ，存到链表是 O（N），所以取个最大的，就是 O(NlogN)O(Nlog_N)O(NlogN)。
空间复杂度：新建了一个链表，O（N）。
解法二 一列一列比较
我们可以一列一列的比较，将最小的一个存到一个新的链表里。
public ListNode mergeKLists(ListNode[] lists) {
int min_index = 0;
ListNode head = new ListNode(0);
ListNode h = head;
while (true) {
boolean isBreak = true;//标记是否遍历完所有链表
int min = Integer.MAX_VALUE;
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
//找出最小下标
if (lists[i].val < min) {
min_index = i;
min = lists[i].val;
}
//存在一个链表不为空，标记改完 false
isBreak = false;
}
}
if (isBreak) {
break;
}
//加到新链表中
ListNode a = new ListNode(lists[min_index].val);
h.next = a;
h = h.next;
//链表后移一个元素
lists[min_index] = lists[min_index].next;
}
h.next = null;
return head.next;
}时间复杂度：假设最长的链表长度是 n ，那么 while 循环将循环 n 次。假设链表列表里有 k 个链表，for 循环执行 k 次，所以时间复杂度是 O（kn）。
空间复杂度：N 表示最终链表的长度，则为 O（N）。
其实我们不需要创建一个新链表保存，我们只需要改变得到的最小结点的指向就可以了。
public ListNode mergeKLists(ListNode[] lists) {
int min_index = 0;
ListNode head = new ListNode(0);
ListNode h = head;
while (true) {
boolean isBreak = true;
int min = Integer.MAX_VALUE;
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
if (lists[i].val < min) {
min_index = i;
min = lists[i].val;
}
isBreak = false;
}
}
if (isBreak) {
break;
}
//最小的节点接过来
h.next = lists[min_index];
h = h.next;
lists[min_index] = lists[min_index].next;
}
h.next = null;
return head.next;
}时间复杂度：假设最长的链表长度是 n ，那么 while 循环将循环 n 次。假设链表列表里有 k 个链表，for 循环执行 k 次，所以时间复杂度是 O（kn）。
空间复杂度：O（1）。
解法三 优先队列
解法二中，我们每次都是取出一个最小的，然后加入一个新的， O（1）的复杂度，再找最小的，O（k） 的复杂度。我们完全可以用一个优先队列。
我们将优先级定义为数越小优先级越高，如果用堆实现优先队列，这样我们每次找最小不再需要 O（k），而是 O（log（k）），当然这样的话，我们加入新的话不再是 O（1），也需要 O（log（k））。可以看看这里和这里。
public ListNode mergeKLists(ListNode[] lists) {
//定义优先队列的比较器
Comparator<ListNode> cmp;
cmp = new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
// TODO Auto-generated method stub
return o1.val-o2.val;
}
};
//建立队列
Queue<ListNode> q = new PriorityQueue<ListNode>(cmp);
for(ListNode l : lists){
if(l!=null){
q.add(l);
}
}
ListNode head = new ListNode(0);
ListNode point = head;
while(!q.isEmpty()){
//出队列
point.next = q.poll();
point = point.next;
//判断当前链表是否为空，不为空就将新元素入队
ListNode next = point.next;
if(next!=null){
q.add(next);
}
}
return head.next;
}时间复杂度：假如总共有 N 个节点，每个节点入队出队都需要 log（k），所有时间复杂度是 O（N log（k））。
空间复杂度：优先队列需要 O（k）的复杂度。
解法四 两两合并
利用之前合并两个链表的算法，我们直接两两合并，第 0 个和第 1 个链表合并，新生成的再和第 2 个链表合并，新生成的再和第 3 个链表合并…直到全部合并完。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode h = new ListNode(0);
ListNode ans=h;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
h.next = l1;
h = h.next;
l1 = l1.next;
} else {
h.next = l2;
h = h.next;
l2 = l2.next;
}
}
if(l1==null){
h.next=l2;
}
if(l2==null){
h.next=l1;
}
return ans.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==1){
return lists[0];
}
if(lists.length==0){
return null;
}
ListNode head = mergeTwoLists(lists[0],lists[1]);
for (int i = 2; i < lists.length; i++) {
head = mergeTwoLists(head,lists[i]);
}
return head;
}时间复杂度：不妨假设是 k 个链表并且长度相同，链表总长度为 N，那么第一次合并就是 N/k 和 N/k ，第二次合并就是 2 * N/k 和 N/k，第三次合并就是 3 * N/k 和 N / k，总共进行 n - 1 次合并，每次合并的时间复杂度是 O（n），所以总时间复杂度就是O(∑i=1k−1(i∗Nk+Nk))=O(kN)O(\sum_{i=1}^{k-1}(i*\frac{N}{k}+\frac{N}{k}))=O(kN)O(∑i=1k−1(i∗kN+kN))=O(kN)，可以将两项分开，N/k 其实是常数，分开的第一项是等差数列。
空间复杂度：O（1）。
解法五 两两合并优化
依旧假设是 k 个链表，合并的过程优化下，使得只需要合并 log（k）次。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode h = new ListNode(0);
ListNode ans=h;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
h.next = l1;
h = h.next;
l1 = l1.next;
} else {
h.next = l2;
h = h.next;
l2 = l2.next;
}
}
if(l1==null){
h.next=l2;
}
if(l2==null){
h.next=l1;
}
return ans.next;
}
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){
return null;
}
int interval = 1;
while(interval<lists.length){
System.out.println(lists.length);
for (int i = 0; i + interval< lists.length; i=i+interval*2) {
lists[i]=mergeTwoLists(lists[i],lists[i+interval]);
}
interval*=2;
}
return lists[0];
}时间复杂度：假设每个链表的长度都是 n ，有 k 个链表，记总结点数是 N = n * k，那么时间复杂度就是O(∑i=1log2kN)=O(Nlogk)O(\sum_{i=1}^{log_2k}N)=O(Nlogk)O(∑i=1log2kN)=O(Nlogk)。
空间复杂度：O（1）。
总
优先队列的运用印象深刻，此外对两两链表的合并，我们仅仅改变了合并的方式就将时间复杂度降低了很多，美妙！
第24题: Swap Nodes in Pairs
题目描述（中等难度）
给定一个链表，然后两两交换链表的位置。
解法一 迭代
首先为了避免单独讨论头结点的情况，一般先申请一个空结点指向头结点，然后再用一个指针来遍历整个链表。
先来看一下图示：
point 是两个要交换结点前边的一个位置。
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode point = dummy;
while (point.next != null && point.next.next != null) {
ListNode swap1 = point.next;
ListNode swap2 = point.next.next;
point.next = swap2;
swap1.next = swap2.next;
swap2.next = swap1;
point = swap1;
}
return dummy.next;
}时间复杂度：O（n）。
空间复杂度：O（1）。
解法二 递归
参考这里。
自己画了个参考图。
public ListNode swapPairs(ListNode head) {
if ((head == null)||(head.next == null))
return head;
ListNode n = head.next;
head.next = swapPairs(head.next.next);
n.next = head;
return n;
}递归时间复杂度留坑。
总
自己开始没有想出递归的算法，每次都会被递归的简洁吸引。另外，感觉链表的一些题，只要画图打打草稿，搞清指向关系，一般不难。
第25题 : Reverse Nodes in k-Group
题目描述（困难难度）
将一个链表，每 k 个倒置，最后一组不足 k 个就不倒置。
解法一 迭代
关于单链表倒置，我们在第 2 题就讨论过。有了单链表倒置，这道题无非就是用一个循环，每次将 k 个结点取下来，倒置后再接回去，然后再取 k 个，以此循环，到了最后一组如果不足 k 个，不做处理，直接返回头结点就可以了。所以关键就是，指针指来指去，大家不晕掉就好，我做了图示，大家参考一下。
为了将头结点也一般化，我们创建一个 dummy 结点，然后整个过程主要运用三个指针， tail 指针表示已经倒置后的链表的尾部，subhead 指针表示要进行倒置的子链表，toNull 指针为了将子链表从原来链表中取下来。
一个 while 循环，让 toNull 指针走 k - 1 步使其指向子链表的尾部。中间的 if 语句就是判断当前节点数够不够 k 个了，不够的话直接返回结果就可以了。
将子链表指向 null ，脱离出来。并且用 temp 保存下一个结点的位置。
然后调用倒置函数，将子链表倒置。
接下来四步分别是，新链表接到 tail（注意下边的图 tail 是更新后的位置，之前 tail 在 dummy 的位置） 的后边；更新 tail 到新链表的尾部，也就是之前的 subhead （下图 subhead 也是更新后的位置，之前的位置参见上边的图）；sub_head 更新到 temp 的位置；toNull 到 sub_head 的位置；然后将新的尾部 tail 把之前断开的链表连起来，接到 sub_head 上。
整理下其实就是下边的样子
和初始的时候（下边的图）对比一下，发现 tail，subhead 和 toNull 三个指针已经就位，可以愉快的重复上边的步骤了。
看下代码吧。
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null)
return null;
ListNode sub_head = head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tail = dummy;
ListNode toNull = head;
while (sub_head != null) {
int i = k;
//找到子链表的尾部
while (i - 1 > 0) {
toNull = toNull.next;
if (toNull == null) {
return dummy.next;
}
i--;
}
ListNode temp = toNull.next;
//将子链表断开
toNull.next = null;
ListNode new_sub_head = reverse(sub_head);
//将倒置后的链表接到 tail 后边
tail.next = new_sub_head;
//更新 tail
tail = sub_head; //sub_head 由于倒置其实是新链表的尾部
sub_head = temp;
toNull = sub_head;
//将后边断开的链表接回来
tail.next = sub_head;
}
return dummy.next;
}
public ListNode reverse(ListNode head) {
ListNode current_head = null;
while (head != null) {
ListNode next = head.next;
head.next = current_head;
current_head = head;
head = next;
}
return current_head;
}时间复杂度：while 循环中本质上我们只是将每个结点访问了一次，加上结点倒置访问的一次，所以总共加起来每个结点其实只访问了 2 次。所以时间复杂度是 O（n）。
空间复杂度：O（1）。
解法二递归
有没有被解法一的各种指针绕晕呢，我们有一个更好的选择，递归，这样看起来就会简洁很多。
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null)
return null;
ListNode point = head;
//找到子链表的尾部
int i = k;
while(i - 1 >0){
point = point.next;
if (point == null) {
return head;
}
i--;
}
ListNode temp = point.next;
//将子链表断开
point.next = null;
//倒置子链表，并接受新的头结点
ListNode new_head = reverse(head);
//head 其实是倒置链表的尾部，然后我们将后边的倒置结果接过来就可以了
//temp 是链表断开后的头指针，可以参考解法一的图示
head.next = reverseKGroup(temp,k);
return new_head;
}
public ListNode reverse(ListNode head) {
ListNode current_head = null;
while (head != null) {
ListNode next = head.next;
head.next = current_head;
current_head = head;
head = next;
}
return current_head;
}复杂度：递归留坑。
总
还是那句话，涉及到链表的，我们就画下图，把各个指针的移动理清楚，一般没啥问题。
今天我们一起学习了LeetCode 题的算法分析,感谢大家阅读,觉得不错记得收藏哦!
喜欢 请点个 + 关注
腾讯云开发者
