小菜鸟

java菜鸟号正在起航

0%

基本算法

发表于 更新于 分类于 阅读次数： 33 Valine： 0
本文字数： 4.6k 阅读时长 ≈ 4 分钟

算法基本使用：从经典问题看算法思想

算法是解决问题的步骤化策略，不同算法思想适用于不同场景。本文结合具体示例，解析最大公约数、递推、递归、分治、穷举、贪婪、回溯等经典算法的核心思想与实现。

最大公约数（欧几里得算法）

核心思想：利用 “两个数的最大公约数等于其中较小数与两数余数的最大公约数” 这一性质，通过反复取模简化问题，直至余数为 0。

算法步骤

  1. 若 m < n，交换 m 和 n（确保 m ≥ n）。
  2. 计算 m % n（m 除以 n 的余数）。
  3. 若余数为 0，则 n 即为最大公约数；否则，令 m = n，n = 余数，重复步骤 2。

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxCommonDisvisor(int m, int n) {
    int temp;
    // 确保 m ≥ n
    if (m < n) {
        temp = m;
        m = n;
        n = temp;
    }
    while (true) {
        if (m % n == 0) { // 余数为0，n是最大公约数
            return n;
        }
        // 迭代：m = n，n = 余数
        temp = m % n;
        m = n;
        n = temp;
    }
}

扩展

  • 更相减损术：通过反复用大数减小数（而非取模）求最大公约数，适合无法高效取模的场景（如大数运算）。
  • 最小公倍数：两数乘积除以最大公约数，即 lcm(m, n) = m * n / gcd(m, n)。

递推算法

核心思想：从已知条件出发，通过迭代计算中间结果，逐步推导出最终答案（分顺推和逆推）。

经典示例：斐波那契数列

斐波那契数列定义为：f(0)=1，f(1)=1，f(n)=f(n-1)+f(n-2)（n ≥ 2）。

代码解析（顺推）

1
2
3
4
5
6
7
8
9
10
11
12
public void fs(int num) {
    int[] fs = new int[num];
    // 初始条件
    fs[0] = 1;
    fs[1] = 1;
    // 顺推：从已知项计算未知项
    for (int i = 2; i < num; i++) {
        fs[i] = fs[i - 1] + fs[i - 2];
    }
    // 输出结果
    Arrays.stream(fs).forEach(System.out::println);
}

特点

  • 优点：效率高（时间复杂度 O(n)），无递归栈溢出风险。
  • 适用场景：问题可分解为递推关系（如数列、动态规划基础）。

递归算法

核心思想：函数通过调用自身解决子问题，需明确终止条件（避免无限递归）和递推关系。

经典示例：十进制转二进制

通过反复除以 2 取余，余数逆序即为二进制数。

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void tenToTwo(int ten, StringBuilder sb) {
    if (ten == 0) { // 终止条件：商为0时停止递归
        return;
    }
    // 递推：记录余数，递归处理商
    sb.append(ten % 2);
    tenToTwo(ten / 2, sb);
}

// 调用示例
public static void main(String[] args) {
    StringBuilder sb = new StringBuilder();
    tenToTwo(10, sb);
    System.out.println(sb.reverse().toString()); // 输出 "1010"
}

特点

  • 优点：代码简洁，符合人类思维习惯。
  • 缺点：可能因递归深度过大导致栈溢出，效率低于递推（函数调用开销）。
  • 适用场景：问题具有明显递归结构（如树遍历、分治算法）。

分治算法

核心思想：“分而治之”，将大问题分解为规模更小的子问题，解决子问题后合并结果。

经典示例：快速排序

  1. 分：选择基准元素，将数组分为 “小于基准” 和 “大于基准” 两部分。
  2. 治：递归排序两部分子数组。
  3. 合：子数组已有序，直接拼接。

核心步骤

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
public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return; // 终止条件：子数组长度为1
    int pivot = partition(arr, left, right); // 分区，返回基准位置
    quickSort(arr, left, pivot - 1); // 排序左半部分
    quickSort(arr, pivot + 1, right); // 排序右半部分
}

// 分区函数：将小于基准的元素放左，大于的放右
private int partition(int[] arr, int left, int right) {
    int pivot = arr[right]; // 选最右元素为基准
    int i = left - 1;
    for (int j = left; j < right; 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[right];
    arr[right] = temp;
    return i + 1;
}

特点

  • 优点：效率高（平均时间复杂度 O(n log n)），适合大规模问题。
  • 适用场景：问题可分解为独立子问题（如排序、矩阵乘法）。

穷举算法

核心思想：遍历所有可能的解，检查是否符合条件，本质是 “暴力搜索”。

经典示例：鸡兔同笼问题

已知头数和脚数，求鸡和兔的数量（鸡 2 脚，兔 4 脚）。

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static int chicken, rabbit;

public static boolean qiongju(int head, int foot) {
    // 遍历鸡的数量（0到head）
    for (int i = 0; i <= head; i++) {
        int j = head - i; // 兔的数量 = 总头数 - 鸡的数量
        if (i * 2 + j * 4 == foot) { // 脚数匹配
            chicken = i;
            rabbit = j;
            return true;
        }
    }
    return false; // 无解
}

特点

  • 优点：逻辑简单，无需复杂推导。
  • 缺点：效率极低（时间复杂度与解空间大小成正比）。
  • 适用场景：解空间小且无更好算法（如密码破解、简单数学问题）。

贪婪算法

核心思想：每次选择 “局部最优解”，希望通过局部最优积累得到 “全局最优解”（不一定总能实现）。

经典示例：找零钱问题

用最少的纸币数凑出指定金额（如人民币面额：100、50、20、10、5、1）。

代码解析

1
2
3
4
5
6
7
8
9
10
11
12
int[] value = {100, 50, 20, 10, 5, 1}; // 面额从大到小

public void exchange(int amount) {
    StringBuilder sb = new StringBuilder();
    for (int v : value) {
        if (amount < v) continue; // 金额小于当前面额，跳过
        int count = amount / v; // 最多使用的当前面额数量
        amount -= count * v; // 剩余金额
        sb.append(count).append("张").append(v).append("元, ");
    }
    System.out.println(sb.toString());
}

特点

  • 优点：效率高（时间复杂度 O(n)，n 为面额种类）。
  • 缺点：仅在特定场景下得到最优解（如面额为 “贪心友好” 的情况）。
  • 适用场景：问题具有 “贪心选择性质”（局部最优可导致全局最优），如活动选择、哈夫曼编码。

回溯算法

核心思想：试探性选择路径，若发现当前路径无效则回退（撤销选择），重新尝试其他路径，直至找到解或遍历所有可能。

经典示例：八皇后问题

在 8×8 棋盘上放置 8 个皇后，使她们互不攻击（不同行、列、对角线）。

核心步骤

  1. 选择：在当前行放置皇后，尝试每一列。
  2. 约束检查：检查当前位置是否与已放置的皇后冲突（同列或同对角线）。
  3. 递归：若有效，继续下一行；若无效，回溯（撤销当前选择），尝试下一列。

代码解析

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
int n = 8; // 8皇后
int[] queens = new int[n]; // 存储每行皇后的列索引（queens[i] = j 表示第i行第j列）
List<List<String>> result = new ArrayList<>();

public List<List<String>> solveNQueens() {
    backtrack(0); // 从第0行开始
    return result;
}

// 回溯函数：放置第row行的皇后
private void backtrack(int row) {
    if (row == n) { // 终止条件：所有行都放置了皇后
        result.add(generateBoard());
        return;
    }
    for (int col = 0; col < n; col++) { // 尝试当前行的每一列
        if (isValid(row, col)) { // 检查是否冲突
            queens[row] = col; // 放置皇后
            backtrack(row + 1); // 递归下一行
            queens[row] = -1; // 回溯：撤销选择
        }
    }
}

// 检查第row行第col列是否可以放置皇后
private boolean isValid(int row, int col) {
    for (int i = 0; i < row; i++) {
        // 同列或同对角线（行差=列差）
        if (queens[i] == col || Math.abs(row - i) == Math.abs(col - queens[i])) {
            return false;
        }
    }
    return true;
}

// 生成棋盘字符串
private List<String> generateBoard() {
    List<String> board = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        char[] row = new char[n];
        Arrays.fill(row, '.');
        row[queens[i]] = 'Q';
        board.add(new String(row));
    }
    return board;
}

特点

  • 优点：能找到所有解（若存在），逻辑清晰。
  • 缺点：效率较低（本质是带剪枝的穷举）。
  • 适用场景：解空间有约束条件的问题（如排列组合、迷宫求解）。

总结

不同算法思想各有侧重，选择需结合问题特性：

  • 求最大公约数用欧几里得算法（高效取模）；
  • 数列生成用递推（效率优先）或递归（代码简洁）；
  • 大规模排序用分治（如快速排序）；
  • 简单数学问题用穷举（逻辑简单）；
  • 找零钱等问题用贪婪（效率高）；
  • 约束条件下的组合问题用回溯（确保找到解）
相关文章

欢迎关注我的其它发布渠道

表情 | 预览
快来做第一个评论的人吧~
Powered By Valine
v1.3.10