时常，在项目中会遇到算法问题，多数人也就在面试时背背算法题，工作中也用的比较少，常见的算法也有封装好的实现，比如 JDK封装的Arrays工具类中的二分查找。
那我们还需要去研究算法吗，答案是需要，在很多业务场景中，成熟的算法可以提高效率，减少不必要的问题出现，规避风险。
今天V哥总结了15个在实现业务场景中使用到的算法，分享给你，可能对你有用。
- 1.快速排序算法
- 2.动态规划-背包问题
- 3.最短路径算法-Dijkstra算法
- 4.树的遍历-深度优先搜索（DFS）
- 5.树的遍历-广度优先搜索（BFS）
- 6.图的最短路径-Floyd-Warshall算法
- 7.排序算法-归并排序
- 8.字符串匹配算法-KMP算法
- 9.图的最小生成树-Prim算法
- 10.图的最短路径-Bellman-Ford算法
- 11.图的最小生成树-Kruskal算法
- 12.协同过滤推荐算法
- 13.基于内容的推荐算法
- 14.K-均值聚类算法
- 15.决策树算法
1.快速排序算法
实现原理：
快速排序是一种高效的排序算法，采用分治法的思想。它选择一个基准元素，将数组分割成左右两个子数组，其中左边的元素都小于等于基准元素，右边的元素都大于等于基准元素，然后递归地对左右子数组进行排序。
示例代码：
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {
12, 3, 9, 7, 2, 16, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
逻辑步骤：
- 选择数组中的一个元素作为基准元素（通常选择最后一个元素）。
- 使用分区函数将数组重新排列，使得比基准元素小的元素位于基准元素的左侧，大的位于右侧。
- 递归地对基准元素左右两侧的子数组进行排序。
业务场景和案例说明：
快速排序算法适用于需要对大规模数据进行排序的场景，例如在数据库系统中对数据进行排序、搜索引擎中对搜索结果进行排序等。由于快速排序具有平均时间复杂度为 O(n log n)，因此在处理大规模数据时具有较好的性能表现。例如，在对海量用户数据进行排序时，可以使用快速排序算法提高排序效率。
2.动态规划-背包问题
实现原理：
背包问题是一个经典的动态规划问题，其目标是在限定的背包容量下，装入最有价值的物品。动态规划解决背包问题的核心思想是通过构建一个二维数组来记录在不同背包容量和不同物品数量下的最大价值，然后利用状态转移方程来更新数组中的值，最终得到背包能装下的最大价值。
示例代码：
public class KnapsackProblem {
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][capacity];
}
public static void main(String[] args) {
int[] weights = {
2, 3, 4, 5};
int[] values = {
3, 4, 5, 6};
int capacity = 8;
int maxValue = knapsack(weights, values, capacity);
System.out.println("背包能装下的最大价值为：" + maxValue);
}
}
逻辑步骤：
- 初始化一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时的最大价值。
- 遍历物品和背包容量的组合，根据当前物品是否放入背包，更新 dp[i][j] 的值。
- 最终返回 dp[n][capacity]，即所有物品都考虑完毕，背包容量为 capacity 时的最大价值。
业务场景和案例说明：
动态规划背包问题在很多场景中都有应用，例如在资源分配、投资决策、作业调度等领域。一个典型的案例是在零售业中的库存管理，商家需要在有限的仓库空间内选择存放哪些商品以及存放多少数量，以最大化销售额和利润。通过动态规划背包问题，可以帮助商家做出最优的库存管理决策，使得在有限的仓库空间内存放最有价值的商品。
3.最短路径算法-Dijkstra算法
实现原理：
Dijkstra 算法用于求解单源最短路径问题，即从一个源点到图中所有其他顶点的最短路径。它的基本思想是通过不断地选择距离源点最近的顶点来逐步确定最短路径，并使用优先队列来加速查找过程。
示例代码：
import java.util.*;
public class DijkstraAlgorithm {
public static int[] dijkstra(int[][] graph, int source) {
int vertices = graph.length;
int[] distance = new int[vertices];
boolean[] visited = new boolean[vertices];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[source] = 0;
for (int i = 0; i < vertices - 1; i++) {
int minDistance = Integer.MAX_VALUE;
int minIndex = -1;
for (int v = 0; v < vertices; v++) {
if (!visited[v] && distance[v] < minDistance) {
minDistance = distance[v];
minIndex = v;
}
}
visited[minIndex] = true;
for (int j = 0; j < vertices; j++) {
if (!visited[j] && graph[minIndex][j] != 0 && distance[minIndex] != Integer.MAX_VALUE
&& distance[minIndex] + graph[minIndex][j] < distance[j]) {
distance[j] = distance[minIndex] + graph[minIndex][j];
}
}
}
return distance;
}
public static void main(String[] args) {
int[][] graph = {
{
0, 4, 0, 0, 0, 0, 0, 8, 0},
{
4, 0, 8, 0, 0, 0, 0, 11, 0},
{
0, 8, 0, 7, 0, 4, 0, 0, 2},
{
0, 0, 7, 0, 9, 14, 0, 0, 0},
{
0, 0, 0, 9, 0, 10, 0, 0, 0},
{
0, 0, 4, 14, 10, 0, 2, 0, 0},
{
0, 0, 0, 0, 0, 2, 0, 1, 6},
{
8, 11, 0, 0, 0, 0, 1, 0, 7},
{
0, 0, 2, 0, 0, 0, 6, 7, 0}
};
int source = 0;
int[] shortestDistances = dijkstra(graph, source);
System.out.println("从源点到其他顶点的最短路径长度为：");
for (int i = 0; i < shortestDistances.length; i++) {
System.out.println("从顶点 " + source + " 到顶点 " + i + " 的距离为 " + shortestDistances[i]);
}
}
}
逻辑步骤：
- 初始化距离数组 distance 和访问标记数组 visited，并将距离数组的源点距离设为0。
- 循环遍历所有顶点，每次选择未访问的顶点中距离源点最近的顶点，将其标记为已访问。
- 更新从源点到其他顶点的最短距离，如果经过当前顶点到其他顶点的距离比已有距离小，则更新距离数组。
- 重复步骤 2 - 3，直到所有顶点都被访问过，最终得到从源点到其他顶点的最短路径长度数组。
业务场景和案例说明：
Dijkstra 算法在网络路由、地图导航、电信网络等领域有广泛的应用。一个典型的应用场景是在地图导航系统中，通过 Dijkstra 算法可以找到两个地点之间的最短路径，帮助用户快速规划出行路线。例如，用户在导航软件中输入起点和终点后，系统可以利用 Dijkstra 算法计算出最短路径，并指导用户进行导航。这种应用不仅可以节省用户的时间，还可以提高行驶效率。
4.树的遍历-深度优先搜索（DFS）
实现原理：
深度优先搜索是一种用于遍历或搜索树或图的算法，其核心思想是尽可能深地搜索树的分支，直到不能再继续为止，然后回溯并继续搜索其他分支。在树的遍历中，深度优先搜索使用递归或栈来实现。
示例代码：
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int val) {
this.val = val;
left = right = null;
}
}
public class DepthFirstSearch {
public static List<Integer> dfs(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root != null) {
dfsHelper(root, result);
}
return result;
}
private static void dfsHelper(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
result.add(node.val);
dfsHelper(node.left, result);
dfsHelper(node.right, result);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
List<Integer> traversal = dfs(root);
System.out.println("深度优先搜索遍历结果：" + traversal);
}
}
逻辑步骤：
- 如果根节点不为空，则将根节点值加入结果列表。
- 递归地遍历左子树。
- 递归地遍历右子树。
业务场景和案例说明：
深度优先搜索算法在树的遍历、路径搜索、拓扑排序等场景中都有应用。一个典型的应用场景是在社交网络中查找两个用户之间的关系路径。通过深度优先搜索算法可以在社交网络的用户关系图中搜索两个用户之间的连接路径，例如两个用户是否有共同的好友、是否存在间接的关系链等。这种应用有助于社交网络平台为用户提供更多的社交互动和信息推荐服务。
5.树的遍历-广度优先搜索（BFS）
实现原理：
广度优先搜索是一种用于遍历或搜索树或图的算法，其核心思想是从根节点开始，逐层地访问每个节点，直到找到目标节点为止。在树的遍历中，广度优先搜索使用队列来实现。
示例代码：
import java.util.*;
public class BreadthFirstSearch {
public static List<Integer> bfs(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
result.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return result;
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
List<Integer> traversal = bfs(root);
System.out.println("广度优先搜索遍历结果：" + traversal);
}
}
逻辑步骤：
- 将根节点加入队列。
- 循环遍历队列中的节点，依次将它们的子节点加入队列。
- 按层次遍历树，直到队列为空。
业务场景和案例说明：
广度优先搜索算法在树的层次遍历、图的最短路径等场景中有应用。一个典型的应用场景是在社交网络中查找两个用户之间的最短路径。通过广度优先搜索算法可以在社交网络的用户关系图中搜索两个用户之间的最短路径，例如最少经过多少个中间人就能建立起两个用户之间的联系。这种应用有助于社交网络平台为用户提供更多的社交互动和信息推荐服务。
6.图的最短路径-Floyd-Warshall算法
实现原理：
Floyd-Warshall 算法用于解决图中所有顶点之间的最短路径问题，即找出任意两个顶点之间的最短路径长度。该算法通过动态规划的思想，使用一个二维数组来记录任意两个顶点之间的最短路径长度，并通过更新数组中的值来求解最短路径。
示例代码：
public class FloydWarshallAlgorithm {
public static final int INF = Integer.MAX_VALUE / 2;
public static void floydWarshall(int[][] graph) {
int vertices = graph.length;
// 初始化距离数组
int[][] dist = new int[vertices][vertices];
for (int i = 0; i < vertices; i++) {
System.arraycopy(graph[i], 0, dist[i], 0, vertices);
}
// 计算最短路径
for (int k = 0; k < vertices; k++) {
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// 输出最短路径
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
if (dist[i][j] == INF) {
System.out.print("INF\t");
} else {
System.out.print(dist[i][j] + "\t");
}
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] graph = {
{
0, 5, INF, 10},
{
INF, 0, 3, INF},
{
INF, INF, 0, 1},
{
INF, INF, INF, 0}
};
floydWarshall(graph);
}
}
逻辑步骤：
- 初始化距离数组 dist，其中 dist[i][j] 表示顶点 i 到顶点 j 的最短路径长度。
- 遍历所有顶点对 (i, j)，通过中间顶点 k 更新 dist[i][j] 的值，使得 dist[i][j] 表示经过顶点 k 的最短路径长度。
- 最终得到的 dist 数组即为图中任意两个顶点之间的最短路径长度。
业务场景和案例说明：
Floyd-Warshall 算法在网络路由、城市交通规划、航班调度等场景中有应用。例如，在城市交通规划中，可以使用 Floyd-Warshall 算法计算任意两个地点之间的最短路径长度，以便规划公交线路、优化交通流量等。这种应用有助于城市交通管理部门更好地规划城市交通系统，提高交通效率和便利性。
7.排序算法-归并排序
实现原理：
归并排序是一种经典的分治算法，它的基本思想是将待排序数组分成两个子数组，分别对两个子数组进行排序，然后将排好序的子数组合并成一个有序数组。归并排序通过递归地将问题分解成小问题并解决，然后再将结果合并起来，最终得到整个数组的有序序列。
示例代码：
public class MergeSort {
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
private static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
public static void main(String[] args) {
int[] arr = {
12, 3, 9, 7, 2, 16, 8};
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
逻辑步骤：
- 将待排序数组分成两个子数组，分别对左右两个子数组进行归并排序。
- 合并两个排好序的子数组，得到一个排好序的大数组。
业务场景和案例说明：
归并排序算法适用于需要稳定排序且不在乎空间复杂度的场景。例如在外部排序中，由于归并排序的分治思想和合并步骤，使得它适用于对大规模数据进行排序，尤其是当所有数据不能一次性加载到内存中时。在数据库系统中，当需要对超大型表中的数据进行排序时，归并排序也被广泛应用。它将大数据集分成小块，对每一块进行排序，然后再将排序后的块合并成一个有序序列，这样可以有效地对大规模数据进行排序，并且具有稳定的时间复杂度。
8.字符串匹配算法-KMP算法
实现原理：
KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，用于在一个文本串中查找一个模式串的出现位置。它利用已经部分匹配这个有效信息，尽可能减少模式串与文本串的匹配次数。KMP 算法的核心是构建一个部分匹配表（即 next 数组），用于指示在匹配失败时模式串应该向右移动的距离。
示例代码：
public class KMPAlgorithm {
public static int[] buildNextArray(String pattern) {
int[] next = new int[pattern.length()];
int i = 0, j = -1;
next[0] = -1;
while (i < pattern.length() - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
public static int kmpSearch(String text, String pattern) {
int[] next = buildNextArray(pattern);
int i = 0, j = 0;
while (i < text.length() && j < pattern.length()) {
if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == pattern.length()) {
return i - j; // 匹配成功，返回匹配的起始位置
} else {
return -1; // 匹配失败
}
}
public static void main(String[] args) {
String text = "ABABCABAB";
String pattern = "ABAB";
int index = kmpSearch(text, pattern);
if (index != -1) {
System.out.println("模式串在文本串中的起始位置为：" + index);
} else {
System.out.println("文本串中未找到模式串");
}
}
}
逻辑步骤：
- 构建模式串的部分匹配表（next 数组）。
- 在文本串中逐个字符与模式串进行匹配，根据部分匹配表确定模式串的移动位置。
业务场景和案例说明：
KMP 算法在字符串匹配、文本搜索等领域有广泛的应用。一个典型的应用场景是在搜索引擎中进行字符串匹配，例如用户输入一个搜索关键词，搜索引擎需要在大量的文本数据中快速定位包含该关键词的文本片段。通过 KMP 算法，可以高效地在文本数据中查找搜索关键词的出现位置，并提供相关的搜索结果给用户。这种应用有助于提高搜索引擎的搜索速度和准确性。
9.图的最小生成树-Prim算法
实现原理：
Prim 算法是一种用于构建无向图的最小生成树的贪心算法。它从图中的任意顶点开始，逐步选择与当前生成树相连的最短边，直到生成树覆盖了图中的所有顶点。Prim 算法通过维护一个边集合和一个顶点集合来实现。
示例代码：
import java.util.*;
public class PrimAlgorithm {
static class Edge {
int from, to, weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
public static List<Edge> primMST(List<List<Edge>> graph) {
List<Edge> minSpanningTree = new ArrayList<>();
int vertices = graph.size();
Set<Integer> visited = new HashSet<>();
visited.add(0); // 从第一个顶点开始
PriorityQueue<Edge> minHeap = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
minHeap.addAll(graph.get(0));
while (!minHeap.isEmpty() && visited.size() < vertices) {
Edge edge = minHeap.poll();
if (!visited.contains(edge.to)) {
visited.add(edge.to);
minSpanningTree.add(edge);
for (Edge nextEdge : graph.get(edge.to)) {
if (!visited.contains(nextEdge.to)) {
minHeap.offer(nextEdge);
}
}
}
}
return minSpanningTree;
}
public static void main(String[] args) {
List<List<Edge>> graph = new ArrayList<>();
int vertices = 5;
for (int i = 0; i < vertices; i++) {
graph.add(new ArrayList<>());
}
// 添加边
graph.get(0).add(new Edge(0, 1, 2));
graph.get(1).add(new Edge(1, 0, 2));
graph.get(0).add(new Edge(0, 3, 6));
graph.get(3).add(new Edge(3, 0, 6));
graph.get(1).add(new Edge(1, 2, 3));
graph.get(2).add(new Edge(2, 1, 3));
graph.get(1).add(new Edge(1, 3, 8));
graph.get(3).add(new Edge(3, 1, 8));
graph.get(1).add(new Edge(1, 4, 5));
graph.get(4).add(new Edge(4, 1, 5));
graph.get(2).add(new Edge(2, 4, 7));
graph.get(4).add(new Edge(4, 2, 7));
List<Edge> minSpanningTree = primMST(graph);
System.out.println("最小生成树的边集合：");
for (Edge edge : minSpanningTree) {
System.out.println("(" + edge.from + " -> " + edge.to + "), Weight: " + edge.weight);
}
}
}
逻辑步骤：
- 初始化一个空的最小生成树和一个已访问的顶点集合，将任意一个顶点加入已访问集合中。
- 从已访问集合中的顶点出发，选择一条与当前生成树相连的最短边，将其加入最小生成树，并将与该边连接的顶点加入已访问集合中。
- 重复步骤2，直到所有顶点都被访问。
业务场景和案例说明：
Prim 算法在网络设计、物流运输、智慧城市等领域有广泛的应用。一个典型的应用场景是在城市规划中，通过 Prim 算法可以帮助城市规划部门设计出一条最优的供水管道网络，以确保城市各个区域都能够获得充足的供水，并且减少供水管道的总长度和成本。这种应用有助于提高城市基础设施的建设效率和节约资源成本。
10.图的最短路径-Bellman-Ford算法
实现原理：
Bellman-Ford 算法用于解决带有负权边的图的单源最短路径问题。它通过对所有边进行松弛操作来逐步逼近最短路径的值，直到达到最优解。该算法适用于存在负权边但不存在负权环的图。
示例代码：
import java.util.*;
public class BellmanFordAlgorithm {
static class Edge {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
public static void bellmanFord(List<Edge> edges, int V, int source) {
int[] distance = new int[V];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[source] = 0;
// Relax all edges |V| - 1 times
for (int i = 0; i < V - 1; i++) {
for (Edge edge : edges) {
if (distance[edge.src] != Integer.MAX_VALUE && distance[edge.src] + edge.weight < distance[edge.dest]) {
distance[edge.dest] = distance[edge.src] + edge.weight;
}
}
}
// Check for negative-weight cycles
for (Edge edge : edges) {
if (distance[edge.src] != Integer.MAX_VALUE && distance[edge.src] + edge.weight < distance[edge.dest]) {
System.out.println("图中存在负权环！");
return;
}
}
// Print shortest distances
System.out.println("顶点\t\t最短距离");
for (int i = 0; i < V; i++) {
System.out.println(i + "\t\t" + distance[i]);
}
}
public static void main(String[] args) {
int V = 5; // 顶点数
int source = 0; // 源顶点
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, -1));
edges.add(new Edge(0, 2, 4));
edges.add(new Edge(1, 2, 3));
edges.add(new Edge(1, 3, 2));
edges.add(new Edge(1, 4, 2));
edges.add(new Edge(3, 2, 5));
edges.add(new Edge(3, 1, 1));
edges.add(new Edge(4, 3, -3));
bellmanFord(edges, V, source);
}
}
逻辑步骤：
- 初始化源顶点到所有顶点的距离为无穷大，源顶点到自身的距离为 0。
- 重复进行 V-1 次松弛操作，其中 V 为顶点数，每次遍历所有边，尝试通过当前边缩短源顶点到目标顶点的距离。
- 检查是否存在负权环，如果某次松弛操作导致了距离的进一步缩短，则说明图中存在负权环。
- 输出最短距离。
业务场景和案例说明：
Bellman-Ford 算法在网络路由、金融风险管理、交通规划等领域有广泛的应用。例如，在网络路由中，该算法可以帮助路由器选择最优路径来转发数据包，以提高网络的性能和稳定性。在金融风险管理中，Bellman-Ford 算法可以用来评估不同资产之间的风险和收益，以便制定合理的投资策略。在交通规划中，该算法可以用来规划最优的交通路线，以减少交通拥堵和能源消耗。
11.图的最小生成树-Kruskal算法
实现原理：
Kruskal 算法是一种用于构建无向图的最小生成树的贪心算法。
它通过不断地选择边来构建最小生成树，并确保所选的边不会形成环，直到生成树覆盖了图中的所有顶点。Kruskal 算法适用于边的权值不全为正数的图。
示例代码：
import java.util.*;
public class KruskalAlgorithm {
static class Edge implements Comparable<Edge> {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
static class DisjointSet {
int[] parent, rank;
public DisjointSet(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
}
public static List<Edge> kruskalMST(List<Edge> edges, int V) {
List<Edge> minSpanningTree = new ArrayList<>();
Collections.sort(edges); // 按权重排序
DisjointSet disjointSet = new DisjointSet(V);
for (Edge edge : edges) {
int srcParent = disjointSet.find(edge.src);
int destParent = disjointSet.find(edge.dest);
if (srcParent != destParent) {
minSpanningTree.add(edge);
disjointSet.union(srcParent, destParent);
}
}
return minSpanningTree;
}
public static void main(String[] args) {
int V = 4; // 顶点数
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 10));
edges.add(new Edge(0, 2, 6));
edges.add(new Edge(0, 3, 5));
edges.add(new Edge(1, 3, 15));
edges.add(new Edge(2, 3, 4));
List<Edge> minSpanningTree = kruskalMST(edges, V);
System.out.println("最小生成树的边集合：");
for (Edge edge : minSpanningTree) {
System.out.println("(" + edge.src + " -> " + edge.dest + "), Weight: " + edge.weight);
}
}
}
逻辑步骤：
- 初始化一个空的最小生成树集合。
- 对图中的所有边按权重进行排序。
- 遍历排序后的边集合，依次将边加入最小生成树中，但不加入会形成环的边。
- 使用并查集来判断两个顶点是否在同一连通分量中，避免加入会形成环的边。
业务场景和案例说明：
Kruskal 算法在网络设计、城市规划等领域有广泛的应用。例如，在网络设计中，可以使用 Kruskal 算法设计出一条最优的光纤网络，以满足不同用户的网络需求并降低网络成本。在城市规划中，Kruskal 算法可以帮助规划部门设计出一条最优的供电网络，以确保城市各个区域都能够获得高效供电，并且降低供电网络的总成本。
12.协同过滤推荐算法
实现原理：
协同过滤是一种常用的推荐算法，它基于用户的历史行为数据，发现用户与用户或者物品与物品之间的相似性，然后利用这种相似性来进行推荐。协同过滤算法分为基于用户的协同过滤和基于物品的协同过滤两种方法。
- 基于用户的协同过滤：通过计算用户之间的相似度，推荐给目标用户与相似度高的其他用户喜欢的物品。
- 基于物品的协同过滤：通过计算物品之间的相似度，推荐给目标用户喜欢的物品相似的其他物品。
示例代码：
import java.util.*;
public class CollaborativeFiltering {
static class Rating {
int userId;
int itemId;
double rating;
public Rating(int userId, int itemId, double rating) {
this.userId = userId;
this.itemId = itemId;
this.rating = rating;
}
}
static class User {
int userId;
Map<Integer, Double> ratings;
public User(int userId) {
this.userId = userId;
this.ratings = new HashMap<>();
}
public void addRating(int itemId, double rating) {
ratings.put(itemId, rating);
}
public double getRating(int itemId) {
return ratings.getOrDefault(itemId, 0.0);
}
}
public static double pearsonCorrelation(User user1, User user2) {
Set<Integer> commonItems = new HashSet<>(user1.ratings.keySet());
commonItems.retainAll(user2.ratings.keySet());
if (commonItems.size() == 0) {
return 0.0;
}
double sum1 = 0, sum2 = 0, sumSq1 = 0, sumSq2 = 0, sumProducts = 0;
int n = commonItems.size();
for (int itemId : commonItems) {
double rating1 = user1.getRating(itemId);
double rating2 = user2.getRating(itemId);
sum1 += rating1;
sum2 += rating2;
sumSq1 += rating1 * rating1;
sumSq2 += rating2 * rating2;
sumProducts += rating1 * rating2;
}
double numerator = sumProducts - (sum1 * sum2 / n);
double denominator = Math.sqrt((sumSq1 - sum1 * sum1 / n) * (sumSq2 - sum2 * sum2 / n));
if (denominator == 0) {
return 0.0;
}
return numerator / denominator;
}
public static List<Rating> recommend(User targetUser, List<User> users, int numRecommendations) {
Map<Integer, Double> weightedRatings = new HashMap<>();
Map<Integer, Double> similaritySums = new HashMap<>();
for (User user : users) {
if (user.userId == targetUser.userId) {
continue;
}
double similarity = pearsonCorrelation(targetUser, user);
if (similarity <= 0) {
continue;
}
for (Map.Entry<Integer, Double> entry : user.ratings.entrySet()) {
int itemId = entry.getKey();
double rating = entry.getValue();
if (!targetUser.ratings.containsKey(itemId) || targetUser.getRating(itemId) == 0) {
weightedRatings.put(itemId, weightedRatings.getOrDefault(itemId, 0.0) + similarity * rating);
similaritySums.put(itemId, similaritySums.getOrDefault(itemId, 0.0) + similarity);
}
}
}
List<Rating> recommendations = new ArrayList<>();
for (Map.Entry<Integer, Double> entry : weightedRatings.entrySet()) {
int itemId = entry.getKey();
double weightedRatingSum = entry.getValue();
double similaritySum = similaritySums.get(itemId);
double predictedRating = similaritySum != 0 ? weightedRatingSum / similaritySum : 0.0;
recommendations.add(new Rating(targetUser.userId, itemId, predictedRating));
}
recommendations.sort((r1, r2) -> Double.compare(r2.rating, r1.rating)); // Sort in descending order
return recommendations.subList(0, Math.min(numRecommendations, recommendations.size()));
}
public static void main(String[] args) {
List<User> users = new ArrayList<>();
users.add(new User(1));
users.add(new User(2));
users.add(new User(3));
users.get(0).addRating(1, 3.0);
users.get(0).addRating(2, 4.0);
users.get(0).addRating(3, 5.0);
users.get(1).addRating(1, 2.0);
users.get(1).addRating(2, 3.0);
users.get(2).addRating(1, 5.0);
users.get(2).addRating(3, 2.0);
User targetUser = new User(4);
targetUser.addRating(2, 4.0);
targetUser.addRating(3, 3.0);
List<Rating> recommendations = recommend(targetUser, users, 2);
System.out.println("推荐结果：");
for (Rating rating : recommendations) {
System.out.println("用户 " + targetUser.userId + " 可能会喜欢物品 " + rating.itemId + "，预测评分为 " + rating.rating);
}
}
}
逻辑步骤：
- 计算用户之间的相似度，常用的相似度计算方法包括皮尔逊相关系数、余弦相似度等。
- 根据用户相似度和其他用户的评分，为目标用户推荐未评分的物品。
- 根据推荐物品的预测评分，返回给用户。
业务场景和案例说明：
协同过滤推荐算法在电子商务、社交网络、视频点播等领域有广泛的应用。例如，在电子商务平台上，可以根据用户的历史购买记录和行为数据，为用户推荐可能感兴趣的商品。在社交网络中，可以根据用户之间的好友关系和行为相似性，推荐给用户可能感兴趣的文章、视频等内容。在视频点播平台中，可以根据用户的观看历史和喜好，推荐给用户可能喜欢的电影、电视剧等节目。
以上是协同过滤推荐算法的简单实现和应用场景。这种算法能够根据用户的历史行为和偏好，为用户提供个性化的推荐，从而提升用户体验和平台的粘性，是推荐系统中常用的一种方法。
13.基于内容的推荐算法
实现原理：
基于内容的推荐算法是根据物品的内容特征和用户的偏好之间的匹配程度来进行推荐的。它不同于协同过滤算法，而是通过分析物品的属性或特征，以及用户的历史偏好来进行推荐。通常，基于内容的推荐算法会使用文本挖掘、自然语言处理等技术来分析物品的内容特征，并根据这些特征与用户偏好的匹配程度来进行推荐。
示例代码：
import java.util.*;
public class ContentBasedRecommendation {
static class Item {
int itemId;
String[] features;
public Item(int itemId, String[] features) {
this.itemId = itemId;
this.features = features;
}
}
static class User {
int userId;
Map<Integer, Double> preferences;
public User(int userId) {
this.userId = userId;
this.preferences = new HashMap<>();
}
public void addPreference(int itemId, double preference) {
preferences.put(itemId, preference);
}
public double getPreference(int itemId) {
return preferences.getOrDefault(itemId, 0.0);
}
}
public static double cosineSimilarity(String[] features1, String[] features2) {
double dotProduct = 0, norm1 = 0, norm2 = 0;
for (int i = 0; i < features1.length; i++) {
dotProduct += Double.parseDouble(features1[i]) * Double.parseDouble(features2[i]);
norm1 += Math.pow(Double.parseDouble(features1[i]), 2);
norm2 += Math.pow(Double.parseDouble(features2[i]), 2);
}
double similarity = dotProduct / (Math.sqrt(norm1) * Math.sqrt(norm2));
return similarity;
}
public static List<Item> recommend(User user, List<Item> items, int numRecommendations) {
Map<Integer, Double> scores = new HashMap<>();
for (Item item : items) {
double score = 0;
for (Map.Entry<Integer, Double> entry : user.preferences.entrySet()) {
int itemId = entry.getKey();
double preference = entry.getValue();
score += preference * cosineSimilarity(user.features, item.features);
}
scores.put(item.itemId, score);
}
List<Item> recommendations = new ArrayList<>();
scores.entrySet().stream()
.sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
.limit(numRecommendations)
.forEach(entry -> {
int itemId = entry.getKey();
double score = entry.getValue();
recommendations.add(new Item(itemId, null)); // Replace null with actual features
});
return recommendations;
}
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item(1, new String[]{
"1", "0", "1"}));
items.add(new Item(2, new String[]{
"0", "1", "0"}));
items.add(new Item(3, new String[]{
"1", "1", "1"}));
User user = new User(1);
user.addPreference(1, 3.0);
user.addPreference(2, 4.0);
List<Item> recommendations = recommend(user, items, 2);
System.out.println("推荐结果：");
for (Item item : recommendations) {
System.out.println("用户 " + user.userId + " 可能会喜欢物品 " + item.itemId);
}
}
}
逻辑步骤：
- 计算用户偏好与物品内容特征之间的相似度，常用的相似度计算方法包括余弦相似度、欧氏距离等。
- 根据相似度计算用户对物品的兴趣程度，得到每个物品的推荐分数。
- 根据推荐分数，为用户推荐与之相似度高的物品。
业务场景和案例说明：
基于内容的推荐算法在新闻推荐、音乐推荐、商品推荐等场景有着广泛的应用。例如，在新闻推荐系统中，可以根据用户浏览的新闻内容特征，推荐与之相似的其他新闻。在音乐推荐系统中，可以根据用户喜欢的音乐的音频特征，推荐与之相似的其他音乐。在商品推荐系统中，可以根据用户购买或点击的商品的属性特征，推荐与之相似的其他商品。
14.K-均值聚类算法
实现原理：
K-均值聚类算法是一种常用的无监督学习算法，用于将数据集分成 K 个不同的簇。该算法通过迭代优化，将数据点划分到最近的簇，并更新簇的中心点，直到达到收敛条件。K-均值聚类算法的核心步骤包括初始化簇中心点、计算每个数据点与簇中心的距离、将数据点分配到最近的簇、更新簇的中心点，不断重复这些步骤直到收敛。
示例代码：
import java.util.*;
public class KMeansClustering {
static class Point {
double x, y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public double distance(Point other) {
return Math.sqrt(Math.pow(x - other.x, 2) + Math.pow(y - other.y, 2));
}
public void set(Point other) {
this.x = other.x;
this.y = other.y;
}
}
public static List<List<Point>> kMeans(List<Point> dataPoints, int k, int maxIterations) {
List<Point> centroids = new ArrayList<>();
Random random = new Random();
// Initialize centroids randomly
for (int i = 0; i < k; i++) {
int randomIndex = random.nextInt(dataPoints.size());
centroids.add(new Point(dataPoints.get(randomIndex).x, dataPoints.get(randomIndex).y));
}
List<List<Point>> clusters = new ArrayList<>();
for (int i = 0; i < k; i++) {
clusters.add(new ArrayList<>());
}
for (int iteration = 0; iteration < maxIterations; iteration++) {
// Assign data points to nearest centroid
for (Point point : dataPoints) {
int nearestCentroidIndex = 0;
double minDistance = Double.MAX_VALUE;
for (int i = 0; i < k; i++) {
double distance = point.distance(centroids.get(i));
if (distance < minDistance) {
minDistance = distance;
nearestCentroidIndex = i;
}
}
clusters.get(nearestCentroidIndex).add(point);
}
// Update centroids
for (int i = 0; i < k; i++) {
double sumX = 0, sumY = 0;
List<Point> cluster = clusters.get(i);
for (Point point : cluster) {
sumX += point.x;
sumY += point.y;
}
centroids.get(i).x = sumX / cluster.size();
centroids.get(i).y = sumY / cluster.size();
cluster.clear(); // Clear the cluster for next iteration
}
}
return clusters;
}
public static void main(String[] args) {
List<Point> dataPoints = new ArrayList<>();
dataPoints.add(new Point(1, 1));
dataPoints.add(new Point(1, 2));
dataPoints.add(new Point(2, 1));
dataPoints.add(new Point(5, 4));
dataPoints.add(new Point(6, 5));
dataPoints.add(new Point(6, 6));
int k = 2; // Number of clusters
int maxIterations = 1000; // Maximum number of iterations
List<List<Point>> clusters = kMeans(dataPoints, k, maxIterations);
for (int i = 0; i < clusters.size(); i++) {
System.out.println("Cluster " + (i + 1) + ": " + clusters.get(i));
}
}
}
逻辑步骤：
- 随机初始化 K 个簇中心点。
- 计算每个数据点与簇中心点的距离，并将数据点分配到最近的簇。
- 更新每个簇的中心点，计算新的簇中心点。
- 重复步骤 2 和步骤 3，直到簇中心点不再发生变化或达到最大迭代次数。
业务场景和案例说明：
K-均值聚类算法在数据分析、图像分割、市场分析等领域有着广泛的应用。例如，在数据分析中，可以利用 K-均值聚类算法对客户数据进行聚类，识别出具有相似特征的客户群体，从而制定针对性的营销策略。在图像分割中，可以利用 K-均值聚类算法对图像像素进行聚类，实现图像的分割和物体识别。在市场分析中，可以利用 K-均值聚类算法对市场数据进行聚类，发现潜在的市场细分和目标客户群体。
15.决策树算法
实现原理：
决策树算法是一种常用的监督学习算法，用于分类和回归任务。它通过对数据集进行递归地划分，构建一棵树形结构，每个节点表示一个属性特征，每个分支表示一个特征值，叶子节点表示一个类别（分类任务）或者一个数值（回归任务）。决策树的构建过程通常包括特征选择、节点划分和树的剪枝等步骤。
示例代码：
import java.util.*;
public class DecisionTree {
static class TreeNode {
int featureIndex; // 特征索引
String decision; // 决策结果
Map<String, TreeNode> children; // 子节点
public TreeNode() {
children = new HashMap<>();
}
}
public static TreeNode buildDecisionTree(List<String[]> data, String[] features) {
if (data.isEmpty()) {
return null;
}
Set<String> uniqueLabels = new HashSet<>();
for (String[] instance : data) {
uniqueLabels.add(instance[instance.length - 1]);
}
// 如果所有实例的类别相同，则返回单节点树
if (uniqueLabels.size() == 1) {
TreeNode leaf = new TreeNode();
leaf.decision = uniqueLabels.iterator().next();
return leaf;
}
// 如果特征集为空，则返回类别数最多的类别作为叶子节点
if (features.length == 0) {
TreeNode leaf = new TreeNode();
leaf.decision = majorityVote(data);
return leaf;
}
// 选择最佳特征进行划分
int bestFeatureIndex = selectBestFeature(data, features);
TreeNode root = new TreeNode();
root.featureIndex = bestFeatureIndex;
// 根据最佳特征进行划分
Map<String, List<String[]>> dividedData = divideData(data, bestFeatureIndex);
for (Map.Entry<String, List<String[]>> entry : dividedData.entrySet()) {
String featureValue = entry.getKey();
List<String[]> subset = entry.getValue();
String[] newFeatures = Arrays.copyOf(features, features.length - 1); // 移除已选特征
root.children.put(featureValue, buildDecisionTree(subset, newFeatures));
}
return root;
}
public static int selectBestFeature(List<String[]> data, String[] features) {
// 在这里实现特征选择的方法，比如信息增益、基尼指数等
// 这里简化为随机选择特征
return new Random().nextInt(features.length);
}
public static Map<String, List<String[]>> divideData(List<String[]> data, int featureIndex) {
Map<String, List<String[]>> dividedData = new HashMap<>();
for (String[] instance : data) {
String featureValue = instance[featureIndex];
dividedData.putIfAbsent(featureValue, new ArrayList<>());
dividedData.get(featureValue).add(instance);
}
return dividedData;
}
public static String majorityVote(List<String[]> data) {
// 返回类别数最多的类别
Map<String, Integer> labelCounts = new HashMap<>();
for (String[] instance : data) {
String label = instance[instance.length - 1];
labelCounts.put(label, labelCounts.getOrDefault(label, 0) + 1);
}
return Collections.max(labelCounts.entrySet(), Map.Entry.comparingByValue()).getKey();
}
public static void main(String[] args) {
List<String[]> data = new ArrayList<>();
data.add(new String[]{
"青年", "否", "否", "一般", "否"});
data.add(new String[]{
"青年", "否", "否", "好", "否"});
data.add(new String[]{
"青年", "是", "否", "好", "是"});
data.add(new String[]{
"青年", "是", "是", "一般", "是"});
data.add(new String[]{
"青年", "否", "否", "一般", "否"});
data.add(new String[]{
"中年", "否", "否", "一般", "否"});
data.add(new String[]{
"中年", "否", "否", "好", "否"});
data.add(new String[]{
"中年", "是", "是", "好", "是"});
data.add(new String[]{
"中年", "否", "是", "非常好", "是"});
data.add(new String[]{
"中年","否", "是", "非常好", "是"});
data.add(new String[]{
"老年", "否", "是", "非常好", "是"});
data.add(new String[]{
"老年", "否", "是", "好", "是"});
data.add(new String[]{
"老年", "是", "否", "好", "是"});
data.add(new String[]{
"老年", "是", "否", "非常好", "是"});
data.add(new String[]{
"老年", "否", "否", "一般", "否"});
String[] features = {
"年龄", "有工作", "有自己的房子", "信贷情况"};
TreeNode root = buildDecisionTree(data, features);
printDecisionTree(root, 0);
}
public static void printDecisionTree(TreeNode root, int depth) {
if (root == null) {
return;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < depth; i++) {
sb.append(" ");
}
if (root.decision != null) {
sb.append("-> ").append(root.decision);
System.out.println(sb.toString());
return;
}
sb.append("Feature ").append(root.featureIndex).append(":");
System.out.println(sb.toString());
for (Map.Entry<String, TreeNode> entry : root.children.entrySet()) {
System.out.print(entry.getKey() + " ");
printDecisionTree(entry.getValue(), depth + 1);
}
}
}
逻辑步骤：
- 选择最佳特征进行划分，通常使用信息增益、基尼指数等指标来评估特征的重要性。
- 根据最佳特征将数据集划分为多个子集。
- 递归地在每个子集上构建决策树。
- 直到满足停止条件，如节点中的样本全部属于同一类别，或者特征集为空。
业务场景和案例说明：
决策树算法在医学诊断、金融风控、客户分类等领域有着广泛的应用。例如，在医学诊断中，可以根据患者的症状和体征构建决策树模型，帮助医生诊断疾病。在金融风控中，可以根据客户的信用评级和财务状况构建决策树模型，评估客户的信用风险。在客户分类中，可以根据客户的消费行为和偏好构建决策树模型，将客户分为不同的细分群体，制定个性化营销策略。
最后
V哥最后再啰嗦几句，常用的算法理解起来还是有难度的，大多数初中级程序员接触的机会也不多，但我们不能因为不接触就放弃研究和积累算法，除非你不想往更高的技术架构或高级去走，算法通常都是比较成熟的，拿来即用也不是不可以，这是第一步解决问题，然后再慢慢研究理解，因为项目中的核心技术永远掌握在公司那些天价核心的技术人员手里，今天的内容就分享到这里。
