Java算法题类型及解法

以下为你详细介绍算法题常见的解法、类型，并给出相应的 Java 代码示例。

1. 暴力解法

说明：暴力解法是一种直接求解问题的方法，它通常通过枚举所有可能的解，然后逐一检查这些解是否满足问题的条件。这种方法简单直接，但在处理大规模问题时效率可能较低。
适用类型：适用于问题规模较小，且可能的解空间有限的情况。
示例问题：给定一个整数数组和一个目标值，找出数组中两个数的和等于目标值的所有组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.ArrayList;
import java.util.List;

public class TwoSumBruteForce {
    public static List<int[]> twoSum(int[] nums, int target) {
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result.add(new int[]{i, j});
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        List<int[]> pairs = twoSum(nums, target);
        for (int[] pair : pairs) {
            System.out.println("Indices: " + pair[0] + ", " + pair[1]);
        }
    }
}

2. 分治法

说明：分治法将一个复杂的问题分解为多个相似的子问题，然后递归地解决这些子问题，最后将子问题的解合并得到原问题的解。
适用类型：适用于问题可以分解为多个相互独立且结构与原问题相似的子问题的情况，如排序、搜索等。
示例问题：使用分治法实现归并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = left;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        mergeSort(arr);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

3. 动态规划

说明：动态规划通过将原问题分解为相对简单的子问题，并保存子问题的解来避免重复计算，从而提高算法的效率。
适用类型：适用于具有最优子结构和重叠子问题的问题，如背包问题、最长公共子序列等。
示例问题：计算斐波那契数列的第 n 项。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FibonacciDynamicProgramming {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 5;
        System.out.println("Fibonacci number at position " + n + " is: " + fibonacci(n));
    }
}

4. 贪心算法

说明：贪心算法在每一步都做出当前看来最优的选择，希望通过局部最优解来达到全局最优解。
适用类型：适用于具有贪心选择性质和最优子结构的问题，如活动选择问题、哈夫曼编码等。
示例问题：给定一些硬币面额和一个总金额，计算最少需要多少个硬币来组成这个金额。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Arrays;

public class CoinChangeGreedy {
    public static int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int count = 0;
        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                count++;
            }
        }
        return amount == 0 ? count : -1;
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("Minimum number of coins: " + coinChange(coins, amount));
    }
}

5. 回溯算法

说明：回溯算法通过深度优先搜索的方式遍历所有可能的解空间，当发现当前的解不满足问题的条件时，回溯到上一步，尝试其他的选择。
适用类型：适用于求解组合、排列、子集等问题，如八皇后问题、全排列问题等。
示例问题：生成给定数组的所有全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.ArrayList;
import java.util.List;

public class Permutations {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);
        return result;
    }

    private static void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tempList.contains(nums[i])) continue;
                tempList.add(nums[i]);
                backtrack(result, tempList, nums);
                tempList.remove(tempList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permutations = permute(nums);
        for (List<Integer> permutation : permutations) {
            System.out.println(permutation);
        }
    }
}