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

Commitc761b59

Browse files
Update
1 parent634dcfb commitc761b59

24 files changed

+787
-287
lines changed

‎README.md

Lines changed: 2 additions & 240 deletions
Original file line numberDiff line numberDiff line change
@@ -152,246 +152,7 @@
152152

153153
#算法模板
154154

155-
##二分查找法
156-
157-
```
158-
class Solution {
159-
public:
160-
int searchInsert(vector<int>& nums, int target) {
161-
int n = nums.size();
162-
int left = 0;
163-
int right = n; // 我们定义target在左闭右开的区间里，[left, right)
164-
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
165-
int middle = left + ((right - left) >> 1);
166-
if (nums[middle] > target) {
167-
right = middle; // target 在左区间，因为是左闭右开的区间，nums[middle]一定不是我们的目标值，所以right = middle，在[left, middle)中继续寻找目标值
168-
} else if (nums[middle] < target) {
169-
left = middle + 1; // target 在右区间，在 [middle+1, right)中
170-
} else { // nums[middle] == target
171-
return middle; // 数组中找到目标值的情况，直接返回下标
172-
}
173-
}
174-
return right;
175-
}
176-
};
177-
178-
```
179-
180-
##KMP
181-
182-
```
183-
void kmp(int* next, const string& s){
184-
next[0] = -1;
185-
int j = -1;
186-
for(int i = 1; i < s.size(); i++){
187-
while (j >= 0 && s[i] != s[j + 1]) {
188-
j = next[j];
189-
}
190-
if (s[i] == s[j + 1]) {
191-
j++;
192-
}
193-
next[i] = j;
194-
}
195-
}
196-
```
197-
198-
##二叉树
199-
200-
二叉树的定义：
201-
202-
```
203-
struct TreeNode {
204-
int val;
205-
TreeNode *left;
206-
TreeNode *right;
207-
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
208-
};
209-
```
210-
211-
###深度优先遍历（递归）
212-
213-
前序遍历（中左右）
214-
```
215-
void traversal(TreeNode* cur, vector<int>& vec) {
216-
if (cur == NULL) return;
217-
vec.push_back(cur->val); // 中 ，同时也是处理节点逻辑的地方
218-
traversal(cur->left, vec); // 左
219-
traversal(cur->right, vec); // 右
220-
}
221-
```
222-
中序遍历（左中右）
223-
```
224-
void traversal(TreeNode* cur, vector<int>& vec) {
225-
if (cur == NULL) return;
226-
traversal(cur->left, vec); // 左
227-
vec.push_back(cur->val); // 中 ，同时也是处理节点逻辑的地方
228-
traversal(cur->right, vec); // 右
229-
}
230-
```
231-
中序遍历（中左右）
232-
```
233-
void traversal(TreeNode* cur, vector<int>& vec) {
234-
if (cur == NULL) return;
235-
vec.push_back(cur->val); // 中 ，同时也是处理节点逻辑的地方
236-
traversal(cur->left, vec); // 左
237-
traversal(cur->right, vec); // 右
238-
}
239-
```
240-
241-
###深度优先遍历（迭代法）
242-
243-
相关题解：[0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md)
244-
245-
前序遍历（中左右）
246-
```
247-
vector<int> preorderTraversal(TreeNode* root) {
248-
vector<int> result;
249-
stack<TreeNode*> st;
250-
if (root != NULL) st.push(root);
251-
while (!st.empty()) {
252-
TreeNode* node = st.top();
253-
if (node != NULL) {
254-
st.pop();
255-
if (node->right) st.push(node->right); // 右
256-
if (node->left) st.push(node->left); // 左
257-
st.push(node); // 中
258-
st.push(NULL);
259-
} else {
260-
st.pop();
261-
node = st.top();
262-
st.pop();
263-
result.push_back(node->val); // 节点处理逻辑
264-
}
265-
}
266-
return result;
267-
}
268-
269-
```
270-
271-
中序遍历（左中右）
272-
```
273-
vector<int> inorderTraversal(TreeNode* root) {
274-
vector<int> result; // 存放中序遍历的元素
275-
stack<TreeNode*> st;
276-
if (root != NULL) st.push(root);
277-
while (!st.empty()) {
278-
TreeNode* node = st.top();
279-
if (node != NULL) {
280-
st.pop();
281-
if (node->right) st.push(node->right); // 右
282-
st.push(node); // 中
283-
st.push(NULL);
284-
if (node->left) st.push(node->left); // 左
285-
} else {
286-
st.pop();
287-
node = st.top();
288-
st.pop();
289-
result.push_back(node->val); // 节点处理逻辑
290-
}
291-
}
292-
return result;
293-
}
294-
```
295-
296-
后序遍历（左右中）
297-
```
298-
vector<int> postorderTraversal(TreeNode* root) {
299-
vector<int> result;
300-
stack<TreeNode*> st;
301-
if (root != NULL) st.push(root);
302-
while (!st.empty()) {
303-
TreeNode* node = st.top();
304-
if (node != NULL) {
305-
st.pop();
306-
st.push(node); // 中
307-
st.push(NULL);
308-
if (node->right) st.push(node->right); // 右
309-
if (node->left) st.push(node->left); // 左
310-
311-
} else {
312-
st.pop();
313-
node = st.top();
314-
st.pop();
315-
result.push_back(node->val); // 节点处理逻辑
316-
}
317-
}
318-
return result;
319-
}
320-
```
321-
###广度优先遍历（队列）
322-
323-
相关题解：[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)
324-
325-
```
326-
vector<vector<int>> levelOrder(TreeNode* root) {
327-
queue<TreeNode*> que;
328-
if (root != NULL) que.push(root);
329-
vector<vector<int>> result;
330-
while (!que.empty()) {
331-
int size = que.size();
332-
vector<int> vec;
333-
for (int i = 0; i < size; i++) {// 这里一定要使用固定大小size，不要使用que.size()
334-
TreeNode* node = que.front();
335-
que.pop();
336-
vec.push_back(node->val); // 节点处理的逻辑
337-
if (node->left) que.push(node->left);
338-
if (node->right) que.push(node->right);
339-
}
340-
result.push_back(vec);
341-
}
342-
return result;
343-
}
344-
345-
```
346-
347-
348-
349-
可以直接解决如下题目：
350-
351-
*[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)
352-
*[0199.二叉树的右视图](https://github.com/youngyangyang04/leetcode/blob/master/problems/0199.二叉树的右视图.md)
353-
*[0637.二叉树的层平均值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0637.二叉树的层平均值.md)
354-
*[0104.二叉树的最大深度 （迭代法）](https://github.com/youngyangyang04/leetcode/blob/master/problems/0104.二叉树的最大深度.md)
355-
356-
*[0111.二叉树的最小深度（迭代法）]((https://github.com/youngyangyang04/leetcode/blob/master/problems/0111.二叉树的最小深度.md))
357-
*[0222.完全二叉树的节点个数（迭代法）](https://github.com/youngyangyang04/leetcode/blob/master/problems/0222.完全二叉树的节点个数.md)
358-
359-
###二叉树深度
360-
361-
```
362-
int getDepth(TreeNode* node) {
363-
if (node == NULL) return 0;
364-
return 1 + max(getDepth(node->left), getDepth(node->right));
365-
}
366-
```
367-
368-
###二叉树节点数量
369-
370-
```
371-
int countNodes(TreeNode* root) {
372-
if (root == NULL) return 0;
373-
return 1 + countNodes(root->left) + countNodes(root->right);
374-
}
375-
```
376-
377-
##回溯算法
378-
379-
```
380-
backtracking() {
381-
if (终止条件) {
382-
存放结果;
383-
}
384-
385-
for (选择：选择列表（可以想成树中节点孩子的数量）) {
386-
递归，处理节点;
387-
backtracking();
388-
回溯，撤销处理结果
389-
}
390-
}
391-
392-
```
393-
394-
（持续补充ing）
155+
[各类基础算法模板](https://github.com/youngyangyang04/leetcode/blob/master/problems/算法模板.md)
395156

396157
#LeetCode 最强题解:
397158

@@ -469,6 +230,7 @@ backtracking() {
469230
|[0617.合并二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0617.合并二叉树.md)|树|简单|**递归****迭代**|
470231
|[0637.二叉树的层平均值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0637.二叉树的层平均值.md)|树|简单|**广度优先搜索/队列**|
471232
|[0654.最大二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0654.最大二叉树.md)|树|中等|**递归**|
233+
|[0685.冗余连接II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0685.冗余连接II.md)| 并查集/树/图|困难|**并查集**|
472234
|[0700.二叉搜索树中的搜索](https://github.com/youngyangyang04/leetcode/blob/master/problems/0700.二叉搜索树中的搜索.md)|树|简单|**递归****迭代**|
473235
|[0701.二叉搜索树中的插入操作](https://github.com/youngyangyang04/leetcode/blob/master/problems/0701.二叉搜索树中的插入操作.md)|树|简单|**递归****迭代**|
474236
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md)|哈希表|简单|**模拟**|

‎pics/239.滑动窗口最大值.png

46.6 KB
Loading

‎pics/347.前K个高频元素.png

65 KB
Loading

‎pics/47.全排列II1.png

263 KB
Loading

‎pics/47.全排列II2.png

210 KB
Loading

‎pics/47.全排列II3.png

258 KB
Loading

‎pics/685.冗余连接II1.png

91 KB
Loading

‎pics/685.冗余连接II2.png

62.6 KB
Loading

‎pics/78.子集.png

149 KB
Loading

‎pics/90.子集II.png

235 KB
Loading

‎problems/0047.全排列II.md

Lines changed: 65 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,9 +3,31 @@ https://leetcode-cn.com/problems/permutations-ii/
33

44
##思路
55

6-
i > 0 && nums[i] == nums[i-1] && used[i-1] == false
6+
这道题目和46.全排列的区别在与**给定一个可包含重复数字的序列**，要返回**所有不重复的全排列**。
77

8-
这是最高效的，可以用 1 1 1 1 1 跑一个样例试试
8+
这里就涉及到去重了。
9+
10+
要注意**全排列是要取树的子节点的，如果是子集问题，就取树上的所有节点。**
11+
12+
很多同学在去重上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。
13+
14+
这个去重为什么很难理解呢，**所谓去重，其实就是使用过的元素不能重复选取。** 这么一说好像很简单！
15+
16+
但是什么又是“使用过”，我们把排列问题抽象为树形结构之后，**“使用过”在这个树形结构上是有两个维度的**，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。
17+
18+
**没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。**
19+
20+
那么排列问题，既可以在 同一树层上的“使用过”来去重，也可以在同一树枝上的“使用过”来去重！
21+
22+
理解这一本质，很多疑点就迎刃而解了。
23+
24+
首先把示例中的[1,1,2]，抽象为一棵树，然后在同一树层上对nums[i-1]使用过的话，进行去重如图：
25+
26+
<imgsrc='../pics/47.全排列II1.png'width=600> </img></div>
27+
28+
图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
29+
30+
代码如下：
931

1032
##C++代码
1133

@@ -21,7 +43,11 @@ private:
2143
}
2244
2345
for (int i = 0; i < nums.size(); i++) {
24-
if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) {
46+
// 这里理解used[i - 1]非常重要
47+
// used[i - 1] == true，说明同一树支nums[i - 1]使用过
48+
// used[i - 1] == false，说明同一树层nums[i - 1]使用过
49+
// 如果同一树层nums[i - 1]使用过则直接跳过
50+
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
2551
continue;
2652
}
2753
if (used[i] == false) {
@@ -45,3 +71,39 @@ public:
4571
}
4672
};
4773
```
74+
75+
##拓展
76+
77+
大家发现，去重最为关键的代码为：
78+
79+
```
80+
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
81+
continue;
82+
}
83+
```
84+
85+
可是如果把`used[i - 1] == true` 也是正确的，去重代码如下：
86+
```
87+
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
88+
continue;
89+
}
90+
```
91+
92+
这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用`used[i - 1] == false`，如果要对树枝前一位去重用用`used[i - 1] == true`。
93+
94+
**对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！**
95+
96+
这么说是不是有点抽象？
97+
98+
来来来，我就用输入:[1,1,1] 来举一个例子。
99+
100+
树层上去重(used[i - 1] == false)，的树形结构如下：
101+
102+
<imgsrc='../pics/47.全排列II2.png'width=600> </img></div>
103+
104+
树枝上去重（used[i - 1] == true）的树型结构如下：
105+
106+
<imgsrc='../pics/47.全排列II3.png'width=600> </img></div>
107+
108+
大家应该很清晰的看到，树层上去重非常彻底，效率很高，树枝上去重虽然最后可能得到答案，但是多做了很多无用搜索。
109+

0 commit comments

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