Skip to content

Commit c11ab1e

Browse files
chilimyanchilimyan
authored
Merge pull request MisterBooo#4 from MisterBooo/master
更新项目
2 parents 244bfaa + 62bcddc commit c11ab1e

File tree

33 files changed

+1083
-1
lines changed

33 files changed

+1083
-1
lines changed

‎0001-Two-Sum/Article/0001-Two-Sum.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,7 @@ public:
5757
5858
record[nums[i]] = i;
5959
}
60+
return {};
6061
}
6162
};
6263
@@ -66,4 +67,4 @@ public:
6667

6768

6869

69-
![](../../Pictures/qrcode.jpg)
70+
![](../../Pictures/qrcode.jpg)

‎0004-median-of-two-sorted-arrays/Animation/Animation.gif

3.93 MB
Loading

‎0004-median-of-two-sorted-arrays/Animation/case1.png

8.56 KB
Loading

‎0004-median-of-two-sorted-arrays/Animation/case2.png

8.88 KB
Loading

‎0004-median-of-two-sorted-arrays/Animation/case3.png

8.7 KB
Loading

‎0004-median-of-two-sorted-arrays/Animation/image1.PNG

16.7 KB
Loading

‎0004-median-of-two-sorted-arrays/Animation/image2.PNG

11.5 KB
Loading

‎0004-median-of-two-sorted-arrays/Article/0004-median-of-two-sorted-arrays.md

Lines changed: 151 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,151 @@
1+
# LeetCode 第 4 号问题：寻找两个正序数组的中位数
2+
3+
> 本文首发于公众号「图解面试算法」，是 [图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
4+
>
5+
> 同步博客：https://www.algomooc.com
6+
7+
题目来源于 LeetCode 上第 4 号问题：寻找两个正序数组的中位数。题目难度为 Hard，目前通过率为 29.0% 。
8+
9+
#### 题目描述
10+
11+
> 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
12+
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
13+
你可以假设 nums1 和 nums2 不会同时为空。
14+
15+
```java
16+
示例1：
17+
nums1 = [1, 3]
18+
nums2 = [2]
19+
20+
则中位数是 2.0
21+
22+
示例2：
23+
nums1 = [1, 2]
24+
nums2 = [3, 4]
25+
26+
则中位数是 (2 + 3)/2 = 2.5
27+
```
28+
29+
#### 题目解析
30+
这道题网络上的解析都非常“高深”，很难理解。私以为它们都将简单的问题复杂化了。本题在一些处理上确实会有些麻烦，比如数组边界的处理，和偶数个数的中位数的处理。但其核心思想并不复杂。
31+
32+
首先，我们可以只考虑数字总个数为奇数的情况。让我们看下下图：
33+
34+
![](../Animation/image1.PNG)
35+
36+
蓝框是中位数左边的数（包括中位数），而橘框则为中位数右边的数。
37+
38+
3个显然的规则：
39+
1.两个数组的蓝框总个数=(数字总个数+1)/2;
40+
2.所有蓝框内的数都小于橘框内的数
41+
3.中位数为蓝框中最大的那一位（即数组1蓝框最后一位，或数组2蓝框最后一位）
42+
![](../Animation/image2.PNG)
43+
如图，我们要找到一组A，B，满足上面3条规则。
44+
对于规则1，我们在数组1中找任意A，然后根据规则1就能推算出对应的B的位置。
45+
对于规则2，由于数组1和2都是有序数组，即X1<A<Y1;X2<B<Y2。我们实际上只需要判断A是否小于Y2，以及B是否小于Y2。
46+
对于规则3，由于数组1和2都是有序数组，因此中位数为A,B中较大的那一项。
47+
48+
那么具体该如何操作呢?
49+
由于数组1和2都是有序数组，且题目要求O(log(m+n))复杂度，我们明显应考虑二分法。
50+
51+
**情况1：**
52+
53+
![](../Animation/case1.png)
54+
55+
首先，我们选择数组1进行操作。取其中间值9 。（因此 A=9) 根据规则1,我们在数组2中找到对应值（B = 4）。（一共有11个数，(11+1) / 2 = 6，因此蓝色框总数为6）
56+
紧接着，我们根据规则2判断A(9)是否小于B.next(5)，以及B(4)是否小于A.next(11)。
57+
显然，A比B.next,也就是一个橘框还要大。这是不允许的。可见A只能取比9更小的数字了。如果取更大的数字，那B就会更小，更不可能满足规则2。所以这种情况下我们要向左进行二分。
58+
59+
**情况2：**
60+
61+
![](../Animation/case2.png)
62+
63+
这种情况下B比A.next,也就是一个橘框还要大。这是不允许的。可见A只能取比9更大的数字了。如果取更小的数字，那B就会更大，更不可能满足规则2。所以这种情况下我们要向右进行二分。
64+
65+
**情况3：**
66+
67+
![](../Animation/case3.png)
68+
69+
随着我们不断地二分，中位数显然必然会出现。
70+
如图上这种情况，A小于B.next，且B小于A.next。
71+
那么，显然，A,B中较大的那一项就是中位数（规则3）。
72+
73+
本题算法的核心思想就是这样简单。此外，当数字总数为偶数时，我们需要把我们求得的“中位数"与它下一项相加并除以2即可。由于本题中数字可能相同，所以大小的比较需要使用>=和<=。
74+
下面提供了作者的一份代码，leetcode上的结果为：执行用时：2 ms；内存消耗：40.3 MB，都超过了100%的用户。读者可以参考一下。
75+
76+
77+
#### 代码实现
78+
79+
Java语言
80+
81+
```java
82+
public class Solution {
83+
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
84+
// 使nums1成为较短数组,不仅可以提高检索速度,同时可以避免一些边界问题
85+
if (nums1.length > nums2.length) {
86+
int[] temp = nums1;
87+
nums1 = nums2;
88+
nums2 = temp;
89+
}
90+
91+
int len1 = nums1.length;
92+
int len2 = nums2.length;
93+
int leftLen = (len1 + len2 + 1) / 2; //两数组合并&排序后,左半边的长度
94+
95+
// 对数组1进行二分检索
96+
int start = 0;
97+
int end = len1;
98+
while (start <= end) {
99+
// 两个数组的被测数A,B的位置(从1开始计算)
100+
// count1 = 2 表示 num1 数组的第2个数字
101+
// 比index大1
102+
int count1 = start + ((end - start) / 2);
103+
int count2 = leftLen - count1;
104+
105+
if (count1 > 0 && nums1[count1 - 1] > nums2[count2]) {
106+
// A比B的next还要大
107+
end = count1 - 1;
108+
} else if (count1 < len1 && nums2[count2 - 1] > nums1[count1]) {
109+
// B比A的next还要大
110+
start = count1 + 1;
111+
} else {
112+
// 获取中位数
113+
int result = (count1 == 0)? nums2[count2 - 1]: // 当num1数组的数都在总数组右边
114+
(count2 == 0)? nums1[count1 - 1]: // 当num2数组的数都在总数组右边
115+
Math.max(nums1[count1 - 1], nums2[count2 - 1]); // 比较A,B
116+
if (isOdd(len1 + len2)) {
117+
return result;
118+
}
119+
120+
// 处理偶数个数的情况
121+
int nextValue = (count1 == len1) ? nums2[count2]:
122+
(count2 == len2) ? nums1[count1]:
123+
Math.min(nums1[count1], nums2[count2]);
124+
return (result + nextValue) / 2.0;
125+
}
126+
}
127+
128+
return Integer.MIN_VALUE; // 绝对到不了这里
129+
}
130+
131+
// 奇数返回true,偶数返回false
132+
private boolean isOdd(int x) {
133+
return (x & 1) == 1;
134+
}
135+
}
136+
```
137+
138+
#### 动画理解
139+
140+
![](../Animation/Animation.gif)
141+
142+
#### 复杂度分析
143+
144+
+ 时间复杂度：对数组进行二分查找，因此为O(logN)
145+
+ 空间复杂度：O(1)
146+
147+
148+
149+
150+
151+
![](../../Pictures/qrcode.jpg)

‎0004-median-of-two-sorted-arrays/Code/1.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
public class Solution {
2+
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3+
// 使nums1成为较短数组,不仅可以提高检索速度,同时可以避免一些边界问题
4+
if (nums1.length > nums2.length) {
5+
int[] temp = nums1;
6+
nums1 = nums2;
7+
nums2 = temp;
8+
}
9+
10+
int len1 = nums1.length;
11+
int len2 = nums2.length;
12+
int leftLen = (len1 + len2 + 1) / 2; //两数组合并&排序后,左半边的长度
13+
14+
// 对数组1进行二分检索
15+
int start = 0;
16+
int end = len1;
17+
while (start <= end) {
18+
// 两个数组的被测数A,B的位置(从1开始计算)
19+
// count1 = 2 表示 num1 数组的第2个数字
20+
// 比index大1
21+
int count1 = start + ((end - start) / 2);
22+
int count2 = leftLen - count1;
23+
24+
if (count1 > 0 && nums1[count1 - 1] > nums2[count2]) {
25+
// A比B的next还要大
26+
end = count1 - 1;
27+
} else if (count1 < len1 && nums2[count2 - 1] > nums1[count1]) {
28+
// B比A的next还要大
29+
start = count1 + 1;
30+
} else {
31+
// 获取中位数
32+
int result = (count1 == 0)? nums2[count2 - 1]: // 当num1数组的数都在总数组右边
33+
(count2 == 0)? nums1[count1 - 1]: // 当num2数组的数都在总数组右边
34+
Math.max(nums1[count1 - 1], nums2[count2 - 1]); // 比较A,B
35+
if (isOdd(len1 + len2)) {
36+
return result;
37+
}
38+
39+
// 处理偶数个数的情况
40+
int nextValue = (count1 == len1) ? nums2[count2]:
41+
(count2 == len2) ? nums1[count1]:
42+
Math.min(nums1[count1], nums2[count2]);
43+
return (result + nextValue) / 2.0;
44+
}
45+
}
46+
47+
return Integer.MIN_VALUE; // 绝对到不了这里
48+
}
49+
50+
// 奇数返回true,偶数返回false
51+
private boolean isOdd(int x) {
52+
return (x & 1) == 1;
53+
}
54+
}

‎0025-Reverse-Nodes-In-K-Group/Animation/0025-Reverse-Nodes-In-K-Group.m4v

2.26 MB
Binary file not shown.

‎0025-Reverse-Nodes-In-K-Group/Animation/Animation.gif

16.7 MB
Loading

‎0025-Reverse-Nodes-In-K-Group/Article/0025-Reverse-Nodes-In-K-Group.md

Lines changed: 169 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,169 @@
1+
# LeetCode 第 25 号问题：K 个一组翻转链表
2+
3+
> 本文首发于公众号「图解面试算法」，是 [图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
4+
>
5+
> 同步博客：https://www.algomooc.com
6+
7+
题目来源于 LeetCode 上第 25 号问题：K 个一组翻转链表。题目难度为 Hard
8+
9+
### 题目描述
10+
11+
给你一个链表，每 *k* 个节点一组进行翻转，请你返回翻转后的链表。
12+
13+
*k* 是一个正整数，它的值小于或等于链表的长度。
14+
15+
如果节点总数不是 *k* 的整数倍，那么请将最后剩余的节点保持原有顺序。
16+
17+
**示例:**
18+
19+
给你这个链表：`1->2->3->4->5`
20+
21+
当 *k* = 2 时，应当返回: `2->1->4->3->5`
22+
23+
当 *k* = 3 时，应当返回: `3->2->1->4->5`
24+
25+
**说明:**
26+
27+
- 你的算法只能使用常数的额外空间。
28+
- **你不能只是单纯的改变节点内部的值**，而是需要实际进行节点交换。
29+
30+
### 题目解析
31+
32+
这道算法题可以说是 [两两交换链表中的节点](https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0024-Swap-Nodes-in-Pairs/Article/0024-Swap-Nodes-in-Pairs2.md) 的升级版, 区别就是反转的子链表节点个数变成了自定义.
33+
34+
总体思路还是一样的, 具体可以分为两个处理模块:
35+
36+
1. 根据 *k* 划分若干个需要反转的子链表, 连接反转后的子链表, 最后不足 *k* 的子链表保持不变
37+
38+
- 设置哨兵 `dummy` 指向 `head` , 为了能找到反转后的链表头结点;
39+
40+
- 循环 *k* 确定需要 反转子链表 的范围:
41+
42+
- 循环完成, 确定子链表可以反转
43+
44+
假设 *A* , *B* 子链表邻接且都可以反转
45+
46+
- 指针 `start` 指向 *A* 的头结点, `end` 指向 *A* 的尾结点, `nxt` 指向 *B* 的头结点
47+
- `start -> end` 反转后, `start` 变成了 A 的尾结点, `start -> next = nxt` , 反转后的 *A* 链表指向了 *B*
48+
- 重置 `start` 为 *B* 的头节点, `end` 为 *B* 的尾结点, `nxt` 为下一个子链表头节点, 反转 *B* 链表
49+
- 重复上面动作, 知道 循环终止
50+
51+
- 循环终止, 剩余节点不足 *k* , 终止反转, 返回链表
52+
53+
2. 反转子链表
54+
55+
假设子链表前三个节点为 *a*, *b*, *c* ,设置指针 `pre`, `cur`, `nxt` , 初始化 `pre` 值为 `null`, `cur` 值为 *a* , `nxt` 值为 *a* , 这三个指针位置不变且相邻
56+
57+
终止条件: `cur` 不为空
58+
59+
将当前节点的指针指向上一个节点
60+
61+
1. `cur` 指向 `nxt` ( `nxt` 值为 *b* )
62+
2. `cur` 指向 `pre` ( `cur` 指向 `null` )
63+
3. `cur` 赋值给 `pre` ( `pre` 值为 *a* ) , `nxt` 赋值给 `cur` ( `cur` 值为 *b* )
64+
4. 在执行 步骤 `1` ( `nxt` 值为 *c* , 到此相当于 `pre`, `cur` , `nxt` 指向依次向后移动 `1` 位 )
65+
5. 重复上面动作
66+
67+
### 动画描述
68+
69+
<img src="../Animation/Animation.gif" alt="Animation" style="zoom:150%;" />
70+
71+
### 参考代码
72+
73+
#### 反转链表
74+
75+
```javascript
76+
/**
77+
* JavaScript 描述
78+
* 反转区间 [start, end) 的元素, 注意不包含 end
79+
*/
80+
function reverse(start, end) {
81+
let pre = null,
82+
cur = start,
83+
nxt = start;
84+
while (cur != end) {
85+
nxt = cur.next;
86+
// 逐个节点反转
87+
cur.next = pre;
88+
// 更新指针位置
89+
pre = cur;
90+
cur = nxt;
91+
}
92+
// 反转后的头结点, start 移到了最后, end 没有发生改变
93+
return pre;
94+
};
95+
```
96+
97+
#### 递归解法
98+
99+
```javascript
100+
/**
101+
* JavaScript 描述
102+
* 递归
103+
*/
104+
var reverseKGroup = function(head, k) {
105+
if (head == null) {
106+
return null;
107+
}
108+
let start, end;
109+
start = end = head;
110+
for (let i = 0; i < k; i++) {
111+
// 不足 k 个，不需要反转
112+
if (end == null) {
113+
return head;
114+
}
115+
end = end.next;
116+
}
117+
// 反转前 k 个元素, 不包含 end
118+
let reverseHead = reverse(start, end);
119+
// 递归反转后面k个元素 , 并前后连接起来
120+
start.next = reverseKGroup(end, k);
121+
return reverseHead;
122+
};
123+
```
124+
125+
#### 迭代解法
126+
127+
```javascript
128+
/**
129+
* JavaScript 描述
130+
* 迭代
131+
*/
132+
var reverseKGroup = function(head, k) {
133+
let dummy = new ListNode(0);
134+
dummy.next = head;
135+
let pre, start ,end, nxt;
136+
pre = start = end = nxt = dummy;
137+
while (end.next != null) {
138+
for (let i = 0; i < k && end != null; i++) {
139+
end = end.next;
140+
}
141+
if (end == null) {
142+
// 不足 k 个, 跳出循环
143+
break;
144+
}
145+
start = pre.next;
146+
nxt = end.next;
147+
// 反转前 k 个元素, 不包含 nxt
148+
pre.next = reverse(start, nxt);
149+
// 链接后面的链表
150+
start.next = nxt;
151+
// pre , end 重置到 下一个 k 子链表
152+
pre = start;
153+
end = pre;
154+
}
155+
return dummy.next;
156+
};
157+
```
158+
159+
### 复杂度分析
160+
161+
- 时间复杂度: **O( nk )** , 最好情况 O( n ), 最坏情况 O( n^2 )
162+
163+
- 空间复杂度: **O( 1 )**
164+
165+
166+
167+
168+
169+
![](../../Pictures/qrcode.jpg)

‎0120-Triangle/Animation/120.gif

3.6 MB
Loading

‎0120-Triangle/Animation/120.m4v

1.65 MB
Binary file not shown.

0 commit comments

Comments
 (0)