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

Commit3ee636e

Browse files
Update
1 parent8e3f6e8 commit3ee636e

File tree

9 files changed

+390
-6
lines changed

9 files changed

+390
-6
lines changed

‎README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -349,10 +349,14 @@ int countNodes(TreeNode* root) {
349349
|[0027.移除元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0027.移除元素.md)|数组|简单|**暴力****双指针/快慢指针/双指针**|
350350
|[0028.实现strStr()](https://github.com/youngyangyang04/leetcode/blob/master/problems/0028.实现strStr().md)|字符串|简单|**KMP**|
351351
|[0035.搜索插入位置](https://github.com/youngyangyang04/leetcode/blob/master/problems/0035.搜索插入位置.md)|数组|简单|**暴力****二分**|
352+
|[0039.组合总和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0039.组合总和.md)|数组/回溯|中等|**回溯**|
353+
|[0040.组合总和II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0040.组合总和II.md)|数组/回溯|中等|**回溯**|
352354
|[0046.全排列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0046.全排列.md)|回溯|中等|**回溯**|
353355
|[0047.全排列II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0047.全排列II.md)|回溯|中等|**回溯**|
354356
|[0053.最大子序和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0053.最大子序和.md)|数组|简单|**暴力****贪心** 动态规划 分治|
355357
|[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md)|数组|中等|**模拟**|
358+
|[0077.组合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0077.组合.md)|回溯|中等|**回溯**|
359+
|[0078.子集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0078.子集.md)|回溯/数组|中等|**回溯**|
356360
|[0083.删除排序链表中的重复元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0083.删除排序链表中的重复元素.md)|链表|简单|**模拟**|
357361
|[0093.复原IP地址](https://github.com/youngyangyang04/leetcode/blob/master/problems/0093.复原IP地址)|回溯|中等|**回溯**|
358362
|[0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md)|树|中等|**递归****迭代/栈**|
@@ -375,6 +379,7 @@ int countNodes(TreeNode* root) {
375379
|[0205.同构字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0205.同构字符串.md)|哈希表|简单|**哈希**|
376380
|[0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)|链表|简单|**双指针法****递归**|
377381
|[0209.长度最小的子数组](https://github.com/youngyangyang04/leetcode/blob/master/problems/0209.长度最小的子数组.md)|数组|中等|**暴力****滑动窗口**|
382+
|[0216.组合总和III](https://github.com/youngyangyang04/leetcode/blob/master/problems/0216.组合总和III.md)|数组/回溯|中等|**回溯**|
378383
|[0219.存在重复元素II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0219.存在重复元素II.md)| 哈希表|简单|**哈希**|
379384
|[0222.完全二叉树的节点个数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0222.完全二叉树的节点个数.md)| 树|简单|**递归**|
380385
|[0225.用队列实现栈](https://github.com/youngyangyang04/leetcode/blob/master/problems/0225.用队列实现栈.md)| 队列|简单|**队列**|

‎pics/90_子集 II.png

43.6 KB
Loading

‎problems/0001.两数之和.md

Lines changed: 56 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,67 @@
1-
##题目地址
1+
#题目地址
22
https://leetcode-cn.com/problems/two-sum/
33

4-
##思路
4+
>只用数组和set还是不够的！
5+
6+
#第1题. 两数之和
7+
8+
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
9+
10+
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
11+
12+
**示例:**
13+
14+
给定 nums =[2, 7, 11, 15], target = 9
15+
16+
因为 nums[0] + nums[1] = 2 + 7 = 9
17+
18+
所以返回[0, 1]
19+
20+
21+
#思路
522

623
很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。
7-
我们来看一下使用数组和set来做哈希法的局限。
24+
25+
使用哈希法最为合适，之前已经介绍过，数组和set在哈希法中的应用，那么来看一下使用数组和set来做哈希法的局限。
826

927
* 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
10-
* set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为我们要返回x 和 y的下表。所以set 也不能用。
28+
* set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为要返回x 和 y的下表。所以set 也不能用。
29+
30+
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下表。
31+
32+
C++中map，有三种类型：
33+
34+
|映射|底层实现| 是否有序|数值是否可以重复| 能否更改数值|查询效率|增删效率|
35+
|---|---| ---|---| ---| ---| ---|
36+
|std::map|红黑树|key有序|key不可重复|key不可修改| O(logn)|O(logn)|
37+
|std::multimap| 红黑树|key有序| key可重复| key不可修改|O(logn)|O(logn)|
38+
|std::unordered_map|哈希表| key无序|key不可重复|key不可修改|O(1)| O(1)|
39+
40+
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。
41+
42+
同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。 更多哈希表的理论知识请看[关于哈希表，你该了解这些！](https://mp.weixin.qq.com/s/g8N6WmoQmsCUw3_BaWxHZA)。
43+
44+
**这道题目中并不需要key有序，选择std::unordered_map 效率更高！**
1145

12-
此时我们就要选择一种数据结构 map ，map是一种key value的存储结构，我们可以用key保存数值，用value在保存数值所在的下表。
13-
这道题目是map在哈希法中的经典应用
46+
#C++代码
1447

48+
```
49+
class Solution {
50+
public:
51+
vector<int> twoSum(vector<int>& nums, int target) {
52+
std::unordered_map <int,int> map;
53+
for(int i = 0; i < nums.size(); i++) {
54+
auto iter = map.find(target - nums[i]);
55+
if(iter != map.end()) {
56+
return {iter->second, i};
57+
break;
58+
}
59+
map.insert(nums[i], i);
60+
}
61+
return {};
62+
}
63+
};
64+
```
1565

1666
##一般解法
1767

‎problems/0039.组合总和.md

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
#第39题. 组合总和
2+
3+
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
4+
5+
candidates 中的数字可以无限制重复被选取。
6+
7+
**说明：**
8+
9+
所有数字（包括 target）都是正整数。
10+
解集不能包含重复的组合。 
11+
12+
示例 1：
13+
14+
输入：candidates =[2,3,6,7], target = 7,
15+
所求解集为：
16+
[
17+
[7],
18+
[2,2,3]
19+
]
20+
21+
示例 2：
22+
23+
输入：candidates =[2,3,5], target = 8,
24+
所求解集为：
25+
[
26+
 [2,2,2,2],
27+
 [2,3,3],
28+
 [3,5]
29+
]
30+
31+
#思路
32+
33+
#C++代码
34+
35+
```
36+
// 无限制重复被选取。 吓得我赶紧想想 0 可咋办
37+
class Solution {
38+
private:
39+
vector<vector<int>> result;
40+
void backtracking(vector<int>& candidates, int target, vector<int>& vec, int sum, int startIndex) {
41+
if (sum > target) {
42+
return;
43+
}
44+
if (sum == target) {
45+
result.push_back(vec);
46+
return;
47+
}
48+
49+
// 因为可重复，所以我们从0开始， 这道题目感觉像是47.全排列II，其实不是
50+
for (int i = startIndex; i < candidates.size(); i++) {
51+
sum += candidates[i];
52+
vec.push_back(candidates[i]);
53+
backtracking(candidates, target, vec, sum, i); // 关键点在这里，不用i+1了
54+
sum -= candidates[i];
55+
vec.pop_back();
56+
57+
}
58+
}
59+
public:
60+
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
61+
vector<int> vec;
62+
backtracking(candidates, target, vec, 0, 0);
63+
return result;
64+
}
65+
};
66+
```

‎problems/0040.组合总和II.md

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
#第40题. 组合总和
2+
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
3+
4+
candidates 中的每个数字在每个组合中只能使用一次。
5+
6+
说明：
7+
8+
所有数字（包括目标数）都是正整数。
9+
解集不能包含重复的组合。 
10+
11+
示例 1:
12+
13+
输入: candidates = [10,1,2,7,6,1,5], target = 8,
14+
所求解集为:
15+
[
16+
[1, 7],
17+
[1, 2, 5],
18+
[2, 6],
19+
[1, 1, 6]
20+
]
21+
22+
示例 2:
23+
24+
输入: candidates = [2,5,2,1,2], target = 5,
25+
所求解集为:
26+
[
27+
 [1,2,2],
28+
 [5]
29+
]
30+
31+
#思想
32+
33+
#C++代码
34+
35+
```
36+
class Solution {
37+
private:
38+
vector<vector<int>> result;
39+
void backtracking(vector<int>& candidates, int target, vector<int>& vec, int sum, int startIndex, vector<bool>& used) {
40+
if (sum > target) {
41+
return;
42+
}
43+
if (sum == target) {
44+
result.push_back(vec);
45+
return;
46+
}
47+
48+
// 每个组合中只能使用一次 所以用 startindex
49+
// 给定一个数组 candidates 默认有重复项，解集不能包含重复的组合。 所以使用if这一套
50+
for (int i = startIndex; i < candidates.size(); i++) {
51+
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
52+
continue;
53+
}
54+
sum += candidates[i];
55+
vec.push_back(candidates[i]);
56+
used[i] = true;
57+
backtracking(candidates, target, vec, sum, i + 1, used); // 关键点在这里，不用i+1了
58+
used[i] = false;
59+
sum -= candidates[i];
60+
vec.pop_back();
61+
}
62+
}
63+
64+
public:
65+
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
66+
vector<int> vec;
67+
vector<bool> used(candidates.size(), false);
68+
sort(candidates.begin(), candidates.end());
69+
backtracking(candidates, target, vec, 0, 0, used);
70+
return result;
71+
72+
}
73+
};
74+
```

‎problems/0077.组合.md

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
#第77题. 组合
2+
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
3+
示例:
4+
5+
输入: n = 4, k = 2
6+
输出:
7+
[
8+
[2,4],
9+
[3,4],
10+
[2,3],
11+
[1,2],
12+
[1,3],
13+
[1,4],
14+
]
15+
16+
#思路
17+
18+
19+
#C++ 代码
20+
21+
```
22+
class Solution {
23+
private:
24+
vector<vector<int>> result;
25+
void backtracking(int n, int k, vector<int>& vec, int startIndex) {
26+
if (vec.size() == k) {
27+
result.push_back(vec);
28+
return;
29+
}
30+
// 这个for循环有讲究，组合的时候 要用startIndex，排列的时候就要从0开始
31+
// 这个过程好难理解，需要画图
32+
for (int i = startIndex; i <= n; i++) {
33+
vec.push_back(i);
34+
backtracking(n, k, vec, i + 1);
35+
vec.pop_back();
36+
}
37+
}
38+
public:
39+
40+
vector<vector<int>> combine(int n, int k) {
41+
vector<int> vec;
42+
backtracking(n, k, vec, 1);
43+
return result;
44+
}
45+
};
46+
```

‎problems/0078.子集.md

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
#题目地址
2+
3+
#第78题. 子集
4+
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
5+
6+
说明：解集不能包含重复的子集。
7+
8+
示例:
9+
10+
输入: nums =[1,2,3]
11+
输出:
12+
[
13+
[3],
14+
 [1],
15+
 [2],
16+
 [1,2,3],
17+
 [1,3],
18+
 [2,3],
19+
 [1,2],
20+
 []
21+
]
22+
23+
24+
#思路
25+
26+
27+
#C++代码
28+
29+
```
30+
31+
class Solution {
32+
private:
33+
void backtracking(vector<int>& nums, vector<vector<int>>& result, vector<int>& vec, int startIndex) {
34+
result.push_back(vec);
35+
for (int i = startIndex; i < nums.size(); i++) {
36+
vec.push_back(nums[i]);
37+
backtracking(nums, result, vec, i + 1);
38+
vec.pop_back();
39+
}
40+
}
41+
public:
42+
vector<vector<int>> subsets(vector<int>& nums) {
43+
vector<vector<int>> result;
44+
vector<int> vec;
45+
backtracking(nums, result, vec, 0);
46+
return result;
47+
}
48+
};
49+
```

‎problems/0090.子集II.md

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
#题目地址
2+
https://leetcode-cn.com/problems/subsets-ii/
3+
#第90题. 子集II
4+
5+
6+
#思路
7+
8+
9+
#C++代码
10+
11+
```
12+
class Solution {
13+
private:
14+
void backtracking(vector<int>& nums, vector<vector<int>>& result, vector<int>& vec, int startIndex, vector<bool>& used) {
15+
result.push_back(vec);
16+
for (int i = startIndex; i < nums.size(); i++) {
17+
if (i > 0 && nums[i] == nums[i - 1] && used[i-1] == false) { // 果然去重都是一个逻辑啊
18+
continue;
19+
}
20+
vec.push_back(nums[i]);
21+
used[i] = true;
22+
backtracking(nums, result, vec, i + 1, used);
23+
used[i] = false;
24+
vec.pop_back();
25+
}
26+
}
27+
28+
public:
29+
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
30+
vector<bool> used(nums.size(), false);
31+
vector<vector<int>> result;
32+
vector<int> vec;
33+
sort(nums.begin(), nums.end());
34+
backtracking(nums, result, vec, 0, used);
35+
return result;
36+
}
37+
};
38+
```

0 commit comments

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