c) 若要求排序稳定，则可选用归并排序。
* TopK或优先队列通常用堆排序来实现
5. Bitmap位图算法
位图是指内存中连续的二进制位，用于对大量的整型数据做去重和查询。Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
-
bitmap应用
1）可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。
2）去重数据而达到压缩数据
位图只是可以映射数字类型的数据，变成字符串以及其他文件好像就不再那么得心应手了，这时就要使用布隆过滤器
6. 布隆过滤器
bloom算法类似一个位图，用来判断某个元素（key）是否在某个集合中。和一般的位图不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。
-
应用场景：比如网络爬虫抓取时url去重，邮件提供商反垃圾黑名单Email地址去重，之所以需要k个比特位是因为我们大多数情况下处理的是字符串，那么不同的字符串就有可能映射到同一个位置，产生冲突。
-
优点：不需要存储key，节省空间
-
缺点：算法判断key在集合中时，有一定的概率key其实不在集合中，已经映射的数据无法删除
7. （Tire）字典树
-
定义：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
-
3个基本性质：
-
根节点不包含字符，除根节点外每一个节点都只包含一个字符；
-
从根节点到某一节点路径上经过的字符连接起来，为该节点对应的字符串；
-
每个节点的所有子节点包含的字符都不相同。
-
8. 海量数据找出前K大的数
top K类问题，通常比较好的方案是分治+Trie树/hash+小顶堆（就是上面提到的最小堆），即先将数据集按照Hash方法分解成多个小数据集，然后使用Trie树活着Hash统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
9. 五大查找方式
10. BFS、DFS优缺点
-
深搜优缺点
-
优点
-
能找出所有解决方案
-
优先搜索一棵子树，然后是另一棵，所以和广搜对比，有着内存需要相对较少的优点
-
-
缺点
-
要多次遍历，搜索所有可能路径，标识做了之后还要取消。
-
在深度很大的情况下效率不高
-
-
-
广搜优缺点
-
优点
-
对于解决最短或最少问题特别有效，而且寻找深度小
-
每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短
-
-
缺点
- 内存耗费量大（需要开大量的数组单元用来存储状态）
-
更多Java学习资料、面试真题获得，请【点击此处】
11. 动态规划
-
核心思想：将大问题分为小问题进行解决，从而一步步获得最优解的处理算法，与分治算法不同的是适合于动态规划求解的问题，经分解得到的子问题往往不是相互独立的。
-
求解方式：填表
-
思想：w[i]为第i个商品的重量，v[i]代表第i个商品的价值，v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值
a) v[i][0]=v[0][j]=0；//使得i和j刚好和第几个商品对应
b) 当w[i]>j时：v[i][j]=v[i-1][j]；//当准备加入新增的商品的容量w[i]大于当前背包的容量j时就直接使用上一单元格的装入策略
c) 当w[i]<=j时：v[i][j]=max{v[i-1][j]， v[i]+v[i-1][j-w[i]]}；
//上一个单元格的装入的最大值v[i-1][j]
//v[i]当前商品的价值
//v[i-1][j-w[i]]装入i-1个商品剩余空间j-w[i]的最大值
-
//根据前面得到公式来动态规划处理
-
for(int i = 1; i < v.length; i++) {//不处理第一行i是从1开始的
-
for(int j=1; j < v[0].length; j++){//不处理第一列，j是从1开始的 -
//公式 -
if(w[i-1]> j){//因为我们程序i是从1开始的，因此原来公式中的w[i]修改成w[i-1] -
v[][j]=v[i-1][j]; -
}else{ -
//说明: -
//因为我们的i从1开始的,因此公式需要调整成 -
//v[i][j]=Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]); -
v[][j]=Math.max(v[i-1][j], val[i]+v[i-1][j-w[i-1]]); -
} -
} -
}
### 12\. 什么样的题适合用动态规划？
* 最值型动态规划，比如求最大，最小值是多少
* 计数型动态规划，比如换硬币，有多少种换法
* 坐标型动态规划，比如在m\*n矩阵求最值型，计数型，一般是二维矩阵
* 区间型动态规划，比如在区间中求最值
### 13\. 暴力匹配算法
-
public static int ViolenceMatch(String str1， String str2) {
-
char[] s1 = str1.toCharArray()； -
char[] s2 = str2.toCharArray()； -
int i = 0； -
int j = 0； -
while (i < s1.length && j < s2.length) { -
if (s1[i] == s2[j]) { -
i++； -
j++； -
} else { -
i = i - (j - 1)； -
j = 0； -
} -
} -
if (j == s2.length) { -
return i - j； -
} -
return -1； -
}
### 14\. KMP算法
建立部分匹配表
移动位数 = 已匹配的字符数 – 对应的部分匹配值
-
public static int[] KmpMatchTable(String str) {
-
int[] matchTable = new int[str.length()]； -
matchTable[0] = 0； -
for (int i = 1， j = 0； i < str.length()； i++) { -
//不等时重新获取前一个的值，kmp算法核心 -
while (j > 0 && str.charAt(i) != str.charAt(j)) { -
j = matchTable[j - 1]； -
} -
//部分匹配则值+1 -
if (str.charAt(i) == str.charAt(j)) { -
j++； -
} -
matchTable[i] = j； -
} -
return matchTable； -
}
KMP搜索
-
public static int KMPMatch(String str1， String str2) {
-
int[] matchTable=KmpMatchTable(str2)； -
for (int i = 0，j=0； i < str1.length()； i++) { -
//处理不等情况 -
while(j>0&&str1.charAt(i)!=str2.charAt(j)){ -
j = matchTable[j-1]； -
} -
if (str1.charAt(i)==str2.charAt(j)){ -
j++； -
} -
if (j==str2.length()){ -
return i-j+1； -
} -
} -
return -1； -
}
### 15\. 贪心算法
### 16\. 普利姆算法（prim）
* 求最小生成树
* 普里姆算法介绍
* 普利姆(Prim)算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n-1)条边包含所有n个顶点的连通子图，也就是所谓的极小连通子图
* 普利姆的算法如下:
(1) 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
(2) 若从顶点u开始构造最小生成树，则从集合V中取出顶点u放入集合U中，标记顶点v的visited\[u\]=1
(3) 若集合U中顶点ui与集合V-U中的顶点vj之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入集合D中，标记visited\[vj\]=1
(4) 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有n-1条边
(5) 提示：单独看步骤很难理解，我们通过代码来讲解，比较好理解.
### 17\. 二叉树的中序遍历
-
List list = new ArrayList<>()；
-
public TreeNode increasingBST(TreeNode root) { -
if(null==root)return null； -
Deque<TreeNode> queue = new ArrayDeque<>()； -
while(root!=null||!queue.isEmpty()){ -
while(root!=null){ -
queue.add(root)； -
root = root.left； -
} -
root = queue.pollLast()； -
list.add(root.val)； -
root=root.right； -
} -
return list； -
}
### 18\. 二叉树层序遍历
-
public List<List> levelOrder(TreeNode root) {
-
List<List<Integer>> res = new ArrayList<>()； -
Queue<TreeNode> queue = new ArrayDeque<>()； -
if (root != null) { -
queue.add(root)； -
} -
while (!queue.isEmpty()) { -
int n = queue.size()；//记录节点个数 -
List<Integer> level = new ArrayList<>()； -
//遍历每个节点的左右子节点 -
for (int i = 0； i < n； i++) { -
TreeNode node = queue.poll()； -
level.add(node.val)；
最后分享一波我的面试宝典——一线互联网大厂Java核心面试题库
以下是我个人的一些做法，希望可以给各位提供一些帮助：
点击《一线互联网大厂Java核心面试题库》即可免费领取，整理了很长一段时间，拿来复习面试刷题非常合适，其中包括了Java基础、异常、集合、并发编程、JVM、Spring全家桶、MyBatis、Redis、数据库、中间件MQ、Dubbo、Linux、Tomcat、ZooKeeper、Netty等等，且还会持续的更新…可star一下！
283页的Java进阶核心pdf文档
Java部分：Java基础，集合，并发，多线程，JVM，设计模式
数据结构算法：Java算法，数据结构
开源框架部分：Spring，MyBatis，MVC，netty，tomcat
分布式部分：架构设计，Redis缓存，Zookeeper，kafka，RabbitMQ，负载均衡等
微服务部分：SpringBoot，SpringCloud，Dubbo，Docker
还有源码相关的阅读学习
全家桶、MyBatis、Redis、数据库、中间件MQ、Dubbo、Linux、Tomcat、ZooKeeper、Netty等等，且还会持续的更新…可star一下！
[外链图片转存中…(img-a5SCagvg-1628601768301)]
283页的Java进阶核心pdf文档
Java部分：Java基础，集合，并发，多线程，JVM，设计模式
数据结构算法：Java算法，数据结构
开源框架部分：Spring，MyBatis，MVC，netty，tomcat
分布式部分：架构设计，Redis缓存，Zookeeper，kafka，RabbitMQ，负载均衡等
微服务部分：SpringBoot，SpringCloud，Dubbo，Docker
[外链图片转存中…(img-MlDVvXfy-1628601768303)]
还有源码相关的阅读学习
[外链图片转存中…(img-g26EvczP-1628601768306)]