1.二分查找（非递归）
2.分治算法
3.动态规划算法
4.KMP算法
5.贪心算法
6.普里姆算法
7.克鲁斯卡尔算法
8.迪杰斯特拉算法
9.弗洛伊德算法
就是不使用递归的二分查找，这里不做介绍
public class BinarySearchNoRecur {
public static void main(String[] args) {
int[] arr = { 1, 3, 8, 10, 11, 67, 100 };
int i = binarySearch(arr, 11);
System.out.println(i);
}
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
比起算法，更像是一种思维
分治算法应用场景：
汉诺塔：
问题分析：
public class Hanoitower {
public static void main(String[] args) {
hanoiTower(6, 'a', 'b', 'c');
}
public static void hanoiTower(int num, char a, char b, char c) {
// 如果只有一个盘
if (num == 1) {
System.out.println("第1个盘从 " + a + "->" + c);
} else {
// 如果我们有n >= 2情况，我们总是可以看做是两个盘1.最下面一个盘2.上面的盘
// 1.先把最上面的所有盘A -> B
//将b参数和c参数互换，下一次递归的任务就是将a移动到b，而不会使用到c，c的使用在下下次递归中
hanoiTower(num - 1, a, c, b);
// 2.将最下面的盘A->C
System.out.println("第" + num + "个盘从 " + a + "->" + c);
// 3.把B塔的所有盘从B -> C,移动过程使用A塔
hanoiTower(num - 1, b, a, c);
}
}
}
背包问题（0-1背包）：
左表有基本信息，右表为最优解表
import java.util.Arrays;
public class KnapsackProblem {
public static void main(String[] args) {
// 物品的重量
int[] weight = { 1, 4, 3 };
// 物品的价值
int[] value = { 1500, 3000, 2000 };
// 背包的容量
int capacity = 4;
// 物品的个数
int num = weight.length;
// 创建一个最优解数组（二维数组）
// v[][]的每一个值都表示一种最优解
// 例如：
// v[2][3]表示：当容量为3时，只有前两种物品可选时存在的最优解
// v[1][2]表示：当容量为2时，只有第一种物品可选时存在的最优解
int[][] v = new int[num + 1][capacity + 1];
// 为了记录放入商品的路径，定义一个二维数组
//如果有新商品加入时，则对应商品数值置为1，否则不处理
int[][] path = new int[num + 1][capacity + 1];
// 初始化第一行和第一列，为0
for (int i = 0; i < v.length; i++) {
v[i][0] = 0;
}
for (int i = 0; i < v[0].length; i++) {
v[0][i] = 0;
}
// 根据公式进行动态规划处理
for (int i = 1; i < v.length; i++) {// 不处理第一行
for (int j = 1; j < v[0].length; j++) {// 不处理第一列
// 如果重量比容量大，则无法放入，最优解为之前的值
//
if (weight[i - 1] > j) {
v[i][j] = v[i - 1][j];
} else {
// 如果容量足够，那么最优解可能有两种情况
// 1.放入物品的价值 + 剩余空间的最优解
// 2.即使能放入物品，但是最优解不比上次的最优解大
// v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - weight[i - 1]]);
if (v[i - 1][j] < value[i - 1] + v[i - 1][j - weight[i - 1]]) {
v[i][j] = value[i - 1] + v[i - 1][j - weight[i - 1]];
path[i][j] = 1;
} else {
// 如果只是用之前的值替换，则表示没有出现最优解
v[i][j] = v[i - 1][j];
}
}
}
}
for (int[] i : v) {
System.out.println(Arrays.toString(i));
}
for (int[] i : path) {
System.out.println(Arrays.toString(i));
}
int i = path.length - 1;
int j = path[0].length - 1;
while (i > 0) {// 逆向遍历
if (path[i][j] == 1) {
System.out.printf("第%d个商品放入到背包\n", i);
j -= weight[i - 1];
}
i--;
}
}
}
参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
public class Kmp {
public static void main(String[] args) {
String string1 = "BBC ABCDAB ABCDABCDABDE";
String string2 = "ABCDABD";
int[] next = kmpNext("ABCDABD");
System.out.println(kmpSearch(string1, string2, next));
}
/**
*
* @param str1 原字符串
* @param str2 子串
* @param next 部分匹配表，是子串对应的部分匹配表
* @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
*/
public static int kmpSearch(String str1, String str2, int[] next) {
// 遍历
for (int i = 0, j = 0; i < str1.length(); i++) {
// KMP核心算法
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {
return i - j + 1;
}
}
return -1;
}
// 获取到一个字符串的部分匹配值表
public static int[] kmpNext(String dest) {
// 创建一个next数组保存部分匹配值
int[] next = new int[dest.length()];
// 第一个肯定是0，因为长度为一，没有前缀和后缀
next[0] = 0;// 如果字符串时长度为1部分匹配值就是0
for (int i = 1, j = 0; i < dest.length(); i++) {
// 当dest.chatAt(i) != dest.chatAt(j),我们需要从next[j-1]获取新的j
// 直到发现有dest.chatAt(i) == dest.chatAt(j)时退出、
// 要j大于0才走这里
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
// 当dest.chatAt(i) == dest.chatAt(j)满足时，部分匹配值就是+1
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
// 暴力匹配
public static int violenceMatch(String str1, String str2) {
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
boolean flag = false;
int s1len = s1.length;
int s2len = s2.length;
int i = 0;
int j = 0;
while (i < s1len && j < s2len) {
if (s1[i] == s2[j]) {
i++;
j++;
} else {
i = i - (j - 1);
j = 0;
}
}
if (j == s2len) {
return i - j;
} else {
return -1;
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class Greedy {
public static void main(String[] args) {
HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
HashSet<String> hashset1 = new HashSet<String>();
hashset1.add("北京");
hashset1.add("上海");
hashset1.add("天津");
HashSet<String> hashset2 = new HashSet<String>();
hashset2.add("北京");
hashset2.add("广州");
hashset2.add("深圳");
HashSet<String> hashset3 = new HashSet<String>();
hashset3.add("成都");
hashset3.add("上海");
hashset3.add("杭州");
HashSet<String> hashset4 = new HashSet<String>();
hashset4.add("天津");
hashset4.add("上海");
HashSet<String> hashset5 = new HashSet<String>();
hashset5.add("杭州");
hashset5.add("大连");
broadcasts.put("K1", hashset1);
broadcasts.put("K2", hashset2);
broadcasts.put("K3", hashset3);
broadcasts.put("K4", hashset4);
broadcasts.put("K5", hashset5);
// allAreas,如果覆盖到其中一个地区，就会移除地区，如果全覆盖，则为空
HashSet<String> allAreas = new HashSet<String>();
allAreas.add("北京");
allAreas.add("上海");
allAreas.add("天津");
allAreas.add("杭州");
allAreas.add("大连");
allAreas.add("成都");
allAreas.add("广州");
allAreas.add("深圳");
// 创建ArrayList，存放选择的电台集合
ArrayList<String> selects = new ArrayList<String>();
String maxKey = null;
HashSet<String> tempSet = new HashSet<String>();
while (allAreas.size() != 0) {
maxKey = null;
for (String key : broadcasts.keySet()) {
tempSet.clear();
HashSet<String> areas = broadcasts.get(key);
tempSet.addAll(areas);
// 求出交集
tempSet.retainAll(allAreas);
// 求交集后，如果大小大于0，则表示还能覆盖新的地区，如果不大于零，就没有必要加入
//如果maxKey为空，则赋值当前的key
//如果maxKey不为空，则保存的是上次的最大覆盖地区key
//如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合未覆盖的地区还多，就重置maxKey
if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
maxKey = key;
}
}
if (maxKey != null) {
//加入选择
selects.add(maxKey);
//移除已添加的地区
allAreas.removeAll(broadcasts.get(maxKey));
}
}
//当退出循环后，则就按照贪心算法得到一个解
System.out.println(selects);
}
}
import java.util.Arrays;
public class Prim {
public static void main(String[] args) {
char[] data = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
int verxs = data.length;
int[][] weight = new int[][] { { 10000, 5, 7, 10000, 10000, 10000, 2 }, { 5, 10000, 10000, 9, 10000, 10000, 3 },
{ 7, 10000, 10000, 10000, 8, 10000, 10000 }, { 10000, 9, 10000, 10000, 10000, 4, 10000 },
{ 10000, 10000, 8, 10000, 10000, 5, 4 }, { 10000, 10000, 10000, 4, 5, 10000, 6 },
{ 2, 3, 10000, 10000, 4, 6, 10000 } };
MGraph mGraph = new MGraph(verxs);
MinTree minTree = new MinTree();
minTree.createGraph(mGraph, verxs, data, weight);
minTree.showGaph(mGraph);
minTree.prim(mGraph, 1);
}
}
//创建最小生成树 -> 村庄的图
class MinTree {
/**
*
* @param graph 图对象
* @param verxs 图对应的顶点个数
* @param data 图的各个顶点的值
* @param weight 图的邻接矩阵
*/
public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
int i, j;
for (i = 0; i < verxs; i++) {
graph.data[i] = data[i];
for (j = 0; j < verxs; j++) {
graph.weight[i][j] = weight[i][j];
}
}
}
public void showGaph(MGraph graph) {
for (int i = 0; i < graph.weight.length; i++) {
System.out.println(Arrays.toString(graph.weight[i]));
}
}
/**
*
* @param graph 图
* @param value 表示从图的第一个顶点开始生成,就是起点的下标
*/
public void prim(MGraph graph, int value) {
int[] visited = new int[graph.verxs];
visited[value] = 1;
int h1 = -1;
int h2 = -1;
int minWeight = 10000;
for (int k = 1; k < graph.verxs; k++) {//因为有graph.verxs顶点，普利姆算法借宿后，有graph.verxs-1边
// 这个是确定每一次生成的子图，和那个结点的距离最近
// 以下的双重循环是为了遍历每一条边,i为起点的下标，j为终点的下标
for (int i = 0; i < graph.verxs; i++) {// i结点表示被访问的结点
for (int j = 0; j < graph.verxs; j++) {// j结点表示还没有访问过的结点
//当然这样做有点冗余
//这里需要过滤一下，i已访问，j未访问才是需要的
//并在这些条件下挑出距离最小的那一个
if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
// 替代minWeight
minWeight = graph.weight[i][j];
//记录下距离最小边的记录
h1 = i;
h2 = j;
}
}
}
// 找到一条边
System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + ">权值：" + minWeight);
visited[h2] = 1;
// minWeight 重新设置为最大值10000
minWeight = 10000;
}
}
}
class MGraph {
int verxs;// 表示圆的结点个数
char[] data;// 存放节点数据
int[][] weight;// 存放边，就是我们的邻接矩阵
public MGraph(int verxs) {
this.verxs = verxs;
data = new char[verxs];
weight = new int[verxs][verxs];
}
}
import java.util.Arrays;
public class Kruskal {
public int edgeNum;// 边的个数
public char[] vertexs;// 顶点数组
public int[][] matrix;// 邻接矩阵
public static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) {
char[] vertexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
int matrix[][] = {
/* A *//* B *//* C *//* D *//* E *//* F *//* G */
/* A */ { 0, 12, INF, INF, INF, 16, 14 }, /* B */ { 12, 0, 10, INF, INF, 7, INF },
/* C */ { INF, 10, 0, 3, 5, 6, INF }, /* D */ { INF, INF, 3, 0, 4, INF, INF },
/* E */ { INF, INF, 5, 4, 0, 2, 8 }, /* F */ { 16, 7, 6, INF, 2, 0, 9 },
/* G */ { 14, INF, INF, INF, 8, 9, 0 } };
Kruskal kruskal = new Kruskal(vertexs, matrix);
kruskal.kruskal();
// kruskal.print();
}
public Kruskal(char[] vertexs, int[][] matrix) {
int vlen = vertexs.length;
this.vertexs = new char[vlen];
// 使用复制的方式
this.vertexs = vertexs.clone();
this.matrix = matrix.clone();
for (int i = 0; i < matrix.length; i++) {
for (int j = i + 1; j < matrix[0].length; j++) {
if (matrix[i][j] != INF) {
edgeNum++;
}
}
}
}
public void print() {
System.out.println("邻接矩阵:");
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.printf("%10d\t", matrix[i][j]);
}
System.out.println();
}
}
public void sortEdges(EData[] edges) {
for (int i = 0; i < edges.length - 1; i++) {
for (int j = 0; j < edges.length - 1 - i; j++) {
if (edges[j].weight > edges[j + 1].weight) {
EData tempData = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = tempData;
}
}
}
}
/**
*
* @param ch
* @return 返回下标
*/
public int getPosition(char ch) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == ch) {
return i;
}
}
return -1;
}
/**
* 功能：获取图中的边， 通过matrix 邻接矩阵类获取
*
* @return
*/
public EData[] getEdges() {
int index = 0;
EData[] edges = new EData[edgeNum];
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (matrix[i][j] != INF) {
edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return edges;
}
/**
* 功能：获取下标 为 i 的顶点的终点，用于后面判断两个顶点的终点是否相同
*
* @param ends：数组就是记录了各个顶点对应的终点是哪个，ends数组是在遍历过程中，逐步形成
* @param i：表示传入的顶点对应的下标
* @return 返回的就是下标为 i 的这个顶点对应的终点的下标
*
*/
public int getEnd(int[] ends, int i) {
while (ends[i] != 0) {
i = ends[i];
}
System.out.println("End:"+Arrays.toString(ends));
return i;
}
public void kruskal() {
int index = 0;// 表示最后结果数组的索引
int[] ends = new int[edgeNum];// 用于保存
EData[] rets = new EData[edgeNum];
EData[] edges = getEdges();
sortEdges(edges);
for (int i = 0; i < edgeNum; i++) {
int p1 = getPosition(edges[i].start);
int p2 = getPosition(edges[i].end);
int m = getEnd(ends, p1);// m = 4
int n = getEnd(ends, p2);// n = 5
// 是否构成回路
if (m != n) {
ends[m] = n;
rets[index++] = edges[i];
}
}
for (int i = 0; i < index; i++) {
System.out.println(rets[i]);
}
}
}
//创建边的类
class EData {
char start;// 起点
char end;// 终点
int weight;// 权值
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "[EData <" + start + ", " + end + "> weight=" + weight + "]";
}
}
import java.util.Arrays;
public class Dijkstra {
public static void main(String[] args) {
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
final int N = 65535;
int[][] matrix = new int[][] {
{ N, 5, 7, N, N, N, 2 },
{ 5, N, N, 9, N, N, 3 },
{ 7, N, N, N, 8, N, N },
{ N, 9, N, N, N, 4, N },
{ N, N, 8, N, N, 5, 4 },
{ N, N, N, 4, 5, N, 6 },
{ 2, 3, N, N, 4, 6, N },
};
Graph graph = new Graph(vertex, matrix);
// graph.showGraph();
graph.dsj(6);
graph.showDjs();
}
}
class Graph {
public char[] vertex;
public int[][] matrix;
// 已经访问的顶点的集合
public VisitedVertex vv;
public Graph(char[] vertex, int[][] matrix) {
this.vertex = vertex;
this.matrix = matrix;
}
public void showDjs() {
vv.show();
}
public void showGraph() {
for (int[] i : matrix) {
System.out.println(Arrays.toString(i));
}
}
/**
*
* @param index 表示出发顶点对应的下标
*/
public void dsj(int index) {
//新创建的已访问数组
vv = new VisitedVertex(vertex.length, index);
//首先更新一下起点
update(index);
for (int j = 1; j < vertex.length; j++) {
index = vv.updateArr();
update(index);
}
}
// 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
public void update(int index) {
int len = 0;
// 根据遍历我们的邻接矩阵的 matrix[index]行
for (int j = 0; j < matrix[index].length; j++) {
// len含义是：出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
//一开始dis的值都是65535
len = vv.getDis(index) + matrix[index][j];
// 如果j没有被访问过，并且len小于出发顶点到j顶点的距离，就需要更新
if (!vv.in(j) && len < vv.getDis(j)) {
vv.updatePre(j, index);// 更新j顶点的前驱为index顶点
vv.updateDis(j, len);// 更新出发顶点到j顶点的距离
}
}
}
}
//已访问顶点的集合
class VisitedVertex {
// 记录各个顶点是否访问过，1表示访问过，0表示未访问，会动态更新
public int[] already_arr;
// 每个小标对应的值为前一个顶点下标，会动态更新
public int[] pre_visited;
// 记录出发顶点到其他所有顶点的距离，比如G为出发顶点，就会记录G到其他顶点的距离，会动态更新，求的最短距离就会存放到dis
public int[] dis;
/**
*
* @param lenght 表示顶点的个数
* @param index 表示出发顶点对应的下标
*/
public VisitedVertex(int lenght, int index) {
this.already_arr = new int[lenght];
this.pre_visited = new int[lenght];
this.dis = new int[lenght];
// 初始化dis数组
Arrays.fill(dis, 65535);
// 设置出发顶点的访问距离为0
this.dis[index] = 0;
this.already_arr[index] = 1;
}
/**
* 功能：判断index顶点是否访问过
*
* @param index
* @return 如果访问过，就放回true，否则返回false
*/
public boolean in(int index) {
return already_arr[index] == 1;
}
/**
* 功能：更新出发顶点到index顶点的距离
*
* @param index
* @param len
*/
public void updateDis(int index, int len) {
dis[index] = len;
}
/**
* 功能：更新顶点的前驱为index结点
*
* @param pre
* @param index
*/
public void updatePre(int pre, int index) {
pre_visited[pre] = index;
}
/**
* 功能：返回出发顶点到index顶点的距离
*
* @param index
*/
public int getDis(int index) {
return dis[index];
}
/**
* 继续选择并返回新的访问顶点，比如这里的G，就是A点作为新的访问顶点（不是出发点）
*
* @return
*/
public int updateArr() {
int min = 65535, index = 0;
for (int i = 0; i < already_arr.length; i++) {
if (already_arr[i] == 0 && dis[i] < min) {
min = dis[i];
index = i;
}
}
already_arr[index] = 1;
return index;
}
public void show() {
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'D', 'G' };
int count = 0;
for (int i : dis) {
if (i != 65535) {
System.out.print(vertex[count++] + "(" + i + ")");
}
}
}
}
import java.util.Arrays;
public class Floyd {
public static void main(String[] args) {
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
int[][] matrix = new int[vertex.length][vertex.length];
final int N = 65535;
matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
Graph2 graph = new Graph2(vertex.length, matrix, vertex);
graph.floyd();
graph.show();
}
}
class Graph2 {
public char[] vertex;// 存放顶点
public int[][] dis;// 保存，从各个顶点出发到其他顶点的距离，最后的结构，也是保存在该数组
public int[][] pre;// 前驱
public Graph2(int length, int[][] matrix, char[] vertex) {
this.vertex = vertex;
this.dis = matrix;
this.pre = new int[length][length];
// 对pre数组初始化
// 一开始前驱是本身
for (int i = 0; i < length; i++) {
Arrays.fill(pre[i], i);
}
}
public void show() {
char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
for (int k = 0; k < dis.length; k++) {
for (int i = 0; i < dis.length; i++) {
System.out.print(vertex[pre[k][i]] + " ");
}
System.out.println();
for (int i = 0; i < dis.length; i++) {
System.out.print("(" + vertex[k] + "到" + vertex[i] + "的最短路径是" + dis[k][i] + ")");
}
System.out.println();
System.out.println();
}
}
public void floyd() {
int len = 0;
// 从中间顶点的遍历
for (int k = 0; k < dis.length; k++) {
// 从i顶点出发a、b、c、d、。。。
for (int i = 0; i < dis.length; i++) {
for (int j = 0; j < dis.length; j++) {
len = dis[i][k] + dis[k][j];// 求出i顶点出发，经过k中间点，到达j顶点距离
if (len < dis[i][j]) {// 如果小于直连距离
dis[i][j] = len;
pre[i][j] = pre[k][j];
}
}
}
}
}
}