Myth

### LinkedHashMap `LinkedHashMap`继承于`HashMap`。 ```Java public class LinkedHashMap extends HashMap implements Map ``` 对于 `HashMap`而言，输出（遍历）结果并不是有序的，`LinkedHashMap` 是有序的，且默认为插入顺序。 `LinkedHashMap` 添加了一些指针，来进行排序

### TreeMap 底层是红黑树，有序的。 Map接口定义了使用equals()判定key是否相等，`SortedMap`却使用`compareTo()`来判断`key`是否相等(key.compareTo(anther)==0时相等)，而`TreeMap`是一种`SortedMap`，

## PriorityQueue 堆的正确使用是取出来堆顶（添加新元素），然后堆自动去调整时间复杂度为O(K) > K是堆的大小 ### 求Top K问题 ```Java for (int value : array) { if (maxHeap.size() < k) { maxHeap.add(value); } else if (maxHeap.peek() > value) { maxHeap.poll(); maxHeap.add(value);...

数左移一位就是乘以2，右移一位就是除以2，传说用位运算效率提高了60%。 乘2^k： n

## 递归，回溯和DFS的区别 递归是一种算法结构，回溯是一种算法思想 一个递归就是在函数中调用函数本身来解决问题 回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“**剪枝**”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。 回溯搜索是深度优先搜索（DFS）的一种对于某一个搜索树来说（搜索树是起**记录路径**和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。**回溯使用了DFS** `回溯 = DFS + Pruning` 其实本质上所有的搜索问题都可以看成一个树结构，DFS应用于典型的树结构，回溯应用于广义的树结构（棋盘问题，数独）

# 回溯算法的标准模板 **参数**：原始参数（题目必备的参数）、start（开始位置）， cur（当前答案）, ans（保存的所有答案） > Java中注意如果将当前答案添加到最终ans list时，要new一个新的对象 ```Java // 找到所有方案 void findSolutions(n, other params) { if (found a solution) { // 找到一个答案 // solutionsFound = solutionsFound + 1; addSolution();...

# Combination 组合 **相关题目**：17、22、39、40、77、216 典型的回溯算法，使用一个循环，一个一个去组合（注意从start开始，避免重复），然后递归进行，递归完，移除之前的操作（回溯） 关于重复元素问题（下面的排列、子集等问题也会遇到重复元素问题）的解决办法：先排序、然后在剪枝语句中添加 if( element[i] == element[i-1] ) continue;

## Permutation排列问题 **相关题目**：46、47、784、996 和Combination类似，只不过每一次的循环从 0开始

## SubSet问题 **相关题目：**78、90、842 和组合问题一致，只不过退出条件可能要添加一个size == 子集的数目，这么一个判断条件

## Partition 分割问题