LeetCode 21-25 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题21-25 =====＞＞＞ ＜建议收藏＞)

LeetCode 21-25 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题21-25 =====＞＞＞ ＜建议收藏＞)

目录

​​第21题. Merge Two Sorted Lists​​​​解法一 迭代​​​​解法二 递归​​​​总​​​​第22题 . Generate Parentheses​​

​​1. 题目描述（中等难度）​​

​​解法一 暴力破解​​​​解法二​​​​解法三​​​​扩展 卡塔兰数​​​​总​​​​第23题: Merge k Sorted Lists​​​​解法一 暴力破解​​​​解法二 一列一列比较​​​​解法三 优先队列​​​​解法四 两两合并​​​​解法五 两两合并优化​​​​总​​​​第24题: Swap Nodes in Pairs​​​​解法一 迭代​​​​解法二 递归​​​​总​​​​第25题 : Reverse Nodes in k-Group​​​​解法一 迭代​​​​解法二递归​​​​总​​​​喜欢 请点个 + 关注​​

第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）。

解法二 递归

参考[这里](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题](Parentheses.html)相反。

自己没想出来，全部参考 LeetCode 给出的 ​​Solution​​。

解法一 暴力破解

列举所有的情况，每一位有左括号和右括号两种情况，总共 2n 位，所以总共 22n2^{2n}22n 种情况。

public List generateParenthesis(int n) { List combinations = new ArrayList(); generateAll(new char[2 * n], 0, combinations); return combinations;}public void generateAll(char[] current, int pos, List 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 generateParenthesis(int n) { List ans = new ArrayList(); backtrack(ans, "", 0, 0, n); return ans;}public void backtrack(List 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 generateParenthesis(int n) { List 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 l = new ArrayList(); //存到数组 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 cmp; cmp = new Comparator() { @Override public int compare(ListNode o1, ListNode o2) { // TODO Auto-generated method stub return o1.val-o2.val; } }; //建立队列 Queue q = new PriorityQueue(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

时间复杂度：假设每个链表的长度都是 ​​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 题的算法分析,感谢大家阅读,觉得不错记得收藏哦!

喜欢 请点个 + 关注

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。