本文共 1789 字，大约阅读时间需要 5 分钟。

贪心算法

贪心算法的名字直接点明了它的特点：在解决问题的过程中，始终选择当前最有利的选项，以期望实现全局最优解。这种算法在很多场景中都能发挥出色表现，尤其是在需要快速决策且对全局影响不敏感的领域。

分发饼干

假设你是一位家长，想要给孩子们分发饼干。每个孩子都有一个胃口值，这个值代表他们满足胃口所需的最小饼干尺寸。饼干的尺寸各不相同，给每个孩子分发饼干的目标是让尽可能多的孩子得到满足。

问题分析

解决方案

通过对饼干尺寸和孩子胃口值进行排序，采用贪心算法依次尝试分发饼干。具体步骤如下：

跳跃游戏

给定一个非负整数数组，表示每个位置可以跳跃的最大步数。目标是用最少的跳跃次数到达数组的最后一个位置。

解决思路

解决代码

int jump(int* nums, int numsSize) {
    if (numsSize == 1) return 0;
    int count = 0;
    int max = 0;
    int sub = 0;
    int i = 0;
    while (i < numsSize) {
        if (nums[i] + i >= numsSize - 1) {
            count++;
            return count;
        }
        sub = 0;
        max = 0;
        for (int j = 1; j <= nums[i]; j++) {
            if (nums[i + j] + j > max) {
                max = nums[i + j] + j;
                sub = j;
            }
        }
        count++;
        i += sub;
    }
    return count;
}

避免重复字母的最小删除成本

给定一个字符串和一个整数数组，表示每个字符删除的成本。目标是通过删除最小数量的字符，使得字符串中任意相邻两个字符都不相同。

解决思路

解决代码

int minCost(char* s, int* cost, int costSize) {
    int count = 0;
    int prev_sub = 0;
    int next_sub = 1;
    while (next_sub < costSize) {
        if (s[prev_sub] == s[next_sub]) {
            if (cost[prev_sub] < cost[next_sub]) {
                count += cost[prev_sub];
                // 删除前指针位置的字符
                prev_sub++;
            } else {
                count += cost[next_sub];
                next_sub++;
            }
        } else {
            next_sub++;
        }
    }
    return count;
}

本文通过对四种算法问题的详细解读和代码实现，展示了贪心算法在不同场景中的应用。每个算法都采用了贪心思想，通过局部最优解的选择来实现全局最优解。