|
152 | 152 |
|
153 | 153 | #算法模板 |
154 | 154 |
|
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) |
395 | 156 |
|
396 | 157 | #LeetCode 最强题解: |
397 | 158 |
|
@@ -469,6 +230,7 @@ backtracking() { |
469 | 230 | |[0617.合并二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0617.合并二叉树.md)|树|简单|**递归****迭代**| |
470 | 231 | |[0637.二叉树的层平均值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0637.二叉树的层平均值.md)|树|简单|**广度优先搜索/队列**| |
471 | 232 | |[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)| 并查集/树/图|困难|**并查集**| |
472 | 234 | |[0700.二叉搜索树中的搜索](https://github.com/youngyangyang04/leetcode/blob/master/problems/0700.二叉搜索树中的搜索.md)|树|简单|**递归****迭代**| |
473 | 235 | |[0701.二叉搜索树中的插入操作](https://github.com/youngyangyang04/leetcode/blob/master/problems/0701.二叉搜索树中的插入操作.md)|树|简单|**递归****迭代**| |
474 | 236 | |[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md)|哈希表|简单|**模拟**| |
|