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

Commit96f7558

Browse files
Update
1 parent6cc132a commit96f7558

7 files changed

+155
-30
lines changed
115 KB
Loading

‎pics/491. 递增子序列2.png

42.8 KB
Loading

‎pics/491. 递增子序列3.png

43.1 KB
Loading

‎problems/0017.电话号码的字母组合.md

Lines changed: 45 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,58 @@
11

22

33
##题目地址
4+
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
45

56
##思路
67

8+
本题要解决如下问题：
79

810
1. 数字和字母如何映射
911
2. 两个字母我就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
10-
3. 如何排列组合呢
11-
4. 1 * # 等等情况
12+
3. 输入1 * #按键等等异常情况
1213

13-
树形结构啊
14+
接下来一一解决这几个问题。
15+
16+
17+
1. 数字和字母如何映射
18+
19+
定义一个二位数组，例如：string letterMap[10]，来做映射
20+
21+
2. 两个字母我就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来。
22+
23+
**遇到这种情况，就应该想到回溯了。**
24+
25+
这是一个回溯法的经典题目，**不要以为回溯是一个性能很高的算法，回溯其实就是暴力枚举，纯暴力，搜出所有的可能性。**
26+
27+
回溯一般都伴随着递归，而这种组合问题，都可以画成一个树形结构。如图所示：
28+
29+
<imgsrc='../pics/17. 电话号码的字母组合.jpeg'width=600> </img></div>
30+
31+
可以想成遍历这棵树，然后把叶子节点都保存下来。
32+
33+
34+
3. 输入1 * #按键等等异常情况
35+
36+
题目的测试数据中应该没有异常情况的数据，可以不考虑，但是要知道会有这些异常。
37+
38+
39+
**那么在来讲一讲回溯法，回溯法的模板如下：**
40+
41+
```
42+
回溯函数() {
43+
if (终止条件) {
44+
存放结果;
45+
}
46+
47+
for (枚举同一个位置的所有可能性，可以想成节点孩子的数量) {
48+
递归，处理下一个孩子;
49+
(递归的下面就是回溯的过程);
50+
}
51+
}
52+
53+
```
54+
55+
按照这个模板，不难写出如下代码：
1456

1557
##C++代码
1658

‎problems/0035.搜索插入位置.md

Lines changed: 64 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,35 @@
22

33
https://leetcode-cn.com/problems/search-insert-position/
44

5+
>二分查找法是数组里的常用方法，彻底掌握它是十分必要的。
6+
7+
#编号35：搜索插入位置
8+
9+
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
10+
11+
你可以假设数组中无重复元素。
12+
13+
示例 1:
14+
输入:[1,3,5,6], 5
15+
输出: 2
16+
17+
示例 2:
18+
输入:[1,3,5,6], 2
19+
输出: 1
20+
21+
示例 3:
22+
输入:[1,3,5,6], 7
23+
输出: 4
24+
25+
示例 4:
26+
输入:[1,3,5,6], 0
27+
输出: 0
28+
529
#思路
630

7-
这道题目其实是一道很简单的题，但是为什么通过率相对来说并不高呢，我理解是大家对 边界处理的判断有所失误，导致的。
31+
这道题目不难，但是为什么通过率相对来说并不高呢，我理解是大家对边界处理的判断有所失误导致的。
832

9-
这道题目，我们要在数组中插入目标值，无非是这四种情况
33+
这道题目，要在数组中插入目标值，无非是这四种情况。
1034

1135
<imgsrc='../pics/35_搜索插入位置3.png'width=600> </img></div>
1236

@@ -15,14 +39,15 @@ https://leetcode-cn.com/problems/search-insert-position/
1539
* 目标值插入数组中的位置
1640
* 目标值在数组所有元素之后
1741

18-
这四种情况确认清楚了，我们就可以尝试解题了
42+
这四种情况确认清楚了，就可以尝试解题了。
1943

20-
暴力解题 不一定时间消耗就非常高，关键看实现的方式，就像是二分查找时间消耗不一定就很低，是一样的。
44+
接下来我将从暴力的解法和二分法来讲解此题，也借此好好讲一讲二分查找法。
2145

22-
这里我给出了一种简洁的暴力解法，和两种二分查找的解法
46+
##暴力解法
2347

48+
暴力解题 不一定时间消耗就非常高，关键看实现的方式，就像是二分查找时间消耗不一定就很低，是一样的。
2449

25-
#解法:暴力枚举
50+
##暴力解法C++代码
2651

2752
```
2853
class Solution {
@@ -42,50 +67,55 @@ public:
4267
}
4368
};
4469
```
45-
效率如下：
46-
<imgsrc='../pics/35_搜索插入位置.png'width=600> </img></div>
4770

48-
时间复杂度：O(n)
71+
时间复杂度：O(n)
4972
时间复杂度：O(1)
5073

74+
效率如下：
75+
76+
<imgsrc='../pics/35_搜索插入位置.png'width=600> </img></div>
5177

52-
#二分法
78+
##二分法
5379

54-
既然暴力解法的时间复杂度是On，我们就要尝试一下使用二分查找法。
80+
既然暴力解法的时间复杂度是O(n)，就要尝试一下使用二分查找法。
5581

5682
<imgsrc='../pics/35_搜索插入位置4.png'width=600> </img></div>
5783

58-
大家注意这道题目的前提是数组是有序数组，这也是使用二分查找的基础条件
84+
大家注意这道题目的前提是数组是有序数组，这也是使用二分查找的基础条件。
5985

6086
以后大家**只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法。**
6187

6288
同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下表可能不是唯一的。
6389

64-
大体讲解一下二分法的思路，这里来举一个例子，例如在这个数组中，我们使用二分法寻找元素为5的位置，并返回其下标
90+
大体讲解一下二分法的思路，这里来举一个例子，例如在这个数组中，使用二分法寻找元素为5的位置，并返回其下标。
6591

6692
<imgsrc='../pics/35_搜索插入位置5.png'width=600> </img></div>
6793

68-
二分查找涉及的很多的边界条件，逻辑比较简单，就是写不好
94+
二分查找涉及的很多的边界条件，逻辑比较简单，就是写不好。
95+
96+
相信很多同学对二分查找法中边界条件处理不好。
6997

70-
相信很多同学对二分查找法中边界条件处理不好，例如 到底是 小于还是小于等于，到底是+1呢，还是要-1呢
98+
例如到底是`while(left < right)`还是`while(left <= right)`，到底是`right = middle`呢，还是要`right = middle - 1`呢？
7199

72-
这是为什么呢，主要是**我们对区间的定义没有想清楚，这就是我们的不变量**
100+
这里弄不清楚主要是因为**对区间的定义没有想清楚，这就是不变量**。
73101

74-
我们要在二分查找的过程中，保持不变量，这也就是**循环不变量** （感兴趣的同学可以查一查）
102+
要在二分查找的过程中，保持不变量，这也就是**循环不变量** （感兴趣的同学可以查一查）。
75103

76104
##二分法第一种写法
77105

78-
以这道题目来举例，以下的代码中我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
106+
以这道题目来举例，以下的代码中定义 target 是在一个在左闭右闭的区间里，**也就是[left, right] （这个很重要）**。
107+
108+
这就决定了这个二分法的代码如何去写，大家看如下代码：
79109

80-
这就决定了我们 这个二分法的代码如何去写，大家看如下代码
110+
**大家要仔细看注释，思考为什么要写while(left <= right)， 为什么要写right = middle - 1**。
81111

82112
```
83113
class Solution {
84114
public:
85115
int searchInsert(vector<int>& nums, int target) {
86116
int n = nums.size();
87117
int left = 0;
88-
int right = n - 1; //我们定义target在左闭右闭的区间里，[left, right]
118+
int right = n - 1; //定义target在左闭右闭的区间里，[left, right]
89119
while (left <= right) { // 当left==right，区间[left, right]依然有效
90120
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
91121
if (nums[middle] > target) {
@@ -105,27 +135,29 @@ public:
105135
}
106136
};
107137
```
108-
时间复杂度：O(logn)
138+
时间复杂度：O(logn)
109139
时间复杂度：O(1)
110140

111141
效率如下：
112142
<imgsrc='../pics/35_搜索插入位置2.png'width=600> </img></div>
113143

114144
##二分法第二种写法
115145

116-
如果说我们定义 target 是在一个在左闭右开的区间里，也就是[left, right)
146+
如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right)。
117147

118148
那么二分法的边界处理方式则截然不同。
119149

120150
不变量是[left, right)的区间，如下代码可以看出是如何在循环中坚持不变量的。
121151

152+
**大家要仔细看注释，思考为什么要写while (left < right)， 为什么要写right = middle**。
153+
122154
```
123155
class Solution {
124156
public:
125157
int searchInsert(vector<int>& nums, int target) {
126158
int n = nums.size();
127159
int left = 0;
128-
int right = n; //我们定义target在左闭右开的区间里，[left, right) target
160+
int right = n; //定义target在左闭右开的区间里，[left, right) target
129161
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
130162
int middle = left + ((right - left) >> 1);
131163
if (nums[middle] > target) {
@@ -146,11 +178,17 @@ public:
146178
};
147179
```
148180

149-
时间复杂度：O(logn)
181+
时间复杂度：O(logn)
150182
时间复杂度：O(1)
151183

152-
##总结
153-
希望通过这道题目 ，可以帮助大家对二分法有更深的理解
184+
#总结
185+
186+
希望通过这道题目，大家会发现平时写二分法，为什么总写不好，就是因为对区间定义不清楚。
187+
188+
确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。
189+
190+
然后在**二分查找的循环中，坚持循环不变量的原则**，很多细节问题，自然会知道如何处理了。
191+
154192

155193
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
156194

‎problems/0222.完全二叉树的节点个数.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,6 @@ public:
3434
int countNodes(TreeNode* root) {
3535
queue<TreeNode*> que;
3636
if (root != NULL) que.push(root);
37-
int count = 0;
3837
int result = 0;
3938
while (!que.empty()) {
4039
int size = que.size();

‎problems/0491.递增子序列.md

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,3 +40,49 @@ public:
4040
}
4141
};
4242
```
43+
44+
一位师弟在评论中对代码进行了改进，效率确实高了很多，优化后如图：
45+
46+
<imgsrc='../pics/491. 递增子序列2.png'width=600> </img></div>
47+
48+
改动的地方主要是将去重的逻辑中把 unordered_set 改成了 数组。
49+
50+
用数组替换unordered_set 确实可以快很多，unordered_set底层符号表也是哈希表，理论上不应该差多少。
51+
52+
估计程序运行的时候对unordered_set 频繁的insert，unordered_set需要做哈希映射（也就是把key通过hash function映射为唯一的哈希值）费了些时间。
53+
54+
用数组来做哈希，效率就高了很多，再加上题目中也说了，数值范围[-100,100]，所以用数组正合适。
55+
56+
**这个事实告诉我们，使用哈希法的时候，条件允许的话，能用数组尽量用数组。**
57+
58+
优化后的代码如下：
59+
60+
```
61+
class Solution {
62+
private:
63+
void backtracking(vector<int>& nums, vector<vector<int>>& result, vector<int>& subseq, int startIndex) {
64+
if (subseq.size() > 1) {
65+
result.push_back(subseq);
66+
// 注意这里不要加return，因为要取所有的可能
67+
}
68+
int hash[201] = {0}; // 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
69+
for (int i = startIndex; i < nums.size(); i++) {
70+
if ((subseq.empty() || nums[i] >= subseq.back())
71+
&& hash[nums[i] + 100] == 0) {
72+
subseq.push_back(nums[i]);
73+
backtracking(nums, result, subseq, i + 1);
74+
subseq.pop_back();
75+
hash[nums[i]+100] = 1;
76+
}
77+
}
78+
}
79+
public:
80+
vector<vector<int>> findSubsequences(vector<int>& nums) {
81+
vector<vector<int>> result;
82+
vector<int> subseq;
83+
backtracking(nums, result, subseq, 0);
84+
return result;
85+
}
86+
};
87+
88+
```

0 commit comments

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