java经典算法题递归回溯贪心

### Java 中的经典算法题目解析 #### 递归算法实例 在 Java 编程中，递归是一种常见的编程技巧。通过函数调用自身来解决问题。经典的例子有： - **阶乘求解** - 计算 n 的阶乘可以通过定义一个方法 `factorial` 来实现，在该方法内部判断如果 n 等于 0 或者 1 则返回 1；否则返回 n 乘以 factorial(n - 1)[^2]。 ```java public class Factorial { public static int factorial(int n) { if (n == 0 || n == 1) return 1; else return n * factorial(n - 1); } } ``` - **汉诺塔问题** - 这个问题是关于如何移动一组不同大小圆盘从一根柱子到另一根柱子而不违反特定规则的一个难题。解决此问题的方法也是利用递归来完成每一步的操作[^2]。 ```java public class HanoiTower { public static void moveDisks(int n, char fromPeg, char toPeg, char auxPeg) { if (n == 1) System.out.println("Move disk 1 from peg " + fromPeg + " to peg " + toPeg); else { moveDisks(n - 1, fromPeg, auxPeg, toPeg); System.out.println("Move disk " + n + " from peg " + fromPeg + " to peg " + toPeg); moveDisks(n - 1, auxPeg, toPeg, fromPeg); } } } ``` #### 回溯算法实例 回溯法用于寻找所有可能的解决方案并从中挑选最优方案或者满足条件的第一个方案。典型的应用场景如下： - **八皇后问题** - 将八个皇后放置在一个 8×8 的国际象棋棋盘上，并使得它们彼此之间不会相互攻击。这个问题可以使用回溯法逐步尝试每一列的位置直到找到合适的组合为止。 ```java import java.util.Arrays; class EightQueens { private final int size = 8; private int[] queens = new int[size]; public boolean solve() { Arrays.fill(queens, -1); return backtrack(0); } private boolean backtrack(int row) { if (row == size) return true; for (int col = 0; col < size; ++col) { if (isSafe(row, col)) { queens[row] = col; if (backtrack(row + 1)) return true; queens[row] = -1; } } return false; } private boolean isSafe(int row, int col) { for (int i = 0; i < row; ++i) if (queens[i] == col || Math.abs(queens[i] - col) == Math.abs(i - row)) return false; return true; } } ``` #### 贪心算法实例 贪心算法总是做出当前看起来最佳的选择，期望以此获得全局最优解。下面给出两个具体案例： - **活动安排问题** - 假设有若干项活动都需要占用同一资源（比如会议室），而这些活动中有些可能会发生冲突即在同一时间内无法同时举行。此时就可以采用贪心策略按照结束时间从小到达排序之后依次选取最早结束且不与其他已选中的事件重叠的新事件加入集合当中去直至遍历完所有的候选对象位置[^4]。 ```java import java.util.*; class ActivitySelection { List<Activity> activities = new ArrayList<>(); record Activity(Integer start, Integer finish) {} Set<Integer> selectActivities() { Collections.sort(activities, Comparator.comparing(Activity::finish)); var selectedIndices = new HashSet<Integer>(); int lastFinishTime = 0; for (var activity : activities.stream().sorted(Comparator.comparing(Activity::start)).toList()) { if (!selectedIndices.contains(activity.start())) continue; if (activity.start() >= lastFinishTime) { selectedIndices.add(activity.finish()); lastFinishTime = activity.finish(); } } return selectedIndices; } } ``` - **最小生成树-Kruskal算法** - Kruskal 是一种用来构建连通无向加权图最小生成树的有效方式之一。其核心思想在于每次从未被处理过的边集中选出权重最小的一条连接尚未相连节点之间的边作为新成员添加进来形成新的部分森林结构重复上述过程直到整个网络完全联通起来为止。 ```java import java.util.*; import org.javatuples.Pair; class MinimumSpanningTreeKruskal { Map<String, String> parentMap = new HashMap<>(); PriorityQueue<Pair<Double, Pair<String, String>>> edgesQueue = new PriorityQueue<>(Comparator.comparing(Pair::getValue0)); void addEdge(double weight, String u, String v) { edgesQueue.offer(Pair.with(weight, Pair.with(u, v))); } String findSet(String node) { while (parentMap.get(node) != null && !node.equals(parentMap.get(node))) { node = parentMap.get(node); } return node; } void unionSets(String setA, String setB) { parentMap.put(setA, setB); } double computeMSTCost() { double cost = 0d; while(!edgesQueue.isEmpty()){ var edge = edgesQueue.poll(); var nodes = edge.getValue1(); var rootU = findSet(nodes.getValue0()),rootV=findSet(nodes.getValue1()); if(rootU!=rootV){ cost+=edge.getValue0(); unionSets(rootU,rootV); } } return cost; } } ```