深度优先搜索是指将每条路径直接走到底，当该条路径遍历完都没有找到目标结果时，在换另一条，直到找到。有种不撞南墙不回头的意思。其实现一般是递归，当然栈也可以，但是多用递归。

广度优先搜索是指按照波纹扩散的方式将对每条路的下一层节点进行遍历，直到找到目标节点。我感觉实际中推荐用BFS，因为DFS当数据量太大时很可能带来较高的时间复杂度。实现一般是队列。

双向BFS指的是在BFS的基础上进行优化，常规BFS是从起点到终点扩散，而双向BFS是从起点和终点同时向中间扩散，且每次优先用节点少的那端扩散，当起点和终点直接深度很深的时候，双向BFS能比常规BFS快很多。双向BFS在代码实现的时候就不是用queue而是用两个set去遍历了。

在计算的每个阶段都得到最优解，从而得到全局的最优解，它可以说是动态规划的一种特殊情况，即每个阶段的解刚好就是它自己，没有额外的回退或者转换。**贪心算法**比较麻烦的是你能证明或者想到这个题能用贪心解，当你知道能用贪心解，其代码实现一般是比较简单的，主要是判定和证明比较麻烦。

二分查找试用数据集有三个特性：

1. 单调性

2. 有上下边界

3. 能通过下标快速访问

常规模板如下：

public int binarySearch(int[] nums,int target){

int left = 0, right = nums.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (nums[mid]==target) {

return mid;

} else if (nums[mid] >target) {

right = mid - 1;

} else {

left = mid + 1;

}

}

}

动态规划是算法里面的大头，也是难点，我理解所有递归的问题都可以用动态规划推到出来解法。

它有两种解题方式，**自顶向下**，先由递归思路往下走，然后在加入记忆化缓存，然后反着推出状态转移方程，这种方法初学者前期用的比较多，便于理解，缺点是会比较慢，因为需要先推一次递归。**自下而上**，直接从下而上，根据有限的初始值得到最终想要的结果，这个需要对动态转移方程定义有熟练的掌握才行，需要多做题去掌握和熟练这种方式。以斐波那契数列为例，我们可以由f(0)和f(1)一直向上递推，得到f(n)。

计算机底层的计算，直接在二进制上面进行运算，计算速度会比高级语言的计算快，一个有一定代码功底的开发基本都要会的东西。

布隆过滤器算是对哈希表的一种泛化数据结构，当在某些业务场景下，我们只需要知道这个东西在集合里面是否存在，而不需要知道这个东西的具体值时，布隆过滤器就派上用场了。

布隆过滤器的实现原理是利用一系列随机哈希函数将元素存在一个很长的二进制位将元素里，一个元素会占几个bit位，但是当可能存在一个bit位被多个元素占用的时候，这个时候就会发生误判。

因此布隆过滤器的优缺点也就出来了，**优点**就是空间效率和查询时间都远远高于一般的算法，**缺点**就是会发生误判和删除困难。

**布隆过滤器里面元素如果不存在一定是不存在的，但是存在是可能存在的，你还需要进一步验证是否存在。**

因此布隆过滤器一般被用作最外层的过滤网，删除一些没用的信息，比如垃圾邮件判定等。

是一个使用比较多的缓存替换算法，最近最长使用缓存，它比较符合人脑的思维，如果一个物品，你如果很长时间没有使用的话，算法就会将其舍弃，且一个物品你前段时间没用最近开始使用了，算法会将这个物品放到最前面。它的实现一般基于HashMap+LinkedList(双向链表)实现，java里面有现成的实现->linkedHashMap。

字典树在搜索的时候经常会用到，可以用O(1)的复杂度找到查找的词组且补全高频查找结果，一般搜索引擎查询补全用的比较多。

字典树也是一种树，只是这个树和我们前面学的BFS和二叉堆不太一样，这个是颗N叉树，再者数据存储也不太一样，正常树的节点是存储完整的数据，而字典树每个节点其实只会存一个字符，当其到达尾部之后（一般条件是isEnd为true），将整个遍历路径连起来会组成一个字符串，这就是查询的结果。

字典树的缺点是空间占用会很大，是一种典型的空间换时间的思想。

并查集这块东西会比较死，记住模板然后认清使用场景，直接套上去用就行了，基本是定式操作，主要是牢记模板。

其使用场景主要是组团和配对问题。判断两个人是否是朋友，判断群组关系等。

PS:并查集现在做的题比较少，还没有产生概念，需要加强。

排序算法有很多，初级的如冒泡排序，选择排序，插入排序等，都是O（n^2）的时间复杂度，还有线性排序有计数排序，桶排序，基数排序等都是时间复杂度O(n)的算法，但是试用场景很局限，都是必须是常数Integer类型的排序，对于字符串这种完全不适用。

高级排序主要有快速排序和归并排序，这两个都是用的分治的思想，只是思考方式有点不一样。其时间复杂度是O(nlogn)，模板如下：

快速排序：

public static void quickSort(int[] array, int begin, int end) {   

if (end <= begin) return;   

int pivot = partition(array, begin, end);   

quickSort(array, begin, pivot - 1);   

quickSort(array, pivot + 1, end);

}

static int partition(int[] a, int begin, int end) {   

// pivot: 标杆位置，counter: 小于pivot的元素的个数   

int pivot = end, counter = begin;   

for (int i = begin; i < end; i++) {       

if (a[i] < a[pivot]) {           

int temp = a[counter];

a[counter] = a[i]; a[i] = temp;           

counter++;       

}   

}   

int temp = a[pivot];

a[pivot] = a[counter];

a[counter] = temp;   

return counter;

}

归并排序：

​

public static void mergeSort(int[] array, int left, int right) {   

if (right <= left) return;   

int mid = (left + right) >> 1; // (left + right) / 2   

mergeSort(array, left, mid);   

mergeSort(array, mid + 1, right);   

merge(array, left, mid, right);

}

public static void merge(int[] arr, int left, int mid, int right) {       

int[] temp = new int[right - left + 1]; // 中间数组       

int i = left, j = mid + 1, k = 0;       

while (i <= mid && j <= right) {           

temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];       

}       

while (i <= mid)   temp[k++] = arr[i++];       

while (j <= right) temp[k++] = arr[j++]; 

     

for (int p = 0; p < temp.length; p++) {           

arr[left + p] = temp[p];       

}       

// 也可以用 System.arraycopy(a, start1, b, start2, length)    }

```

当然还有利用前面堆这种数据结构的堆排序，时间复杂度是O(nlogn)。每个元素建堆是logn,n个元素就是nlogn。

##### 字符串比较算法

字符串的基本操作在实际开发中还是比较常用的，但是初级字符串比较大多数会比较简单，而高级的字符串比较算法现在掌握的还不够，题基本没来得及练，至于kmp算法，基本是懵逼的。先用时间消化吧。

**以上就是算法训练营所有内容，虽然看起来挺少，但是知识点细分和理解掌握还是会话很多时间的。上面其实有很多知识点当时学的时候由于时间原因没有掌握的那么透彻，需要花时间去掌握的。**

都毕业了，对于我来说感觉还是任重而道远，这个状态去面试可能还有问题，应该会拿2-3个月时间准备下。整体来看我有的知识点掌握的还行，如基本的数据结构，都知道使用场景和实现了，在了解其实现后在实际开发中确实会用的更加得心应手了。但有的还是不够熟练，需要过遍数，如并查集，位运算，字符串算法KMP算法等，现在基本还是半懵逼状态，需要多做题去消化。比较庆幸的一点是，对于**递归**和**动态规划**还是有自己的理解，其核心思想都大概掌握了，接下来就是多做题强化了。

**就像超哥说的那样，“师傅领进门，修行在个人。”他只能帮我们提点一下，后面还是要靠自己。你的努力程度，决定你能走多远。**