Skip to content

Commit 3a802a7

Browse files
chilimyanchilimyan
authored
Merge pull request MisterBooo#3 from MisterBooo/master
更新代码
2 parents 53cc742 + 6a20215 commit 3a802a7

File tree

69 files changed

+2350
-3
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

69 files changed

+2350
-3
lines changed

‎0011-maxArea/Article/0011-maxArea.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
1+
## LeetCode第11号问题：盛水最多的容器
2+
13
> 本文首发于公众号「图解面试算法」，是 [图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
24
>
3-
> 同步个人博客：https://www.zhangxiaoshuai.fun
5+
> 同步个人博客：www.zhangxiaoshuai.fun
46
57
**本题选自leetcode的第11题，medium级别，目前通过率：61.3%**
68

‎0022-Generate-Parentheses/Animation/0022-Generate-Parentheses.m4v

7.95 MB
Binary file not shown.

‎0022-Generate-Parentheses/Animation/0022-Generate_Parentheses.gif

6.57 MB
Loading

‎0022-Generate-Parentheses/Article/0022-Generate-Parentheses.md

Lines changed: 149 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,149 @@
1+
# LeetCode 第 22 号问题：生成所有的括号对
2+
3+
> 本文首发于公众号「图解面试算法」，是 [图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
4+
>
5+
> 同步博客：https://www.algomooc.com
6+
7+
题目来源于 LeetCode 上第 22 号问题：生成所有的括号对。题目难度为 Medium，目前通过率为 60.9% 。
8+
9+
### 题目描述
10+
11+
给定数字n，要求使用n对()括号生成所有合法的组合情况。
12+
13+
**示例**
14+
15+
```
16+
3
17+
18+
[
19+
"((()))",
20+
"(()())",
21+
"(())()",
22+
"()(())",
23+
"()()()"
24+
]
25+
```
26+
27+
### 题目解析
28+
29+
#### 解法一： 暴力
30+
31+
暴力的解法应该最容易想到，因为n是确定的，也就是说一共有n个左括号和n个右括号。很容易想到，我们可以对这2n个字符进行排列组合，之后再对所有的组合进行过滤。留下合法的且不重复的即可。
32+
33+
伪代码很容易写：
34+
35+
```python
36+
def brute_force(str, l, r):
37+
if l == n and r == n:
38+
ans.append(str)
39+
if l < n:
40+
brute_force(str+'(', l+1, r)
41+
if r < n:
42+
brute_force(str+')', l, r+1)
43+
```
44+
45+
写完了再根据结果判断是否合法，留下合法的所有情况即可。
46+
47+
这样编码的确不难，而且也很容易想到，但是计算n个字符的排列组合复杂度是 $O(2^n)$ 是一个指数级的算法，复杂度是我们不能接受的。而且根据上一题当中的结论，在匹配括号的时候是可以取巧的，我们其实没必要把所有的情况都枚举到。因为想要括号匹配合法，必须有一条，对于字符串当中的任何一个位置i，都必须有：前i个字符中所有左括号的数量大于等于右括号的数量。
48+
，否则就是非法的。
49+
50+
也就是说必须要保证任意一个位置右括号的数量小于等于左括号的数量，不然的话，多余的右括号永远也无法匹配。
51+
52+
#### 解法二： 回溯
53+
54+
既然左括号的数量必须大于右括号的数量，我们完全可以据此进行优化。我们在递归的时候对l和r进行大小判断，保证所有时刻都有l >= r即可。
55+
56+
代码：
57+
58+
```C++
59+
class Solution {
60+
public:
61+
62+
void dfs(int n, int l, int r, string str, vector<string>& vt) {
63+
if (l+r == 2 *n) {
64+
vt.push_back(str);
65+
return ;
66+
}
67+
if (l < n) dfs(n, l+1, r, str+"(", vt);
68+
if (r < l) dfs(n, l, r+1, str+")", vt);
69+
}
70+
71+
vector<string> generateParenthesis(int n) {
72+
vector<string> vt;
73+
dfs(n, 0, 0, "", vt);
74+
return vt;
75+
}
76+
};
77+
```
78+
79+
#### 解法三： 构造
80+
81+
这个方法是我原创的，官方的题解当中没有收录。
82+
83+
我们直接求解n的答案的时候是比较困难的，这个时候我们可以把问题拆解，大问题变成小问题，通过小问题的答案构造大问题的答案。上述的两种方法本质上也是一样的思路，不过递归替我们做了问题的拆分。
84+
85+
实际上我们可以自己拆分问题，n的时候我们一下子不清楚答案。我们可以先从简单的观察一下结果：比如当n==1的时候，答案就是”()”。n==2有两种：”()()”, “(())”。n==3的时候是5种：”((()))”, “()(())”, “()()()”, “(()())”, “(())()”。
86+
87+
细心的读者已经可以总结出规律了，其实并不难想到。
88+
89+
solution(n) = solution(i) + solution(n-i) + '(' solution(n-1) ')'
90+
91+
解释一下这个公式，这里的solution(n)表示n的所有答案串，也就是说n个括号的答案串是可以通过小于n的答案串进行组合的。比如n=1时答案是()，n=2则有两种，一种是用两个n=1拼接，第二种是在n=1的答案外层加上一个括号：
92+
93+
solution(2) = [()(), (())]
94+
95+
我们再来看solution(3)，它可以用n=1和n=2拼接，以及通过n=2外层加上单独的括号得到所有答案：
96+
97+
solution(3) = [()()(), ()(()), (())(), (()()), ((()))]
98+
99+
前面3种是通过solution(2)和solution(1)拼接得到的，后面两种则是在solution(2)外面直接加上括号得到的，这种情况是无法通过拼接得到的情况。我们把这些情况全部汇总，然后去除掉重复的情况就是答案了。
100+
101+
这样我们就用小于n的所有结果构造出了n的结果，由于n=0 和n=1的情况是已知的。我们只需要把中间结果存储下来，通过递推就可以获取所有的答案。
102+
103+
### 动画描述
104+
105+
![](../Animation/0022-Generate_Parentheses.gif)
106+
107+
### 代码实现
108+
109+
```C++
110+
class Solution {
111+
public:
112+
113+
vector<string> generateParenthesis(int n) {
114+
// 存储所有中间结果
115+
map<int, set<string>> mp;
116+
set<string> st;
117+
st.insert("()");
118+
mp[1] = st;
119+
120+
for (int i = 2; i <= n; i++) {
121+
// 使用set来去重
122+
set<string> cur;
123+
for (int j = 1; j <= i-1; j++) {
124+
// 取出所有solution(j)和solution(i-j)
125+
set<string> vj = mp[j];
126+
set<string> vk = mp[i-j];
127+
for (string str:vj) {
128+
for (string stj : vk) {
129+
cur.insert(str + stj);
130+
}
131+
}
132+
}
133+
// solution(i-1)最外层套上括号
134+
set<string> vj = mp[i-1];
135+
for (string str : vj) {
136+
cur.insert("(" + str + ")");
137+
}
138+
// 得到solution(i)
139+
mp[i] = cur;
140+
}
141+
vector<string> vt;
142+
st = mp[n];
143+
for (string str : st) vt.push_back(str);
144+
return vt;
145+
}
146+
};
147+
```
148+
149+
![](../../Pictures/qrcode.jpg)

‎0024-Swap-Nodes-in-Pairs/Animation/0024-Swap-Nodes-in-Pairs-1.m4v

1.45 MB
Binary file not shown.

‎0024-Swap-Nodes-in-Pairs/Animation/0024-Swap-Nodes-in-Pairs-2.m4v

951 KB
Binary file not shown.

‎0024-Swap-Nodes-in-Pairs/Animation/Animation1.gif

4.68 MB
Loading

‎0024-Swap-Nodes-in-Pairs/Animation/Animation2.gif

2.43 MB
Loading

‎0024-Swap-Nodes-in-Pairs/Article/0024-Swap-Nodes-in-Pairs2.md

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
# LeetCode 第 24 号问题：两两交换链表中的节点
2+
3+
> 本文首发于公众号「图解面试算法」，是 [图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
4+
>
5+
> 同步博客：https://www.algomooc.com
6+
7+
题目来源于 LeetCode 上第 24 号问题：两两交换链表中的节点。
8+
9+
### 题目描述
10+
11+
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
12+
13+
**你不能只是单纯的改变节点内部的值**，而是需要实际的进行节点交换。
14+
15+
**示例:**
16+
17+
```
18+
给定 1->2->3->4, 你应该返回 2->1->4->3.
19+
```
20+
21+
### 题目解析 - 迭代法
22+
23+
由题目描述可知需要两两交换, 那么以两个为一组子链表交换指针即可, 在设置一个 **哨兵** 指向交换后的子链表 (或者哨兵提前指向子链表的第二个节点,因为第二个节点交换后就成了第一个节点); 然后让哨兵指向下一组子链表,继续交换,直至最后.
24+
25+
设 **哨兵** 为 节点 `prev`, 子链表第一个节点为 `A`, 第二个节点为 `B`, 第三个节点为 `C`, 那么操作流程如下:
26+
27+
- 终止条件 `head == null && head -> next == null`
28+
1. prev -> B ( A -> B -> C )
29+
2. A - > C
30+
3. B -> A ( prev -> B -> A -> C )
31+
4. prev -> A
32+
5. head -> C
33+
6. 循环以上步骤
34+
35+
### 动画描述
36+
37+
<img src="../Animation/Animation1.gif" alt="Animation1" style="zoom:150%;" />
38+
39+
### 代码实现
40+
41+
```javascript
42+
/**
43+
* JavaScript描述
44+
* 迭代法
45+
*/
46+
var swapPairs = function(head) {
47+
let dummy = new ListNode(0);
48+
dummy.next = head;
49+
50+
let prevNode = dummy;
51+
52+
while (head !== null && head.next !== null) {
53+
// Nodes to be swapped
54+
let firstNode = head,
55+
secondNode = head.next;
56+
// Swapping
57+
prevNode.next = secondNode; // 放到交换前后都可以
58+
firstNode.next = secondNode.next;
59+
secondNode.next = firstNode;
60+
// Reinitializing the head and prevNode for next swap
61+
prevNode = firstNode;
62+
head = firstNode.next;
63+
}
64+
return dummy.next;
65+
};
66+
```
67+
68+
### 复杂度分析
69+
70+
- 时间复杂度：**O(N)**，其中 *N* 指的是链表的节点数量
71+
- 空间复杂度：**O(1)**
72+
73+
### 题目解析 - 递归
74+
75+
递归的思路和迭代类似, 都是分组交换. 具体来说这里的递归不是针对一个问题深入进去,而是不断向后推进.
76+
77+
- 每次递归只交换一对节点
78+
- 下一次递归则是交换下一对节点
79+
- 交换完成后返回第二个节点, 因为它是交换后的子链表新头
80+
- 递归完成后返回第一次递归的第二个节点, 这就是新链表的头结点
81+
82+
**注意:** 不要人肉递归, 更多关注整体逻辑
83+
84+
示例执行大致流程为:
85+
86+
- 终止条件: `(head == null) || (head.next == null)`
87+
1. 1 -> 2 -> 3 -> 4 ( 原始链表 )
88+
2. 1 -> 3 -> 4
89+
3. ( 2 -> 1 ) -> 3 -> 4 ( 第一次递归完成后返回原来的第二个节点, 也就是值为 2 的节点 )
90+
4. 2 -> 1 -> 3 -> null
91+
5. 2 -> 1 -> ( 4 -> 3 ) ( 第二次递归完成后返回原来的第二个节点, 也就是值为 4 的节点 )
92+
93+
### 动画描述
94+
95+
<img src="../Animation/Animation2.gif" alt="Animation2" style="zoom:150%;" />
96+
97+
### 代码实现
98+
99+
```javascript
100+
/**
101+
* JavaScript描述
102+
* 递归法
103+
*/
104+
var swapPairs = function(head) {
105+
if (head == null || head.next == null) {
106+
return head;
107+
}
108+
// Nodes to be swapped
109+
let firstNode = head,
110+
secondNode = head.next;
111+
// Swapping
112+
firstNode.next = swapPairs(secondNode.next);
113+
secondNode.next = firstNode;
114+
115+
return secondNode;
116+
117+
};
118+
```
119+
120+
### 复杂度分析
121+
122+
- 时间复杂度：**O(N)**，其中 *N* 指的是链表的节点数量
123+
- 空间复杂度：**O(N)**, 递归过程使用的堆栈空间
124+
125+
126+
127+
![](../../Pictures/qrcode.jpg)
128+

‎0034-find-first-and-last-position-of-element-in-sorted-array/Animation/在排序数组中查找元素的第一个和最后一个位置.gif

6.52 MB
Loading

0 commit comments

Comments
 (0)