Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitcfe3b6d

Browse files
Update
1 parent6741e45 commitcfe3b6d

File tree

4 files changed

+190
-69
lines changed

4 files changed

+190
-69
lines changed

‎README.md

Lines changed: 14 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -39,6 +39,7 @@
3939
*[哈希表：其实需要哈希的地方都能找到map的身影](https://mp.weixin.qq.com/s/Ue8pKKU5hw_m-jPgwlHcbA)
4040
*[哈希表：这道题目我做过？](https://mp.weixin.qq.com/s/sYZIR4dFBrw_lr3eJJnteQ)
4141
*[哈希表：解决了两数之和，那么能解决三数之和么？](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
42+
*[双指针法：一样的道理，能解决四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
4243
* 精选链表相关的面试题
4344
* 精选字符串相关的面试题
4445
* 精选栈与队列相关的面试题
@@ -65,18 +66,19 @@
6566
*[0203.移除链表元素](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)
6667
*[0707.设计链表](https://mp.weixin.qq.com/s/Cf95Lc6brKL4g2j8YyF3Mg)
6768
*[0206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
69+
*[面试题02.07.链表相交](https://github.com/youngyangyang04/leetcode/blob/master/problems/面试题02.07.链表相交.md)
6870
*[0142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
6971

7072
* 哈希表经典题目
7173
*[0242.有效的字母异位词](https://mp.weixin.qq.com/s/vM6OszkM6L1Mx2Ralm9Dig)
7274
*[0383.赎金信](https://mp.weixin.qq.com/s/sYZIR4dFBrw_lr3eJJnteQ)
7375
*[0575.分糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0575.分糖果.md)
74-
*[0349.两个数组的交集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0349.两个数组的交集.md)
76+
*[0349.两个数组的交集](https://mp.weixin.qq.com/s/N9iqAchXreSVW7zXUS4BVA)
7577
*[0202.快乐数](https://mp.weixin.qq.com/s/G4Q2Zfpfe706gLK7HpZHpA)
7678
*[0001.两数之和](https://mp.weixin.qq.com/s/uVAtjOHSeqymV8FeQbliJQ)
7779
*[0454.四数相加II](https://mp.weixin.qq.com/s/Ue8pKKU5hw_m-jPgwlHcbA)
78-
*[0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)
79-
*[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)
80+
*[0015.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
81+
*[0018.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
8082
*[0219.存在重复元素II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0219.存在重复元素II.md)
8183
* 0220.存在重复元素III
8284

@@ -89,6 +91,15 @@
8991
*[0028.实现strStr()](https://github.com/youngyangyang04/leetcode/blob/master/problems/0028.实现strStr().md)
9092
*[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)
9193

94+
* 双指针法经典题目
95+
*[0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)
96+
*[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)
97+
*[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
98+
*[0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)
99+
*[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)
100+
*[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
101+
*[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
102+
92103
* 栈与队列经典题目
93104
*[0232.用栈实现队列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0232.用栈实现队列.md)
94105
*[0225.用队列实现栈](https://github.com/youngyangyang04/leetcode/blob/master/problems/0225.用队列实现栈.md)

‎pics/332.重新安排行程.png

42.6 KB
Loading

‎problems/0027.移除元素.md

Lines changed: 52 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -4,25 +4,50 @@
44

55
https://leetcode-cn.com/problems/remove-element/
66

7+
>移除元素想要高效的话，不是很简单！
8+
9+
#编号：27. 移除元素
10+
11+
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
12+
13+
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并**原地**修改输入数组。
14+
15+
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
16+
17+
示例 1:
18+
给定 nums =[3,2,2,3], val = 3,
19+
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
20+
你不需要考虑数组中超出新长度后面的元素。
21+
22+
示例 2:
23+
给定 nums =[0,1,2,2,3,0,4,2], val = 2,
24+
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
25+
26+
**你不需要考虑数组中超出新长度后面的元素。**
27+
728
#思路
829

930
有的同学可能说了，多余的元素，删掉不就得了。
1031

11-
**要清楚数组的元素在内存地址中是连续的，数组中的元素是不能删掉的，只能覆盖。**
32+
**要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。**
33+
34+
数组的基础知识可以看这里[程序员算法面试中，必须掌握的数组理论知识](https://mp.weixin.qq.com/s/X7R55wSENyY62le0Fiawsg)。
1235

1336
#暴力解法
1437

1538
这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
1639

17-
如动画所示：
40+
删除过程如下：
1841

19-
<videosrc='../video/27.移除元素-暴力解法.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
42+
<imgsrc='../../World/Writing/leetcode/video/27.移除元素-暴力解法.gif'width=600> </img></div>
2043

2144
很明显暴力解法的时间复杂度是O(n^2)，这道题目暴力解法在leetcode上是可以过的。
2245

23-
代码如下：
46+
#暴力解法C++代码
2447

2548
```
49+
// 时间复杂度：O(n^2)
50+
// 空间复杂度：O(1)
2651
class Solution {
2752
public:
2853
int removeElement(vector<int>& nums, int val) {
@@ -33,7 +58,7 @@ public:
3358
nums[j - 1] = nums[j];
3459
}
3560
i--; // 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
36-
size--;// 此时数组的大小-1
61+
size--;// 此时数组的大小-1
3762
}
3863
}
3964
return size;
@@ -44,87 +69,48 @@ public:
4469

4570
#双指针法
4671

47-
双指针法（快慢指针法）：**说白了就是通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。**
72+
双指针法（快慢指针法）：**通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。**
4873

49-
先看一下动画理解一下：
74+
删除过程如下：
5075

76+
<imgsrc='../../World/Writing/leetcode/video/27.移除元素-双指针法.gif'width=600> </img></div>
5177

52-
<videosrc='../video/27.移除元素.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
78+
**双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。**
5379

54-
代码如下：
55-
```
56-
// 时间复杂度：O(n)
57-
// 空间复杂度：O(1)
58-
class Solution {
59-
public:
60-
int removeElement(vector<int>& nums, int val) {
61-
int slowIndex = 0; // index为 慢指针
62-
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) { // i 为快指针
63-
if (val != nums[fastIndex]) { //将快指针对应的数值赋值给慢指针对应的数值
64-
nums[slowIndex++] = nums[fastIndex]; 注意这里是slowIndex++ 而不是slowIndex--
65-
}
66-
}
67-
return slowIndex;
68-
}
69-
};
70-
```
80+
我们来回顾一下，之前已经讲过有四道题目使用了双指针法。
7181

72-
其实**双指针法（快慢指针法）在在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法，可以将时间复杂度O(n^2)的解法优化为 O(n)的解法，例如：**
82+
双指针法将时间复杂度O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：
7383

74-
*[0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)
75-
*[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)
76-
*[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
77-
*[0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)
78-
*[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
79-
*[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
84+
*[15.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
85+
*[18.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
8086

81-
**还有链表找环，也用到双指针：**
87+
双指针来记录前后指针实现链表反转：
8288

83-
*[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)
89+
*[206.反转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
8490

85-
大家都可以去做一做，感受一下双指针法的内在逻辑！
91+
使用双指针来确定有环：
8692

87-
#本题C++代码
88-
##暴力解法
93+
*[142题.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
8994

90-
时间复杂度：O(n^2)
91-
空间复杂度：O(1)
92-
```
93-
class Solution {
94-
public:
95-
int removeElement(vector<int>& nums, int val) {
96-
int size = nums.size();
97-
for (int i = 0; i < size; i++) {
98-
if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
99-
for (int j = i + 1; j < size; j++) {
100-
nums[j - 1] = nums[j];
101-
}
102-
i--; // 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
103-
size--;// 此时数组的大小-1
104-
}
105-
}
106-
return size;
107-
108-
}
109-
};
110-
```
95+
双指针法在数组和链表中还有很多应用，后面还会介绍到。
11196

112-
##双指针解法
113-
时间复杂度：O(n)
114-
空间复杂度：O(1)
97+
#双指针法C++代码：
11598
```
99+
// 时间复杂度：O(n)
100+
// 空间复杂度：O(1)
116101
class Solution {
117102
public:
118103
int removeElement(vector<int>& nums, int val) {
119-
int slowIndex = 0;// index为 慢指针
120-
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {// i 为快指针
121-
if (val != nums[fastIndex]) {//将快指针对应的数值赋值给慢指针对应的数值
122-
nums[slowIndex++] = nums[fastIndex];注意这里是slowIndex++ 而不是slowIndex--
104+
int slowIndex = 0;
105+
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
106+
if (val != nums[fastIndex]) {
107+
nums[slowIndex++] = nums[fastIndex];
123108
}
124109
}
125110
return slowIndex;
126111
}
127112
};
128113
```
129-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
114+
115+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
130116

‎problems/0332.重新安排行程.md

Lines changed: 124 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,124 @@
1+
2+
##题目地址
3+
4+
5+
6+
#第242题.有效的字母异位词
7+
8+
#思路
9+
10+
举一个有重复机场的例子：
11+
12+
<imgsrc='../pics/332.重新安排行程.png'width=600> </img></div>
13+
14+
为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，**如果在解题的过程中没有对集合元素处理好，就会死循环。**
15+
16+
这道题目有几个难点：
17+
18+
1. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
19+
2. 这是一个图不是一棵树，使用深搜/回溯 终止条件是什么呢？
20+
3. 回溯的过程中，如何遍历一个城市所对应的所有城市。
21+
22+
首先这道题目是使用回溯法（也可以说深搜），那么按照我总结的回溯模板来。
23+
24+
```
25+
backtracking() {
26+
if (终止条件) {
27+
存放结果;
28+
}
29+
30+
for (枚举同一个位置的所有可能性，可以想成节点孩子的数量) {
31+
递归，处理节点;
32+
backtracking();
33+
回溯，撤销处理结果
34+
}
35+
}
36+
```
37+
38+
##1. 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
39+
40+
一个城市映射多个城市，城市之间要靠字母序排列，一个城市映射多个城市，可以使用std::unordered_map，如果让多个城市之间再有顺序的话，就是用std::map 或者 或者std::multimap 或者 std::multiset。
41+
42+
如果对map 和 set 的实现机制不太了解，也不清楚为什么 map、multimap就是有序的同学，可以看这篇文章[关于哈希表，你该了解这些！](https://mp.weixin.qq.com/s/g8N6WmoQmsCUw3_BaWxHZA)。
43+
44+
这样存放映射关系可以定义为`unordered_map<string, multiset<string>> targets` 或者`unordered_map<string, map<string, int>> targets`。
45+
46+
含义如下：
47+
48+
`unordered_map<string, multiset<string>> targets`：`unordered_map<出发城市, 到达城市的集合> targets`
49+
`unordered_map<string, map<string, int>> targets`：`unordered_map<出发城市, map<到达城市, 航班次数>> targets`
50+
51+
这两个结构，我们选择了后者，因为如果使用`unordered_map<string, multiset<string>> targets` 遍历multiset的时候，不能删除元素，一旦删除元素，迭代器就失效了。而本地在回溯的过程中就是要不断的增删 multiset里的元素，所以 我们使用`unordered_map<string, map<string, int>> targets`。
52+
53+
在遍历`unordered_map<出发城市, map<到达城市, 航班次数>> targets`的过程中，可以使用航班次数这个字段的数字 --或者++，来标记到达城市是否使用过了，而不用对集合做删除元素或者增加元素的操作。
54+
55+
##2. 这是一个图不是一棵树，使用深搜/回溯 终止条件是什么呢？
56+
57+
你看有多少个航班，那题目中的示例为例，输入:[["MUC", "LHR"],["JFK", "MUC"],["SFO", "SJC"],["LHR", "SFO"]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。
58+
59+
所以终止条件 我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。
60+
61+
##3. 回溯的过程中，如何遍历一个城市所对应的所有城市。
62+
63+
这里刚刚说过，在选择映射函数的时候，不能选择`unordered_map<string, multiset<string>> targets`， 因为一旦有元素增删multiset的迭代器就会失效，有一些题解使用了 例如list的迭代器，使用splice来保证 迭代器不失效。
64+
65+
可以说既要找到一个对数据经行排序的容器，而且这个容易增删元素，迭代器还不能失效。
66+
67+
**再说一下为什么一定要增删元素呢，正如开篇我给出的图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除元素就会死循环。**
68+
69+
所以我选择了`unordered_map<string, map<string, int>> targets` 来基于映射条件。
70+
71+
遍历过程如下：
72+
73+
```
74+
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
75+
if (target.second > 0 ) {
76+
result.push_back(target.first);
77+
target.second--;
78+
if (backtracking(ticketNum, index + 1, result)) return true;
79+
result.pop_back();
80+
target.second++;
81+
}
82+
}
83+
```
84+
85+
可以看出 通过`unordered_map<string, map<string, int>> targets`里的int字段来判断 这个集合使用使用完了，这样避免了 增删元素。
86+
87+
此时完整代码如下：
88+
89+
#C++代码
90+
91+
```
92+
93+
class Solution {
94+
private:
95+
// unordered_map<出发城市, map<到达城市, 航班次数>> targets
96+
unordered_map<string, map<string, int>> targets;
97+
bool backtracking(int ticketNum, int index, vector<string>& result) {
98+
if (index == ticketNum + 1) {
99+
return true;
100+
}
101+
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
102+
if (target.second > 0 ) { // 使用int字段来记录到达城市是否使用过了
103+
result.push_back(target.first);
104+
target.second--;
105+
if (backtracking(ticketNum, index + 1, result)) return true;
106+
result.pop_back();
107+
target.second++;
108+
}
109+
}
110+
return false;
111+
}
112+
public:
113+
vector<string> findItinerary(vector<vector<string>>& tickets) {
114+
vector<string> result;
115+
for (const vector<string>& vec : tickets) {
116+
targets[vec[0]][vec[1]]++; // 记录映射关系
117+
}
118+
result.push_back("JFK");
119+
backtracking(tickets.size(), 1, result);
120+
return result;
121+
}
122+
};
123+
```
124+

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp